演化网络

此词条暂由彩云小译翻译，正由Steve Luo整理和审校，带来阅读不便，请见谅。

Animation of an evolving network according to the initial Barabasi–Albert model

Animation of an evolving network according to the initial Barabasi–Albert model

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

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.

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.

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

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.

网络研究源于图论 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.svg

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 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 β.

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 β.

}}</ref> 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.

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

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:

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模型中的度分布遵循泊松分布，而Watts-Strogatz模型生成的图在度上是同质的。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的幂律分布:

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

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

数学 p (k) sim k ^ {- gamma } / math

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

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

}}</ref>

{} / ref

First evolving network model – scale-free networks 第一个演化网络模型——无标度网络

Main article: Barabási–Albert model

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:

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

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

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

数学，数学，数学

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

Therefore, the original model has since been modified模板:By whom? 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.

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

Fitness 适应度

Main article: 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.

</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 的真实概率。

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

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \eta }[/math]是适应度，这也可能依赖时间。适应度可能随时间衰减，可以表示为

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

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

Math Pi (ki) propto ki (t-t i) ^ {- nu } ，/ math

where [math]\displaystyle{ \gamma }[/math] increases with [math]\displaystyle{ \nu. }[/math]

where [math]\displaystyle{ \gamma }[/math] increases with [math]\displaystyle{ \nu. }[/math]

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

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：增加一个内部链接。

Prob q: delete a link.

Prob q: delete a link.

概率 q: 删除一个链接。

Prob r: delete a node.

Prob r: delete a node.

概率 r：删除一个节点。

Prob 1-p-q-r: add a node.

Prob 1-p-q-r: add a node.

概率 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 趋向均衡

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

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.

|volume=In Press |date=2015}}</ref> 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.

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

|display-authors=etal}}</ref> 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.

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.

}}</ref> 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

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>

{} / ref

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

Applications 应用

文件:World-airline-routemap-2009.png

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

}}</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, 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

• "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

Category:Networks

类别: 网络

Category:Network theory

范畴: 网络理论

This page was moved from wikipedia:en:Evolving network. Its edit history can be viewed at 网络演化/edithistory