什么是演化网络 | 集智百科
本文是对集智百科中“演化网络”词条的摘录，参考资料及相关词条请参阅百科词条原文。
本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！
目录
一、什么是演化网络
二、网络理论背景
三、第一个演化网络模型——无标度网络
四、对BA模型的补充和扩展
五、描述演化网络的其他方法
六、应用
七、集智百科词条志愿者招募
演化网络：https://wiki.swarma.org/index.php?title=演化网络
1. 什么是演化网络
演化网络 evolving networks 是一种随时间而变化的网络，如同时变函数。演化网络是网络科学network science的一种自然延伸，毕竟几乎所有现实世界的网络都随时间而演化，随时间的推移，对网络的节点 nodes 或节点间的连接 links进行增添或去除。通常，所有这些增添或去除的网络演化过程都是同时发生的。比如在社交网络 social networks 中，随着时间的推移，人们结交和失去朋友，从而创建和切断节点间的连接，一些人成为新社交网络的一部分，或者离开他们本来所在的网络，从而改变网络中的节点。演化网络的概念建立在既有的网络理论之上，现在正被引入到许多不同领域的网络研究中。
2. 网络理论背景
对网络的研究基于graph theory 图论的发展。1736年，莱昂哈德·欧拉 Leonhard Euler 首先分析了这方面的问题，写了那篇著名的柯尼斯堡七桥问题 Seven Bridges of Königsberg 的论文。随后在八篇由保罗·埃尔德什 Paul Erdős和阿尔弗雷德·雷尼 Alfréd Rényi撰写的研究随机图 random graphs的著名论文的帮助下，概率网络理论得以发展。埃尔德什-雷尼模型 Erdős–Rényi model(ER模型)假定一个图由n个有标记的节点组成，其中每一对节点之间存在连接的概率为p。
尽管ER模型的简单性使得它有许多应用场景， 但它并不能准确地描述许多真实世界的网络。ER模型无法像在现实世界网络中那样频繁地生成局部聚类和三元闭包。为此，提出了瓦茨-斯托加茨模型 Watts-Strogatz model，为此，研究人员提出了瓦茨-斯托加茨模型 Watts-Strogatz model，将网络构造成规则的环形栅格，这样节点就根据一定的概率β而被重新连接。
这样可以产生一个含有局部聚类的网络，同时显著减少网络中的平均路径长度，从而创建出的网络可以表示在许多现实世界网络中所观察到的小世界现象 small world
尽管通过ER模型和Watts-Storgatz模型，我们取得了这些成果，然而，对于像在许多现实世界网络中所能观察到的那种中心节点，这两个模型都未能提供形式化的解释。
ER模型中的度分布近似于泊松分布，而Watts-Strogatz模型生成的图在度上是同质的，度分布函数为狄拉克 Dirac δ函数。然而，不同于这两类模型，许多现实世界中的网络，例如生物学网络 biological networks，或者科研合作网络 scientific collaboration networks 都是无标度的scale-free，这意味着他们的度分布遵循以下形式的幂律分布：
对于许多现实世界的网络来说，这个指数 γ 大约是3。然而，它不是一个通用常数，并且持续地依赖于网络的参数。·
3.第一个演化网络模型——无标度网络
巴拉巴西-阿尔伯特模型 Barabási–Albert model（BA模型）是第一个被广泛接受的产生无标度网络 scale-free network的模型。这是通过把网络生长和偏好依附（也译作择优连接、优先连接） preferential attachment合并起来考虑而实现的。在这种情形中，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。
BA模型首先应用于互联网的度分布。在这一应用场景中可以清楚的看见网络增长和偏好依附。随着时间的推移，不断有新的网页被添加进网络，并且每个新的网页都更有可能链接到像谷歌这样可见度高的中心节点（也就是具有很高的度的中心节点），而不是只有少量连接的节点。从形式上来说，这种偏好依附是:
4. 对BA模型的补充和扩展
BA模型是第一个从随着时间的推移而添加节点和连边的网络构造方式中推导出网络拓扑的模型。然而，该模型只做了产生无标度网络所必需的最简单的假设，即存在线性增长和线性偏好依附。这个最小模型没有刻画度分布形状的变化、度指数的变化、或不依赖大小的集聚系数 clustering coefficient。
因此，通过引入一些新的性质，研究者们对原有的模型进行了修改，以更充分地刻画演化网络的性质。
适应度
与BA模型有关的一个问题是，每个节点的度分布要经受很强的正反馈 positive feedback，即最早的具有高度分布的节点继续无限期地主宰网络。这一问题可以由为每个节点引入一个适应度来缓解，这一方法要修改创建新链接所用的节点的概率，甚至可以修改该节点的链接被删除的概率。
为了保持BA模型中的偏好依附，该适应度乘以基于度分布的偏好依附，得到连接到节点i的真实概率。
其中是适应度，它也可能与时间相关。适应度可能随时间衰减，可以被形式化为
其中随的增长而增长。
删除节点和重连接边
由于节点可能会以一定的概率从网络中移除，因此会出现更多的复杂情况。此外，现有节点之间现有的连接可能会被删除并且创建新的连接。这些行为发生的概率可能依赖于时间，也可能与节点的适应度有关。为了生长出具有相同性质的模型网络，可以通过研究待解决议题中有关网络的特性，来为这些事件（删除节点和重连接边）概率。这种生长将会随每个时间分段中的下列几种动作之一而发生：
概率 p：增加一个内部连接。
概率 q: 删除一个连接。
概率 r：删除一个节点。
概率 1-p-q-r: 添加一个节点。
5.描述演化网络的其他方法
除了上面描述的不断生长的网络模型之外，就描述演化网络的某些特征性质而言，可能有时候其他方法更有用或更方便。
趋向均衡
在需要制定竞争决策的网络系统中，我们经常用博弈论来对系统动态过程建模，并且可以认为，动态过程中朝向均衡态的收敛驱动了拓扑意义上的演化。例如Kasthurirathna和Piraveenan的研究表明，当一个系统中的个体表现出不同程度的理性时，对整个系统理性的提高可能是出现无标度网络的演化原因。他们通过对一个起初随机的网络施加随时间而演化的压力来模拟各种经典博弈，当允许网络重新连接节点时，网络收敛到纳什均衡，从而证明了这一点。在这个过程中，网络变得越来越无标度。
视演化网络为连续的静态网络快照
看待演化网络最常用的方法就是把它们考虑为连续的静态网络。这可以被概念化为构成动画的一个个静态图像。有许多简单的参数可以描述一个静态网络（节点数、边、路径长度、连通子图），或者描述图中的特定节点，比如连接数或集聚系数。然后可以使用信号处理中的概念将这些属性单独作为时间序列进行研究。例如，我们可以通过查看网络的连续快照并清点每个快照中的链接数量，来跟踪每分钟建立到服务器的链接数量。
不幸的是，快照与动画的类比也揭示了这种方法的主要困难:
所使用的时间步长一般来说是随机的，很少能由网络给出。在每个快照之间使用极小的时间步长可以保持分辨率，但实际上可能掩盖了只有在较长时间尺度下才能看到的更一般的趋势。反过来说，使用较大的时间尺度又会丢失每个快照中事件的时间顺序。因此，可能很难找到合适的时间尺度来将网络的演化分割为一幅幅静态快照。
定义动力学性质
不能通过将演化网络视为一系列快照而被直接观察到的特性可能很重要，例如节点之间的接触时长。可以定义其他类似的属性，然后可以通过网络的演化来跟踪这些属性，并直接可视化它们。
使用连续快照的另一个问题是，在网络拓扑中微小的变化可以对用于寻找网络社团的算法的结果产生巨大的影响。因此，有必要使用一个非经典的社团定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，来跟随社团的演化。
6.应用
几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变前文所述中各自的概率，可以使用扩展的BA模型来构造一个与所观测到的网络几乎具有相同性质的网络。
此外，无标度网络的概念告诉我们，时间演化是理解网络性质的必要成分，而且对现有的网络进行即时建模，而且很难将现有网络模型化为瞬间创建的。目前正在研究的演化网络包括社交网络、通信网络、互联网、电影演员网络、万维网和交通网络。
2009年世界预定商业航空交通路线图。这个网络随着新路线的计划或取消而不断演变
7.百科项目志愿者招募
作为集智百科项目团队的成员，本文内容由Steve Luo、打豆豆参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。
在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。
如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！
来源：集智百科审校：LUX编辑：曾祥轩
点击“阅读原文”，阅读演化网络原文与参考文献