“演化网络 Evolving networks”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第1行： 第1行：
 
此词条暂由彩云小译翻译，已由Steve Luo审校。
 
此词条暂由彩云小译翻译，已由Steve Luo审校。
  
−
[[Image:Barabasi Albert model.gif|thumb|256px|Animation of an evolving network according to the initial Barabasi–Albert model]]
+
[[File:256px-Barabasi_Albert_model.gif|256px|基于初始巴拉巴西-阿尔伯特 Barabasi-Albert 模型的演化网络的动画]]
  
−
Animation of an evolving network according to the initial Barabasi–Albert model
+
演化网络 Evolving networks是作为时间的函数而变化的网络。它们是网络科学 network science的自然延伸，因为几乎所有现实世界的网络都是随时间演化的，通过随着时间的推移增加或删除节点或连边实现。通常所有这些过程都是同时发生的，比如在社交网络 social networks中，随着时间的推移人们结交和失去朋友，从而创造和破坏连边，一些人成为新的社交网络的一部分，或者离开他们的网络，从而改变网络中的节点。演化网络的概念建立在既定的网络理论之上，现在正被引入到许多不同领域的网络研究中。
  
−
基于初始<font color="#ff8000">巴拉巴西-阿尔伯特 Barabasi-Albert </font>模型的演化网络的动画
+
==网络理论背景==
  
−
'''Evolving networks''' are [[complex networks|networks]] that change as a function of time. They are a natural extension of [[network science]] since almost all real world networks evolve over time, either by adding or removing [[Vertex (graph theory)|nodes]] or links over time. Often all of these processes occur simultaneously, such as in [[social networks]] where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established [[network theory]] and are now being introduced into studying networks in many diverse fields.
+
网络研究源于图论 graph theory的发展，莱昂哈德·欧拉 Leonhard Euler于1736年首先分析了图论，当时他撰写了著名的柯尼斯堡七桥问题 Seven Bridges of Königsberg论文。随后在八篇由保罗·埃尔德什 Paul Erdős和阿尔弗雷德·雷尼 Alfréd Rényi撰写的研究随机图 random graphs的著名论文的帮助下，概率网络理论得以发展。埃尔德什-雷尼模型 Erdős–Rényi model(ER模型)假定一个图由n个有标记的节点组成，其中每一对节点通过一个预设的概率p连接。
  
−
Evolving networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.
+
[[File:220px-Watts_strogatz.svg.png|220px|Watts–Strogatz graph 瓦茨-斯托加茨图]]
  
−
<font color="#ff8000">演化网络 Evolving networks</font>是作为时间的函数而变化的网络。它们是<font color="#ff8000">网络科学 network science</font>的自然延伸，因为几乎所有现实世界的网络都是随时间演化的，通过随着时间的推移增加或删除节点或连边实现。通常所有这些过程都是同时发生的，比如在<font color="#ff8000">社交网络 social networks</font>中，随着时间的推移人们结交和失去朋友，从而创造和破坏连边，一些人成为新的社交网络的一部分，或者离开他们的网络，从而改变网络中的节点。演化网络的概念建立在既定的网络理论之上，现在正被引入到许多不同领域的网络研究中。
+
尽管ER模型的简单性帮助它找到了许多应用之处，但它并不能准确地描述许多真实世界的网络。ER模型无法像在现实世界网络中那样频繁地生成局部聚类和三元闭包。为此，提出了瓦茨-斯托加茨模型 Watts-Strogatz model，将网络构造成规则的环网格，然后根据一定的概率β重新连接节点。<ref name=WS>{{cite journal  | author1 = Watts, D.J. | author2 = Strogatz, S.H. | year = 1998 | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 409–10  | doi = 10.1038/30918 | pmid = 9623998 | bibcode=1998Natur.393..440W}}</ref>
−
 
 
−
 
 
−
 
 
−
==Network theory background 网络理论背景==
 
−
 
 
−
The study of networks traces its foundations to the development of [[graph theory]], which was first analyzed by [[Leonhard Euler]] in 1736 when he wrote the famous [[Seven Bridges of Königsberg]] paper. Probabilistic network theory then developed with the help of eight famous papers studying [[random graphs]] written by [[Paul Erdős]] and [[Alfréd Rényi]]. The [[Erdős–Rényi model]] (ER) supposes that a graph is composed of '''N''' labeled nodes where each pair of nodes is connected by a preset probability '''p'''.
 
−
 
 
−
The study of networks traces its foundations to the development of graph theory, which was first analyzed by Leonhard Euler in 1736 when he wrote the famous Seven Bridges of Königsberg paper. Probabilistic network theory then developed with the help of eight famous papers studying random graphs written by Paul Erdős and Alfréd Rényi. The Erdős–Rényi model (ER) supposes that a graph is composed of N labeled nodes where each pair of nodes is connected by a preset probability p.
 
−
 
 
−
网络研究源于<font color="#ff8000">图论 graph theory</font>的发展，莱昂哈德·欧拉 Leonhard Euler于1736年首先分析了图论，当时他撰写了著名的<font color="#ff8000">柯尼斯堡七桥问题 Seven Bridges of Königsberg</font>论文。随后在八篇由保罗·埃尔德什 Paul Erdős和阿尔弗雷德·雷尼 Alfréd Rényi撰写的研究<font color="#ff8000">随机图 random graphs</font>的著名论文的帮助下，概率网络理论得以发展。<font color="#ff8000">埃尔德什-雷尼模型 Erdős–Rényi model</font>(ER模型)假定一个图由n个有标记的节点组成，其中每一对节点通过一个预设的概率p连接。
 
−
 
 
−
 
 
−
 
 
−
[[Image:Watts strogatz.svg|thumb|Watts–Strogatz graph]]
 
−
 
 
−
Watts–Strogatz graph
 
−
 
 
−
瓦茨-斯托加茨图
 
