更改

[[File:256px-Barabasi_Albert_model.gif|thumb|256px|基于初始巴拉巴西-阿尔伯特 Barabasi-Albert 模型的演化网络的动画]]

[[File:256px-Barabasi_Albert_model.gif|thumb|256px|基于初始巴拉巴西-阿尔伯特 Barabasi-Albert 模型的演化网络的动画]]

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

演化网络 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连接。

'''网络研究源于图论 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连接。

[[File:220px-Watts_strogatz.svg.png|220px|thumb|Watts–Strogatz graph 瓦茨-斯托加茨图]]

[[File:220px-Watts_strogatz.svg.png|220px|thumb|Watts–Strogatz graph 瓦茨-斯托加茨图]]

这会产生一个局部聚集的网络，并显著减少平均路径长度 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>

这会产生一个局部聚集的网络，并显著减少平均路径长度 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模型生成的图在度上是同质的。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的幂律分布:

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

: <math>P(k)\sim k^{-\gamma}</math>

: <math>P(k)\sim k^{-\gamma}</math>

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

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

巴拉巴西-阿尔伯特模型 Barabási–Albert model(BA模型)是第一个被广泛接受的产生无标度网络 scale-free network的模型。这是通过偏好依附 preferential attachment和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。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>

==BA模型以外==

==BA模型以外==

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

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

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

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

===适应度===

===适应度===

与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模型有关的一个问题是，每个节点的度分布经历很强的[[正反馈 positive feedback]]，即最早的具有高度分布的节点继续无限期地主宰网络。但是，可以通过为每个节点引入一个适应度来缓解这个问题，该适应度可以修改用该节点创建新链接的概率，甚至可以修改该节点的链接被删除的概率。<ref>Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", ''Reviews of Modern Physics'' 74, 47 (2002)</ref>

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

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

其中<math>\gamma</math>随<math>\nu.</math>的增长而增长。

其中<math>\gamma</math>随<math>\nu.</math>的增长而增长。

===删除节点和重连接边===

===删除节点和重连接边===

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

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

==描述演化网络的其他方法==

==描述演化网络的其他方法==

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

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

===趋向均衡===

===趋向均衡===

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

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

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

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

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

===定义动力学性质===

===定义动力学性质===

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

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

==扩展阅读==

==扩展阅读==

* "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.

==参考资料==

==参考资料==

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

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

[[Category:网络]]

[[Category:网络]]

[[Category:网络理论]]

[[Category:网络理论]]