−
 
 
−
While the ER model's simplicity has helped it find many applications, it does not accurately describe many real world networks. The ER model fails to generate local clustering and [[triadic closure]]s as often as they are found in real world networks.  Therefore, the [[Watts and Strogatz model]] was proposed, whereby a network is constructed as a regular ring lattice, and then nodes are rewired according to some probability '''β'''.
 
−
 
 
−
While the ER model's simplicity has helped it find many applications, it does not accurately describe many real world networks. The ER model fails to generate local clustering and triadic closures as often as they are found in real world networks.  Therefore, the Watts and Strogatz model was proposed, whereby a network is constructed as a regular ring lattice, and then nodes are rewired according to some probability β.
 
−
 
 
−
尽管ER模型的简单性帮助它找到了许多应用之处，但它并不能准确地描述许多真实世界的网络。ER模型无法像在现实世界网络中那样频繁地生成局部聚类和三元闭包。为此，提出了<font color="#ff8000">瓦茨-斯托加茨模型 Watts-Strogatz model</font>，将网络构造成规则的环网格，然后根据一定的概率β重新连接节点。<ref name=WS>{{cite journal  | author1 = Watts, D.J. | author2 = Strogatz, S.H. | year = 1998 | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 409–10  | doi = 10.1038/30918 | pmid = 9623998 | bibcode=1998Natur.393..440W}}</ref>
 
−
 
 
−
This produces a locally clustered network and dramatically reduces the [[average path length]], creating networks which represent the [[Small-world networks|small world phenomenon]] observed in many real world networks.
 
−
 
 
−
This produces a locally clustered network and dramatically reduces the average path length, creating networks which represent the small world phenomenon observed in many real world networks.
 
−
 
 
−
这会产生一个局部聚集的网络，并显著减少<font color="#ff8000">平均路径长度 average path length</font>。这样创建的网络可以代表在许多现实世界网络中观察到的<font color="#ff8000">小世界现象 small world phenomenon</font>。<ref name=milg>{{cite journal |author1=Travers Jeffrey |author2=Milgram Stanley | year = 1969 | title = An Experimental Study of the Small World Problem | url = | journal = Sociometry | volume = 32 | issue = 4| pages = 425–443 | doi=10.2307/2786545|jstor=2786545 }}</ref>
 
−
 
 
−
Despite this achievement, both the ER and the Watts and Storgatz models fail to account for the formulation of hubs as observed in many real world networks. The degree distribution in the ER model follows a [[Poisson distribution]], while the Watts and Strogatz model produces graphs that are [[homogeneous]] in [[degree distribution|degree]]. Many networks are instead scale free, meaning that their degree distribution follows a [[power law]] of the form:
 
−
 
 
−
Despite this achievement, both the ER and the Watts and Storgatz models fail to account for the formulation of hubs as observed in many real world networks. The degree distribution in the ER model follows a Poisson distribution, while the Watts and Strogatz model produces graphs that are homogeneous in degree. Many networks are instead scale free, meaning that their degree distribution follows a power law of the form:
 
−
 
 
−
尽管取得了这样的成就，ER模型和Watts-Storgatz模型都未能解释在许多现实世界网络中观察到的中心节点的形成。ER模型中的度分布遵循<font color="#ff8000">泊松分布</font>，而Watts-Strogatz模型生成的图在<font color="#ff8000">度</font>上是<font color="#ff8000">同质的</font>。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的<font color="#ff8000">幂律分布</font>:
 
  
 +
这会产生一个局部聚集的网络，并显著减少平均路径长度 average path length。这样创建的网络可以代表在许多现实世界网络中观察到的小世界现象 small world phenomenon。<ref name=milg>{{cite journal |author1=Travers Jeffrey |author2=Milgram Stanley | year = 1969 | title = An Experimental Study of the Small World Problem | url = | journal = Sociometry | volume = 32 | issue = 4| pages = 425–443 | doi=10.2307/2786545|jstor=2786545 }}</ref>
  
 +
尽管取得了这样的成就，ER模型和Watts-Storgatz模型都未能解释在许多现实世界网络中观察到的中心节点的形成。ER模型中的度分布遵循泊松分布，而Watts-Strogatz模型生成的图在度上是同质的。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的幂律分布:
  
 
: <math>P(k)\sim k^{-\gamma}</math>
 
: <math>P(k)\sim k^{-\gamma}</math>
−
 
−
<math>P(k)\sim k^{-\gamma}</math>
 
−
 
−
数学 p (k) sim k ^ {- gamma } / math
 
−
 
−
This exponent turns out to be approximately 3 for many real world networks, however, it is not a universal constant and depends continuously on the network's parameters
 
−
 
−
This exponent turns out to be approximately 3 for many real world networks, however, it is not a universal constant and depends continuously on the network's parameters
 
  
 
对于许多现实世界的网络来说，这个指数大约是3。然而，它不是一个通用常数，并且持续地依赖于网络的参数。<ref name=Barabasi2000>{{Cite journal| url = http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf  | author1 = R. Albert | author2 = A.-L. Barabási | title = Topology of Evolving Networks: Local Events and Universality | journal = [[Physical Review Letters]] | volume = 85 | issue = 24 | pages = 5234–5237 | year = 2000 | doi = 10.1103/PhysRevLett.85.5234 | pmid = 11102229|arxiv = cond-mat/0005085 |bibcode = 2000PhRvL..85.5234A | hdl = 2047/d20000695 }}</ref>
 
对于许多现实世界的网络来说，这个指数大约是3。然而，它不是一个通用常数，并且持续地依赖于网络的参数。<ref name=Barabasi2000>{{Cite journal| url = http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf  | author1 = R. Albert | author2 = A.-L. Barabási | title = Topology of Evolving Networks: Local Events and Universality | journal = [[Physical Review Letters]] | volume = 85 | issue = 24 | pages = 5234–5237 | year = 2000 | doi = 10.1103/PhysRevLett.85.5234 | pmid = 11102229|arxiv = cond-mat/0005085 |bibcode = 2000PhRvL..85.5234A | hdl = 2047/d20000695 }}</ref>
  
−
==First evolving network model – scale-free networks 第一个演化网络模型——无标度网络==
+
==第一个演化网络模型——无标度网络==
−
 
 
−
{{Main| Barabási–Albert model }}
 
−
 
 
−
The Barabási–Albert (BA) model was the first widely accepted model to produce [[scale-free network]]s. This was accomplished by incorporating [[preferential attachment]] and growth, where nodes are added to the network over time and are more likely to link to other nodes with high degree distributions. The BA model was first applied to degree distributions on the web, where both of these effects can be clearly seen. New web pages are added over time, and each new page is more likely to link to highly visible hubs like [[Google]] which have high degree distributions than to nodes with only a few links. Formally this preferential attachment is:
 
−
 
 
−
The Barabási–Albert (BA) model was the first widely accepted model to produce scale-free networks. This was accomplished by incorporating preferential attachment and growth, where nodes are added to the network over time and are more likely to link to other nodes with high degree distributions. The BA model was first applied to degree distributions on the web, where both of these effects can be clearly seen. New web pages are added over time, and each new page is more likely to link to highly visible hubs like Google which have high degree distributions than to nodes with only a few links. Formally this preferential attachment is:
 
−
 
 
−
巴拉巴西-阿尔伯特模型 Barabási–Albert model(BA模型)是第一个被广泛接受的产生<font color="#ff8000">无标度网络 scale-free network</font>的模型。这是通过<font color="#ff8000">偏好依附 preferential attachment</font>和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。BA模型首先应用于互联网的度分布，这两种影响都可以清楚地看到。随着时间的推移，新的网页会不断增加，并且每个新的网页都更有可能链接到像谷歌这样具有很高的度分布的高度可见的中心节点，而不是只有少量链接的节点。从形式上来说，这种偏好依附是:
 
−
 
 
  
 +
巴拉巴西-阿尔伯特模型 Barabási–Albert model(BA模型)是第一个被广泛接受的产生无标度网络 scale-free network的模型。这是通过偏好依附 preferential attachment和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。BA模型首先应用于互联网的度分布，这两种影响都可以清楚地看到。随着时间的推移，新的网页会不断增加，并且每个新的网页都更有可能链接到像谷歌这样具有很高的度分布的高度可见的中心节点，而不是只有少量链接的节点。从形式上来说，这种偏好依附是:
  
 
: <math>p_i = \frac{k_i}{\displaystyle\sum_j k_j},</math>
 
: <math>p_i = \frac{k_i}{\displaystyle\sum_j k_j},</math>
  
−
<math>p_i = \frac{k_i}{\displaystyle\sum_j k_j},</math>
+
==BA模型以外=  
−
 
 
−
数学，数学，数学
 
−
 
 
−
==Additions to BA model= BA模型以外=
 
−
 
 
−
The BA model was the first model to derive the network topology from the way the network was constructed with nodes and links being added over time. However, the model makes only the simplest assumptions necessary for a scale-free network to emerge, namely that there is linear growth and linear preferential attachment. This minimal model does not capture variations in the shape of the degree distribution, variations in the degree exponent, or the size independent [[clustering coefficient]].
 
−
 
 
−
The BA model was the first model to derive the network topology from the way the network was constructed with nodes and links being added over time. However, the model makes only the simplest assumptions necessary for a scale-free network to emerge, namely that there is linear growth and linear preferential attachment. This minimal model does not capture variations in the shape of the degree distribution, variations in the degree exponent, or the size independent clustering coefficient.
 
−
 
 
−
BA模型是第一个从随着时间的推移而添加节点和连边的网络构造方式中推导出网络拓扑的模型。然而，该模型只做了产生无标度网络所必需的最简单的假设，即存在线性增长和线性偏好依附。这个最小模型没有刻画度分布形状的变化，度指数的变化，或不依赖大小的<font color="#ff8000">集聚系数 clustering coefficient</font>。
 
−
 
 
−
Therefore, the original model has since been modified{{by whom?|date=June 2016}} to more fully capture the properties of evolving networks by introducing a few new properties.
 
  
−
Therefore, the original model has since been modified to more fully capture the properties of evolving networks by introducing a few new properties.
+
BA模型是第一个从随着时间的推移而添加节点和连边的网络构造方式中推导出网络拓扑的模型。然而，该模型只做了产生无标度网络所必需的最简单的假设，即存在线性增长和线性偏好依附。这个最小模型没有刻画度分布形状的变化，度指数的变化，或不依赖大小的集聚系数 clustering coefficient。
  
 
因此，通过引入一些新的性质，对原有的模型进行了修改，以更充分地刻画演化网络的性质。
 
因此，通过引入一些新的性质，对原有的模型进行了修改，以更充分地刻画演化网络的性质。
  
−
===Fitness 适应度===
+
===适应度 Fitness===
−
 
 
−
{{Main|Fitness model (network theory)}}
 
−
 
 
−
One concern with the BA model is that the degree distributions of each nodes experience strong [[positive feedback]] whereby the earliest nodes with high degree distributions continue to dominate the network indefinitely. However, this can be alleviated by introducing a fitness for each node, which modifies the probability of new links being created with that node or even of links to that node being removed.
 
  
−
One concern with the BA model is that the degree distributions of each nodes experience strong positive feedback whereby the earliest nodes with high degree distributions continue to dominate the network indefinitely. However, this can be alleviated by introducing a fitness for each node, which modifies the probability of new links being created with that node or even of links to that node being removed.
+
与BA模型有关的一个问题是，每个节点的度分布经历很强的正反馈 positive feedback，即最早的具有高度分布的节点继续无限期地主宰网络。但是，可以通过为每个节点引入一个适应度来缓解这个问题，该适应度可以修改用该节点创建新链接的概率，甚至可以修改该节点的链接被删除的概率。<ref>Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", ''Reviews of Modern Physics'' 74, 47 (2002)</ref>
−
 
 
−
与BA模型有关的一个问题是，每个节点的度分布经历很强的<font color="#ff8000">正反馈 positive feedback</font>，即最早的具有高度分布的节点继续无限期地主宰网络。但是，可以通过为每个节点引入一个适应度来缓解这个问题，该适应度可以修改用该节点创建新链接的概率，甚至可以修改该节点的链接被删除的概率。<ref>Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", ''Reviews of Modern Physics'' 74, 47 (2002)</ref>
 
−
 
 
−
In order to preserve the preferential attachment from the BA model, this fitness is then multiplied by the preferential attachment based on degree distribution to give the true probability that a link is created which connects to node ''i''.
 
−
 
 
−
In order to preserve the preferential attachment from the BA model, this fitness is then multiplied by the preferential attachment based on degree distribution to give the true probability that a link is created which connects to node i.
 
  
 
为了保持BA模型中的偏好依附，该适应度乘以基于度分布的偏好依附，得到连接到节点i的真实概率。
 
为了保持BA模型中的偏好依附，该适应度乘以基于度分布的偏好依附，得到连接到节点i的真实概率。
−
 
−
 
  
 
: <math>\Pi(k_i) = \frac{\eta_i k_i}{\displaystyle\sum_j \eta_j k_j},</math>
 
: <math>\Pi(k_i) = \frac{\eta_i k_i}{\displaystyle\sum_j \eta_j k_j},</math>
−
 
−
<math>\Pi(k_i) = \frac{\eta_i k_i}{\displaystyle\sum_j \eta_j k_j},</math>
 
−
 
−
数学 Pi (ki) frac { eta i } displaystyle  sum j  eta j j } ，/ math
 
−
 
−
 
−
 
−
Where <math>\eta</math> is the fitness, which may also depend on time. A decay of fitness with respect to time may occur and can be formalized by
 
−
 
−
Where <math>\eta</math> is the fitness, which may also depend on time. A decay of fitness with respect to time may occur and can be formalized by
 
  
 
其中<math>\eta</math>是适应度，这也可能依赖于时间。适应度可能随时间衰减，可以表示为
 
其中<math>\eta</math>是适应度，这也可能依赖于时间。适应度可能随时间衰减，可以表示为
−
 
−
 
  
 
: <math> \Pi(k_i) \propto k_i(t-t_i)^{-\nu},</math>
 
: <math> \Pi(k_i) \propto k_i(t-t_i)^{-\nu},</math>
−
 
−
<math> \Pi(k_i) \propto k_i(t-t_i)^{-\nu},</math>
 
−
 
−
Math  Pi (ki) propto ki (t-t i) ^ {- nu } ，/ math
 
−
 
−
 
−
 
−
where <math>\gamma</math> increases with <math>\nu.</math>
 
−
 
−
where <math>\gamma</math> increases with <math>\nu.</math>
 
  
 
其中<math>\gamma</math>随<math>\nu.</math>的增长而增长。
 
其中<math>\gamma</math>随<math>\nu.</math>的增长而增长。
第145行： 第49行：
  
  
−
===Removing nodes and rewiring links 删除节点和重连接边===
+
===删除节点和重连接边===
−
 
 
−
Further complications arise because nodes may be removed from the network with some probability. Additionally, existing links may be destroyed and new links between existing nodes may be created. The probability of these actions occurring may depend on time and may also be related to the node's fitness. Probabilities can be assigned to these events by studying the characteristics of the network in question in order to grow a model network with identical properties. This growth would take place with one of the following actions occurring at each time step:
 
−
 
 
−
Further complications arise because nodes may be removed from the network with some probability. Additionally, existing links may be destroyed and new links between existing nodes may be created. The probability of these actions occurring may depend on time and may also be related to the node's fitness. Probabilities can be assigned to these events by studying the characteristics of the network in question in order to grow a model network with identical properties. This growth would take place with one of the following actions occurring at each time step:
 
  
 
由于节点可能会以一定的概率从网络中移除，因此会出现更多的复杂情况。此外，节点之间现有的链接可能会被删除并且创建新的链接。这些行为发生的概率可能依赖于时间，也可能与节点的适应度有关。通过研究有关网络的特性，可以为这些事件赋予概率，从而生成具有相同特性的模型网络。这种增长将在每个时间步骤中发生下列行为之一:
 
由于节点可能会以一定的概率从网络中移除，因此会出现更多的复杂情况。此外，节点之间现有的链接可能会被删除并且创建新的链接。这些行为发生的概率可能依赖于时间，也可能与节点的适应度有关。通过研究有关网络的特性，可以为这些事件赋予概率，从而生成具有相同特性的模型网络。这种增长将在每个时间步骤中发生下列行为之一:
−
 
−
 
−
 
−
Prob p: add an internal link.
 
−
 
−
Prob p: add an internal link.
 
  
 
概率 p：增加一个内部链接。
 
概率 p：增加一个内部链接。
−
 
−
 
−
 
−
Prob q: delete a link.
 
−
 
−
Prob q: delete a link.
 
  
 
概率 q: 删除一个链接。
 
概率 q: 删除一个链接。
−
 
−
 
−
 
−
Prob r: delete a node.
 
−
 
−
Prob r: delete a node.
 
  
 
概率 r：删除一个节点。
 
概率 r：删除一个节点。
−
 
−
 
−
 
−
Prob 1-p-q-r: add a node.
 
−
 
−
Prob 1-p-q-r: add a node.
 
  
 
概率 1-p-q-r: 添加一个节点。
 
概率 1-p-q-r: 添加一个节点。
  
−
==Other ways of characterizing evolving networks 描述演化网络的其他方法==
+
==描述演化网络的其他方法==
−
 
 
−
In addition to growing network models as described above, there may be times when other methods are more useful or convenient for characterizing certain properties of evolving networks.
 
−
 
 
−
In addition to growing network models as described above, there may be times when other methods are more useful or convenient for characterizing certain properties of evolving networks.
 
  
 
除了上面描述的不断生长的网络模型之外，可能有时候其他方法对于描述演化网络的某些性质更有用或更方便。
 
除了上面描述的不断生长的网络模型之外，可能有时候其他方法对于描述演化网络的某些性质更有用或更方便。
  
−
 
+
===趋向均衡===
−
 
 
−
===Convergence towards equilibria 趋向均衡===
 
−
 
 
−
In networked systems where competitive decision making takes place, game theory is often used to model system dynamics, and convergence towards equilibria can be considered as a driver of topological evolution. For example,  Kasthurirathna and Piraveenan  have shown that when individuals in a system display varying levels of rationality, improving the overall system rationality might be an evolutionary reason for the emergence of scale-free networks. They demonstrated this by applying evolutionary pressure on an initially random network which simulates a range of classic games, so that the network converges towards Nash equilibria while being allowed to re-wire. The networks become increasingly scale-free during this process.
 
−
 
 
−
In networked systems where competitive decision making takes place, game theory is often used to model system dynamics, and convergence towards equilibria can be considered as a driver of topological evolution. For example,  Kasthurirathna and Piraveenan have shown that when individuals in a system display varying levels of rationality, improving the overall system rationality might be an evolutionary reason for the emergence of scale-free networks. They demonstrated this by applying evolutionary pressure on an initially random network which simulates a range of classic games, so that the network converges towards Nash equilibria while being allowed to re-wire. The networks become increasingly scale-free during this process.
 
−
 
 
  
 
在竞争性决策发生的网络系统中，博弈论经常被用来建模系统动力学，趋向均衡可以被认为是拓扑进化的驱动力。例如Kasthurirathna和Piraveenan<ref>{{cite journal |last1=Kasthurirathna|first1=Dharshana  |last2=Piraveenan |first2=Mahendra. |title=Emergence of scale-free characteristics in socioecological systems with bounded rationality |journal=[[Scientific Reports (journal)|Scientific Reports]] |volume=In Press |date=2015}}</ref>表明，当一个系统中的个体表现出不同程度的理性时，提高整个系统的理性可能是无标度网络出现的进化原因。他们通过对一个最初的随机网络施加进化压力来模拟一系列经典博弈，当允许重新连接时，网络收敛到纳什均衡，从而证明了这一点。在这个过程中，网络变得越来越无标度。
 
在竞争性决策发生的网络系统中，博弈论经常被用来建模系统动力学，趋向均衡可以被认为是拓扑进化的驱动力。例如Kasthurirathna和Piraveenan<ref>{{cite journal |last1=Kasthurirathna|first1=Dharshana  |last2=Piraveenan |first2=Mahendra. |title=Emergence of scale-free characteristics in socioecological systems with bounded rationality |journal=[[Scientific Reports (journal)|Scientific Reports]] |volume=In Press |date=2015}}</ref>表明，当一个系统中的个体表现出不同程度的理性时，提高整个系统的理性可能是无标度网络出现的进化原因。他们通过对一个最初的随机网络施加进化压力来模拟一系列经典博弈，当允许重新连接时，网络收敛到纳什均衡，从而证明了这一点。在这个过程中，网络变得越来越无标度。
  
−
===Treat evolving networks as successive snapshots of a static network 视演化网络为连续的静态网络快照===
+
===视演化网络为连续的静态网络快照===
−
 
 
−
The most common way to view evolving networks is by considering them as successive static networks. This could be conceptualized as the individual still images which compose a [[video|motion picture]]. Many simple parameters exist to describe a static network (number of nodes, edges, path length, connected components), or to describe specific nodes in the graph such as the number of links or the clustering coefficient. These properties can then individually be studied as a time series using signal processing notions. For example, we can track the number of links established to a server per minute by looking at the successive snapshots of the network and counting these links in each snapshot.
 
−
 
 
−
The most common way to view evolving networks is by considering them as successive static networks. This could be conceptualized as the individual still images which compose a motion picture. Many simple parameters exist to describe a static network (number of nodes, edges, path length, connected components), or to describe specific nodes in the graph such as the number of links or the clustering coefficient. These properties can then individually be studied as a time series using signal processing notions. For example, we can track the number of links established to a server per minute by looking at the successive snapshots of the network and counting these links in each snapshot.
 
  
 
观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为组成电影的一个个静态图像。有许多简单的参数可以描述一个静态网络（节点数、边、路径长度、连通子图），或者描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性单独作为时间序列进行研究。<ref name=EvolvingNetworksPDF>{{Cite journal| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf | author1 = Pierre Borgnat | author2 = Eric Fleury | title = Evolving Networks|display-authors=etal}}</ref> 例如，我们可以通过查看网络的连续快照并计算每个快照中的链接数量，来跟踪每分钟建立到服务器的链接数量。
 
观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为组成电影的一个个静态图像。有许多简单的参数可以描述一个静态网络（节点数、边、路径长度、连通子图），或者描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性单独作为时间序列进行研究。<ref name=EvolvingNetworksPDF>{{Cite journal| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf | author1 = Pierre Borgnat | author2 = Eric Fleury | title = Evolving Networks|display-authors=etal}}</ref> 例如，我们可以通过查看网络的连续快照并计算每个快照中的链接数量，来跟踪每分钟建立到服务器的链接数量。
−
 
−
Unfortunately, the analogy of snapshots to a motion picture also reveals the main difficulty with this approach: the time steps employed are very rarely suggested by the network and are instead arbitrary. Using extremely small time steps between each snapshot preserves resolution, but may actually obscure wider trends which only become visible over longer timescales. Conversely, using larger timescales loses the temporal order of events within each snapshot. Therefore, it may be difficult to find the appropriate timescale for dividing the evolution of a network into static snapshots.
 
−
 
−
Unfortunately, the analogy of snapshots to a motion picture also reveals the main difficulty with this approach: the time steps employed are very rarely suggested by the network and are instead arbitrary. Using extremely small time steps between each snapshot preserves resolution, but may actually obscure wider trends which only become visible over longer timescales. Conversely, using larger timescales loses the temporal order of events within each snapshot. Therefore, it may be difficult to find the appropriate timescale for dividing the evolution of a network into static snapshots.
 
  
 
不幸的是，快照与电影的类比也揭示了这种方法的主要困难: 使用的时间步骤很少由网络给出，而是任意的。在每个快照之间使用极小的时间步骤可以保持分辨率，但实际上可能掩盖了只有在较长时间尺度下才能看到的更广泛的趋势。相反，使用较大的时间尺度会失去每个快照中事件的时间顺序。因此，可能很难找到合适的时间尺度来将网络的演化划分为静态快照。
 
不幸的是，快照与电影的类比也揭示了这种方法的主要困难: 使用的时间步骤很少由网络给出，而是任意的。在每个快照之间使用极小的时间步骤可以保持分辨率，但实际上可能掩盖了只有在较长时间尺度下才能看到的更广泛的趋势。相反，使用较大的时间尺度会失去每个快照中事件的时间顺序。因此，可能很难找到合适的时间尺度来将网络的演化划分为静态快照。
  
−
===Define dynamic properties 定义动力学性质===
+
===定义动力学性质===
−
 
 
−
It may be important to look at properties which cannot be directly observed by treating evolving networks as a sequence of snapshots, such as the duration of contacts between nodes. Other similar properties can be defined and then it is possible to instead track these properties through the evolution of a network and visualize them directly.
 
−
 
 
−
It may be important to look at properties which cannot be directly observed by treating evolving networks as a sequence of snapshots, such as the duration of contacts between nodes. Other similar properties can be defined and then it is possible to instead track these properties through the evolution of a network and visualize them directly.
 
  
 
那些不能直接从将演化网络视为一系列快照中观察到的特性可能很重要，例如节点之间的接触时间。<ref name="Impact of human mobility on the design of opportunistic forwarding algorithms">{{Cite journal| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf | author1 = A. Chaintreau | author2 =  P. Hui | author3 =  J. Crowcroft | author4 =  C. Diot | author5 =  R. Gass | author6 =  J. Scott | journal =  Infocom | year =  2006 | title =  Impact of human mobility on the design of opportunistic forwarding algorithms}}</ref>可以定义其他类似的属性，然后可以通过网络的演化来跟踪这些属性，并直接可视化它们。
 
那些不能直接从将演化网络视为一系列快照中观察到的特性可能很重要，例如节点之间的接触时间。<ref name="Impact of human mobility on the design of opportunistic forwarding algorithms">{{Cite journal| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf | author1 = A. Chaintreau | author2 =  P. Hui | author3 =  J. Crowcroft | author4 =  C. Diot | author5 =  R. Gass | author6 =  J. Scott | journal =  Infocom | year =  2006 | title =  Impact of human mobility on the design of opportunistic forwarding algorithms}}</ref>可以定义其他类似的属性，然后可以通过网络的演化来跟踪这些属性，并直接可视化它们。
−
 
−
Another issue with using successive snapshots is that only slight changes in network topology can have large effects on the outcome of algorithms designed to find communities. Therefore, it is necessary to use a non classical definition of communities which permits following the evolution of the community through a set of rules such as birth, death, merge, split, growth, and contraction.
 
−
 
−
Another issue with using successive snapshots is that only slight changes in network topology can have large effects on the outcome of algorithms designed to find communities. Therefore, it is necessary to use a non classical definition of communities which permits following the evolution of the community through a set of rules such as birth, death, merge, split, growth, and contraction.
 
  
 
使用连续快照的另一个问题是，在网络拓扑中微小的变化可以对用于寻找网络社团的算法的结果产生巨大的影响。因此，有必要使用一个非经典的社团定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，来跟随社团的演化。<ref name="Quantifying social group evolution">{{Cite journal| author1 = G. Palla | author2 = A. Barabasi | author3 = T. Vicsek | title =  Quantifying social group evolution | journal = Nature | volume =  446 | pages =  664–667 | year =  2007 | author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng | issue=7136 | doi=10.1038/nature05670|pmid = 17410175|arxiv = 0704.0744 |bibcode = 2007Natur.446..664P }}</ref><ref name="Structural and temporal analysis of the blogosphere through community factorization">{{Cite book| url = http://portal.acm.org/ft_gateway.cfm? | author1 = Y. Chi, S. Zhuid=1281213&type=pdf | author2 =  X. Song | author3 =  J. Tatemura | author4 =  B.L. Tseng | title =  Structural and temporal analysis of the blogosphere through community factorization | journal =  KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining | pages = 163–172 | year =  2007| doi = 10.1145/1281192.1281213 | citeseerx = 10.1.1.69.6959 | isbn = 9781595936097 }}</ref>
 
使用连续快照的另一个问题是，在网络拓扑中微小的变化可以对用于寻找网络社团的算法的结果产生巨大的影响。因此，有必要使用一个非经典的社团定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，来跟随社团的演化。<ref name="Quantifying social group evolution">{{Cite journal| author1 = G. Palla | author2 = A. Barabasi | author3 = T. Vicsek | title =  Quantifying social group evolution | journal = Nature | volume =  446 | pages =  664–667 | year =  2007 | author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng | issue=7136 | doi=10.1038/nature05670|pmid = 17410175|arxiv = 0704.0744 |bibcode = 2007Natur.446..664P }}</ref><ref name="Structural and temporal analysis of the blogosphere through community factorization">{{Cite book| url = http://portal.acm.org/ft_gateway.cfm? | author1 = Y. Chi, S. Zhuid=1281213&type=pdf | author2 =  X. Song | author3 =  J. Tatemura | author4 =  B.L. Tseng | title =  Structural and temporal analysis of the blogosphere through community factorization | journal =  KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining | pages = 163–172 | year =  2007| doi = 10.1145/1281192.1281213 | citeseerx = 10.1.1.69.6959 | isbn = 9781595936097 }}</ref>
  
−
==Applications 应用==
+
==应用==
−
 
+
[[File:256px-World-airline-routemap-2009.png|256px|2009年世界预定商业航空交通路线图。这个网络随着新路线的计划或取消而不断演变]]
−
[[Image:World-airline-routemap-2009.png|thumb|256px|right|Route map of the world's scheduled commercial airline traffic, 2009. This network evolves continuously as new routes are scheduled or cancelled.]]
 
−
 
 
−
Route map of the world's scheduled commercial airline traffic, 2009. This network evolves continuously as new routes are scheduled or cancelled.
 
−
 
 
−
2009年世界预定商业航空交通路线图。这个网络随着新路线的计划或取消而不断演变。
 
−
 
 
−
Almost all real world networks are evolving networks since they are constructed over time. By varying the respective probabilities described above, it is possible to use the expanded BA model to construct a network with nearly identical properties as many observed networks.
 
−
 
 
−
Almost all real world networks are evolving networks since they are constructed over time. By varying the respective probabilities described above, it is possible to use the expanded BA model to construct a network with nearly identical properties as many observed networks.
 
  
 
几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变上述各自的概率，可以使用扩展的BA模型来构造一个具有与许多观测网络几乎相同属性的网络。<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal |url            = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf |author1        = I. Farkas |author2        = I. Derenyi |author3        = H. Heong |title          = Networks in life: scaling properties and eigenvalue spectra |journal        = [[Physica A|Physica]] |volume          = 314 |issue          = 1–4 |pages          = 25–34 |year            = 2002 |arxiv          = cond-mat/0303106 |bibcode        = 2002PhyA..314...25F |doi            = 10.1016/S0378-4371(02)01181-0 |display-authors = etal |access-date    = 2011-04-21 |archive-url    = https://web.archive.org/web/20111004050804/http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf |archive-date    = 2011-10-04 |url-status      = dead}}</ref>
 
几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变上述各自的概率，可以使用扩展的BA模型来构造一个具有与许多观测网络几乎相同属性的网络。<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal |url            = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf |author1        = I. Farkas |author2        = I. Derenyi |author3        = H. Heong |title          = Networks in life: scaling properties and eigenvalue spectra |journal        = [[Physica A|Physica]] |volume          = 314 |issue          = 1–4 |pages          = 25–34 |year            = 2002 |arxiv          = cond-mat/0303106 |bibcode        = 2002PhyA..314...25F |doi            = 10.1016/S0378-4371(02)01181-0 |display-authors = etal |access-date    = 2011-04-21 |archive-url    = https://web.archive.org/web/20111004050804/http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf |archive-date    = 2011-10-04 |url-status      = dead}}</ref>
−
 
−
Moreover, the concept of scale free networks shows us that time evolution is a necessary part of understanding the network's properties, and that it is difficult to model an existing network as having been created instantaneously. Real evolving networks which are currently being studied include [[social networks]], [[telecommunications network|communications networks]], the [[internet]], the [[Six Degrees of Kevin Bacon|movie actor network]], the [[world wide web]], and [[Transport network|transportation network]]s.
 
−
 
−
Moreover, the concept of scale free networks shows us that time evolution is a necessary part of understanding the network's properties, and that it is difficult to model an existing network as having been created instantaneously. Real evolving networks which are currently being studied include social networks, communications networks, the internet, the movie actor network, the world wide web, and transportation networks.
 
  
 
此外，无标度网络的概念告诉我们，时间演化是理解网络属性的必要组成部分，而且很难将现有网络模型化为瞬间创建的。目前正在研究的演化网络包括社交网络、通信网络、互联网、电影演员网络、万维网和交通网络。
 
此外，无标度网络的概念告诉我们，时间演化是理解网络属性的必要组成部分，而且很难将现有网络模型化为瞬间创建的。目前正在研究的演化网络包括社交网络、通信网络、互联网、电影演员网络、万维网和交通网络。
  
−
==Further reading 扩展阅读==
+
==扩展阅读==
  
 
* "Understanding Network Science," https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
 
* "Understanding Network Science," https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
  
 
* "Linked: The New Science of Networks", A.-L. Barabási Perseus Publishing, Cambridge.
 
* "Linked: The New Science of Networks", A.-L. Barabási Perseus Publishing, Cambridge.
−
 
−
* "理解网络科学" https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
 
−
 
−
* "链接：网络新科学", A.-L. Barabási Perseus Publishing, Cambridge.
 
  
 
==References==
 
==References==
第266行： 第98行：
 
<references />
 
<references />
  
 +
----
 +
本中文词条由[[用户:Steve Luo|Steve Luo]]审校，[[用户:打豆豆|打豆豆]]，欢迎在讨论页面留言。
  
 +
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
  
−
{{DEFAULTSORT:Evolving Networks}}
+
[[Category:网络]]
−
 
+
[[Category:网络理论]]
−
[[Category:Networks]]
 
−
 
 
−
Category:Networks
 
−
 
 
−
类别: 网络
 
−
 
 
−
[[Category:Network theory]]
 
−
 
 
−
Category:Network theory
 
−
 
 
−
范畴: 网络理论
 
−
 
 
−
<noinclude>
 
−
 
 
−
<small>This page was moved from [[wikipedia:en:Evolving network]]. Its edit history can be viewed at [[网络演化/edithistory]]</small></noinclude>
 
−
 
 
−
[[Category:待整理页面]]
 

2020年12月13日 (日) 15:15的版本

此词条暂由彩云小译翻译，已由Steve Luo审校。

基于初始巴拉巴西-阿尔伯特 Barabasi-Albert 模型的演化网络的动画

演化网络 Evolving networks是作为时间的函数而变化的网络。它们是网络科学 network science的自然延伸，因为几乎所有现实世界的网络都是随时间演化的，通过随着时间的推移增加或删除节点或连边实现。通常所有这些过程都是同时发生的，比如在社交网络 social networks中，随着时间的推移人们结交和失去朋友，从而创造和破坏连边，一些人成为新的社交网络的一部分，或者离开他们的网络，从而改变网络中的节点。演化网络的概念建立在既定的网络理论之上，现在正被引入到许多不同领域的网络研究中。

网络理论背景

网络研究源于图论 graph theory的发展，莱昂哈德·欧拉 Leonhard Euler于1736年首先分析了图论，当时他撰写了著名的柯尼斯堡七桥问题 Seven Bridges of Königsberg论文。随后在八篇由保罗·埃尔德什 Paul Erdős和阿尔弗雷德·雷尼 Alfréd Rényi撰写的研究随机图 random graphs的著名论文的帮助下，概率网络理论得以发展。埃尔德什-雷尼模型 Erdős–Rényi model(ER模型)假定一个图由n个有标记的节点组成，其中每一对节点通过一个预设的概率p连接。

Watts–Strogatz graph 瓦茨-斯托加茨图

尽管ER模型的简单性帮助它找到了许多应用之处，但它并不能准确地描述许多真实世界的网络。ER模型无法像在现实世界网络中那样频繁地生成局部聚类和三元闭包。为此，提出了瓦茨-斯托加茨模型 Watts-Strogatz model，将网络构造成规则的环网格，然后根据一定的概率β重新连接节点。[1]

这会产生一个局部聚集的网络，并显著减少平均路径长度 average path length。这样创建的网络可以代表在许多现实世界网络中观察到的小世界现象 small world phenomenon。[2]

尽管取得了这样的成就，ER模型和Watts-Storgatz模型都未能解释在许多现实世界网络中观察到的中心节点的形成。ER模型中的度分布遵循泊松分布，而Watts-Strogatz模型生成的图在度上是同质的。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的幂律分布:

[math]\displaystyle{ P(k)\sim k^{-\gamma} }[/math]

对于许多现实世界的网络来说，这个指数大约是3。然而，它不是一个通用常数，并且持续地依赖于网络的参数。[3]

第一个演化网络模型——无标度网络

巴拉巴西-阿尔伯特模型 Barabási–Albert model(BA模型)是第一个被广泛接受的产生无标度网络 scale-free network的模型。这是通过偏好依附 preferential attachment和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。BA模型首先应用于互联网的度分布，这两种影响都可以清楚地看到。随着时间的推移，新的网页会不断增加，并且每个新的网页都更有可能链接到像谷歌这样具有很高的度分布的高度可见的中心节点，而不是只有少量链接的节点。从形式上来说，这种偏好依附是:

[math]\displaystyle{ p_i = \frac{k_i}{\displaystyle\sum_j k_j}, }[/math]

=BA模型以外

BA模型是第一个从随着时间的推移而添加节点和连边的网络构造方式中推导出网络拓扑的模型。然而，该模型只做了产生无标度网络所必需的最简单的假设，即存在线性增长和线性偏好依附。这个最小模型没有刻画度分布形状的变化，度指数的变化，或不依赖大小的集聚系数 clustering coefficient。

因此，通过引入一些新的性质，对原有的模型进行了修改，以更充分地刻画演化网络的性质。

适应度 Fitness

与BA模型有关的一个问题是，每个节点的度分布经历很强的正反馈 positive feedback，即最早的具有高度分布的节点继续无限期地主宰网络。但是，可以通过为每个节点引入一个适应度来缓解这个问题，该适应度可以修改用该节点创建新链接的概率，甚至可以修改该节点的链接被删除的概率。[4]

为了保持BA模型中的偏好依附，该适应度乘以基于度分布的偏好依附，得到连接到节点i的真实概率。

[math]\displaystyle{ \Pi(k_i) = \frac{\eta_i k_i}{\displaystyle\sum_j \eta_j k_j}, }[/math]

其中[math]\displaystyle{ \eta }[/math]是适应度，这也可能依赖于时间。适应度可能随时间衰减，可以表示为

[math]\displaystyle{ \Pi(k_i) \propto k_i(t-t_i)^{-\nu}, }[/math]

其中[math]\displaystyle{ \gamma }[/math]随[math]\displaystyle{ \nu. }[/math]的增长而增长。


删除节点和重连接边

由于节点可能会以一定的概率从网络中移除，因此会出现更多的复杂情况。此外，节点之间现有的链接可能会被删除并且创建新的链接。这些行为发生的概率可能依赖于时间，也可能与节点的适应度有关。通过研究有关网络的特性，可以为这些事件赋予概率，从而生成具有相同特性的模型网络。这种增长将在每个时间步骤中发生下列行为之一:

概率 p：增加一个内部链接。

概率 q: 删除一个链接。

概率 r：删除一个节点。

概率 1-p-q-r: 添加一个节点。

描述演化网络的其他方法

除了上面描述的不断生长的网络模型之外，可能有时候其他方法对于描述演化网络的某些性质更有用或更方便。

趋向均衡

在竞争性决策发生的网络系统中，博弈论经常被用来建模系统动力学，趋向均衡可以被认为是拓扑进化的驱动力。例如Kasthurirathna和Piraveenan[5]表明，当一个系统中的个体表现出不同程度的理性时，提高整个系统的理性可能是无标度网络出现的进化原因。他们通过对一个最初的随机网络施加进化压力来模拟一系列经典博弈，当允许重新连接时，网络收敛到纳什均衡，从而证明了这一点。在这个过程中，网络变得越来越无标度。

视演化网络为连续的静态网络快照

观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为组成电影的一个个静态图像。有许多简单的参数可以描述一个静态网络（节点数、边、路径长度、连通子图），或者描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性单独作为时间序列进行研究。[6] 例如，我们可以通过查看网络的连续快照并计算每个快照中的链接数量，来跟踪每分钟建立到服务器的链接数量。

不幸的是，快照与电影的类比也揭示了这种方法的主要困难: 使用的时间步骤很少由网络给出，而是任意的。在每个快照之间使用极小的时间步骤可以保持分辨率，但实际上可能掩盖了只有在较长时间尺度下才能看到的更广泛的趋势。相反，使用较大的时间尺度会失去每个快照中事件的时间顺序。因此，可能很难找到合适的时间尺度来将网络的演化划分为静态快照。

定义动力学性质

那些不能直接从将演化网络视为一系列快照中观察到的特性可能很重要，例如节点之间的接触时间。[7]可以定义其他类似的属性，然后可以通过网络的演化来跟踪这些属性，并直接可视化它们。

使用连续快照的另一个问题是，在网络拓扑中微小的变化可以对用于寻找网络社团的算法的结果产生巨大的影响。因此，有必要使用一个非经典的社团定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，来跟随社团的演化。[8][9]

应用

2009年世界预定商业航空交通路线图。这个网络随着新路线的计划或取消而不断演变

几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变上述各自的概率，可以使用扩展的BA模型来构造一个具有与许多观测网络几乎相同属性的网络。[10]

此外，无标度网络的概念告诉我们，时间演化是理解网络属性的必要组成部分，而且很难将现有网络模型化为瞬间创建的。目前正在研究的演化网络包括社交网络、通信网络、互联网、电影演员网络、万维网和交通网络。

扩展阅读

  • "Linked: The New Science of Networks", A.-L. Barabási Perseus Publishing, Cambridge.

References

  1. ↑ Watts, D.J.; Strogatz, S.H. (1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 409–10. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998.
  2. ↑ Travers Jeffrey; Milgram Stanley (1969). "An Experimental Study of the Small World Problem". Sociometry. 32 (4): 425–443. doi:10.2307/2786545. JSTOR 2786545.
  3. ↑ R. Albert; A.-L. Barabási (2000). "Topology of Evolving Networks: Local Events and Universality" (PDF). Physical Review Letters. 85 (24): 5234–5237. arXiv:cond-mat/0005085. Bibcode:2000PhRvL..85.5234A. doi:10.1103/PhysRevLett.85.5234. hdl:2047/d20000695. PMID 11102229.
  4. ↑ Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 74, 47 (2002)
  5. ↑ Kasthurirathna, Dharshana; Piraveenan, Mahendra. (2015). "Emergence of scale-free characteristics in socioecological systems with bounded rationality". Scientific Reports. In Press.
  6. ↑ Pierre Borgnat; Eric Fleury; et al. "Evolving Networks" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
  7. ↑ A. Chaintreau; P. Hui; J. Crowcroft; C. Diot; R. Gass; J. Scott (2006). "Impact of human mobility on the design of opportunistic forwarding algorithms" (PDF). Infocom.
  8. ↑ G. Palla; A. Barabasi; T. Vicsek; Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng (2007). "Quantifying social group evolution". Nature. 446 (7136): 664–667. arXiv:0704.0744. Bibcode:2007Natur.446..664P. doi:10.1038/nature05670. PMID 17410175.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. ↑ Y. Chi, S. Zhuid=1281213&type=pdf; X. Song; J. Tatemura; B.L. Tseng (2007). Structural and temporal analysis of the blogosphere through community factorization. pp. 163–172. doi:10.1145/1281192.1281213. ISBN 9781595936097. http://portal.acm.org/ft_gateway.cfm?. 
  10. ↑ I. Farkas; I. Derenyi; H. Heong; et al. (2002). "Networks in life: scaling properties and eigenvalue spectra" (PDF). Physica. 314 (1–4): 25–34. arXiv:cond-mat/0303106. Bibcode:2002PhyA..314...25F. doi:10.1016/S0378-4371(02)01181-0. Archived from the original (PDF) on 2011-10-04. Retrieved 2011-04-21.

本中文词条由Steve Luo审校，打豆豆，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=演化网络_Evolving_networks&oldid=20018”