1,569
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Evolving network (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
[[Image:Barabasi Albert model.gif|thumb|256px|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 [[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.
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.
进化的网络是随着时间的变化而变化的网络。它们是网络科学的自然延伸，因为几乎所有的现实世界的网络都是随着时间演变的，无论是通过增加或删除节点或链接随着时间的推移。通常所有这些过程都是同时发生的，比如在社交网络中，人们随着时间的推移结交或失去朋友，从而创造和破坏边缘，一些人成为新的社交网络的一部分，或者离开他们的网络，改变网络中的节点。不断发展的网络概念建立在已有的网络理论基础之上，现在正被引入到许多不同领域的网络研究中。
==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.
对网络的研究可以追溯到图论的发展，1736年 Leonhard Euler 首先分析了图论，当时他写了著名的柯尼斯堡七桥问题。概率网络理论是在八篇著名的随机图研究论文的基础上发展起来的。Erd s-r nyi 模型(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 '''β'''.<ref name=WS>{{cite journal
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 name=WS>{{cite journal
尽管 ER 模型的简单性帮助它找到了许多应用程序，但它并不能准确地描述许多真实世界的网络。Er 模型不能像现实网络中常见的那样产生局部聚类和三元闭包。为此，提出了 Watts-Strogatz 模型，将网络构造成规则的环网格，然后根据一定的概率重新布线节点。 引用名称 ws { cite journal
| author1 = Watts, D.J.
| author1 = Watts, D.J.
1 Watts，d.j.
| author2 = Strogatz, S.H.
| author2 = Strogatz, S.H.
2 Strogatz，s.h.
| year = 1998
| year = 1998
1998年
| title = Collective dynamics of 'small-world' networks
| title = Collective dynamics of 'small-world' networks
| 题目“小世界”网络的集体动态
| journal = Nature
| journal = Nature
自然》杂志
| volume = 393
| volume = 393
第393卷
| issue = 6684
| issue = 6684
第6684期
| pages = 409–10
| pages = 409–10
第409-10页
| doi = 10.1038/30918
| doi = 10.1038/30918
10.1038 / 30918
| pmid = 9623998
| pmid = 9623998
9623998
| bibcode=1998Natur.393..440W
| bibcode=1998Natur.393..440W
| bibcode 1998 / natur. 393. . 440 w
}}</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.<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>
}}</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 这会产生一个局部聚集的网络，并显著减少平均路径长度，创建网络，代表在许多现实世界网络中观察到的小世界现象。
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 模型都未能解释在许多现实世界网络中观察到的集线器的形成。模型中的度分布遵循泊松分佈，而 Watts 和 Strogatz 模型生成的图在度上是均匀的。许多网络是无标度的，这意味着它们的学位分布遵循一种形式的幂定律:
: <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 <ref name=Barabasi2000>{{Cite journal
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 name=Barabasi2000>{{Cite journal
对于许多现实世界的网络来说，这个指数大约是3，然而，它不是一个通用常数，并且连续地依赖于网络的参数，例如 barabasi2000{ Cite journal
| url = http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf
| url = http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf
Http://nd.edu/~networks/publication%20categories/03%20journal%20articles/physics/universality_physical%20rev%20ltrs%2085,%205234%20(2000).pdf
| author1 = R. Albert
| author1 = R. Albert
1 r. Albert
| author2 = A.-L. Barabási
| author2 = A.-L. Barabási
| author2 A.-L. barab si
| title = Topology of Evolving Networks: Local Events and Universality
| title = Topology of Evolving Networks: Local Events and Universality
演化网络的拓扑结构: 局部事件与普适性
| journal = [[Physical Review Letters]]
| journal = Physical Review Letters
物理评论快报
| volume = 85
| volume = 85
第85卷
| issue = 24
| issue = 24
第24期
| pages = 5234–5237
| pages = 5234–5237
第5234-5237页
| year = 2000
| year = 2000
2000年
| doi = 10.1103/PhysRevLett.85.5234
| doi = 10.1103/PhysRevLett.85.5234
10.1103 / physrvlett. 85.5234
| pmid = 11102229
| pmid = 11102229
11102229
|arxiv = cond-mat/0005085 |bibcode = 2000PhRvL..85.5234A | hdl = 2047/d20000695
|arxiv = cond-mat/0005085 |bibcode = 2000PhRvL..85.5234A | hdl = 2047/d20000695
| arxiv cond-mat / 0005085 | bibcode 2000PhRvL. . 85.5234 a | hdl 2047 / d20000695
}}</ref>
}}</ref>
{} / 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 (BA)模型是第一个被广泛接受的产生无标度网络的模型。这是通过合并优先连接和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他高度分布的节点。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>
数学，数学，数学
==Additions to BA model==
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.
英国广播公司模型是第一个根据网络的构建方式推导出网络拓扑广播模型的模型，随着时间的推移，网络中的节点和链路不断增加。然而，这个模型只做了最简单的假设，而这些假设对无尺度网络的出现是必要的，即存在线性增长和线性优先连接。这个最小模型没有捕捉度分布形状的变化，度指数的变化，或大小无关的集聚系数。
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.
因此，通过引入一些新的性质，对原有的模型进行了修改，以更充分地捕捉演化网络的性质。
===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.<ref>
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>
Ba 模型的一个关注点是每个节点的度分布经历强正反馈，即最早的高度分布节点继续无限期地主宰网络。但是，可以通过为每个节点引入一个适应度来缓解这个问题，该适应度可以修改用该节点创建新链接的概率，甚至可以修改到该节点的链接被删除的概率。 裁判
Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", ''Reviews of Modern Physics'' 74, 47 (2002)
Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 74, 47 (2002)
和 barab si a.-l. ，“复杂网络的统计力学” ，《现代物理学评论》74,47(2002)
</ref>
</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 模型中的优先连接，该适应度乘以基于度分布的优先连接，得到连接到节点的连接的真实概率。
: <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> \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>
数学 / 数学随着数学 / 数学的增长而增长-数学
===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.
增加一个内部链接。
Prob q: delete a link.
Prob q: delete a link.
问题: 删除链接。
Prob r: delete a node.
Prob r: delete a node.
删除一个节点。
Prob 1-p-q-r: add a node.
Prob 1-p-q-r: add a node.
Prob1-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 <ref>{{cite journal
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 <ref>{{cite journal
在竞争性决策发生的网络系统中，博弈论经常被用来建立系统动力学模型，趋向均衡可以被认为是拓扑进化的驱动力。例如，Kasthurirathna 和 Piraveenan 参考{ cite journal
|last1=Kasthurirathna|first1=Dharshana
|last1=Kasthurirathna|first1=Dharshana
1 / 2010 / 01 / 01
|last2=Piraveenan |first2=Mahendra.
|last2=Piraveenan |first2=Mahendra.
2 Piraveenan | first2 Mahendra.
|title=Emergence of scale-free characteristics in socioecological systems with bounded rationality
|title=Emergence of scale-free characteristics in socioecological systems with bounded rationality
使用有限理性的社会生态系统中无尺度特性的出现
|journal=[[Scientific Reports (journal)|Scientific Reports]]
|journal=Scientific Reports
科学报告
|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.
|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 [[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.<ref name=EvolvingNetworksPDF>{{Cite journal
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.<ref name=EvolvingNetworksPDF>{{Cite journal
观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为个人静态图像组成一个电影。许多简单的参数用来描述一个静态网络(节点数、边、路径长度、连接组件) ，或者用来描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性分别作为时间序列进行研究
| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf
| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf
Http://liris.cnrs.fr/documents/liris-3669.pdf
| author1 = Pierre Borgnat
| author1 = Pierre Borgnat
作者: Pierre Borgnat
| author2 = Eric Fleury
| author2 = Eric Fleury
作者: Eric Fleury
| title = Evolving Networks
| title = Evolving Networks
标题演变中的网络
|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.
|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<ref name="Impact of human mobility on the
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<ref name="Impact of human mobility on the
将进化中的网络视为一系列快照，可能不能直接观察到这些特性，这一点可能很重要，例如节点之间的接触时间，参考名称“人类活动对网络的影响”
design of opportunistic forwarding algorithms">{{Cite journal
design of opportunistic forwarding algorithms">{{Cite journal
设计机会转发算法”{ Cite journal
| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf
| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf
Http://www.cl.cam.ac.uk/~ph315/publications/pid158626.pdf
| author1 = A. Chaintreau
| author1 = A. Chaintreau
| author1 a. Chaintreau
| author2 = P. Hui
| author2 = P. Hui
| author2 p Hui
| author3 = J. Crowcroft
| author3 = J. Crowcroft
作者: j. Crowcroft
| author4 = C. Diot
| author4 = C. Diot
4 c. Diot
| author5 = R. Gass
| author5 = R. Gass
5 r. Gass
| author6 = J. Scott
| author6 = J. Scott
作者: j · 斯科特
| journal = Infocom
| journal = Infocom
| journal = Infocom
| year = 2006
| year = 2006
2006年
| title = Impact of human mobility on the design of opportunistic forwarding algorithms
| title = Impact of human mobility on the design of opportunistic forwarding algorithms
人类移动性对机会转发算法设计的影响
}}</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> 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 name="Quantifying social group evolution">{{Cite journal
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
使用连续快照的另一个问题是，在网络拓扑中只有微小的变化可以对用于寻找社区的算法的结果产生巨大的影响。因此，有必要使用一个非古典的社区定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，跟随社区的演变。 量化社会群体进化{ Cite journal
| author1 = G. Palla
| author1 = G. Palla
1 g. Palla
| author2 = A. Barabasi
| author2 = A. Barabasi
2 a. Barabasi
| author3 = T. Vicsek
| author3 = T. Vicsek
3 t. Vicsek
| title = Quantifying social group evolution
| title = Quantifying social group evolution
社会群体进化的量化
| journal = Nature
| journal = Nature
自然》杂志
| volume = 446
| volume = 446
第446卷
| pages = 664–667
| pages = 664–667
第664-667页
| year = 2007
| year = 2007
2007年
| author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng
| author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng
作者: 纪耀华，朱，x。和 b.l。曾
| issue=7136
| issue=7136
第7136期
| doi=10.1038/nature05670
| doi=10.1038/nature05670
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
|pmid = 17410175|arxiv = 0704.0744 |bibcode = 2007Natur.446..664P }}</ref><ref name="Structural and temporal analysis of the blogosphere through community factorization">{{Cite book
17410175 | arxiv 0704.0744 | bibcode 2007Natur. 446. . 664 p } / ref name"通过社区因子分解对博客圈的结构和时间分析"{ Cite book
| url = http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
| url = http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
Http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
| author1 = Y. Chi, S. Zhu
| author1 = Y. Chi, S. Zhu
1 y. Chi，s. Zhu
| author2 = X. Song
| author2 = X. Song
2 x.歌曲
| author3 = J. Tatemura
| author3 = J. Tatemura
作者: j. Tatemura
| author4 = B.L. Tseng
| author4 = B.L. Tseng
| author4 b.l.曾
| title = Structural and temporal analysis of the blogosphere through community factorization
| 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
| journal = KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
2007: 第13届 ACM SIGKDD 国际知识发现和数据挖掘会议论文集
| pages = 163–172
| pages = 163–172
第163-172页
| year = 2007
| year = 2007
2007年
| doi = 10.1145/1281192.1281213
| doi = 10.1145/1281192.1281213
10.1145 / 1281192.1281213
| citeseerx = 10.1.1.69.6959
| citeseerx = 10.1.1.69.6959
10.1.1.69.6959
| isbn = 9781595936097
| isbn = 9781595936097
9781595936097
}}</ref>
}}</ref>
{} / ref
==Applications==
[[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.<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal
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.<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal
几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变上述各自的概率，可以使用扩展的 BA 模型来构造一个具有与许多观测网络几乎相同属性的网络。 生活中的网络: 比例特性和特征值谱{ Cite journal
|url = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf
|url = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf
Http://www.barabasilab.com/pubs/ccnr-alb_publications/200211-01_physa-networksinlife/200211-01_physa-networksinlife.pdf
|author1 = I. Farkas
|author1 = I. Farkas
1 i. Farkas
|author2 = I. Derenyi
|author2 = I. Derenyi
2 i. Derenyi
|author3 = H. Heong
|author3 = H. Heong
3 h Heong
|title = Networks in life: scaling properties and eigenvalue spectra
|title = Networks in life: scaling properties and eigenvalue spectra
生活中的网络: 标度特性和特征值谱
|journal = [[Physica A|Physica]]
|journal = Physica
物理学杂志
|volume = 314
|volume = 314
第314卷
|issue = 1–4
|issue = 1–4
第1-4期
|pages = 25–34
|pages = 25–34
第25-34页
|year = 2002
|year = 2002
2002年
|arxiv = cond-mat/0303106
|arxiv = cond-mat/0303106
|arxiv = cond-mat/0303106
|bibcode = 2002PhyA..314...25F
|bibcode = 2002PhyA..314...25F
2002 / phya. . 314... 25F
|doi = 10.1016/S0378-4371(02)01181-0
|doi = 10.1016/S0378-4371(02)01181-0
| doi 10.1016 / S0378-4371(02)01181-0
|display-authors = etal
|display-authors = etal
展示-作者金属
|access-date = 2011-04-21
|access-date = 2011-04-21
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-url = https://web.archive.org/web/20111004050804/http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf
| 档案-网址 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
|archive-date = 2011-10-04
| 档案-日期2011-10-04
|url-status = dead
|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.
}}</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.
==References==
<references />
{{DEFAULTSORT:Evolving Networks}}
[[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:待整理页面]]
[[Image:Barabasi Albert model.gif|thumb|256px|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 [[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.
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.
进化的网络是随着时间的变化而变化的网络。它们是网络科学的自然延伸，因为几乎所有的现实世界的网络都是随着时间演变的，无论是通过增加或删除节点或链接随着时间的推移。通常所有这些过程都是同时发生的，比如在社交网络中，人们随着时间的推移结交或失去朋友，从而创造和破坏边缘，一些人成为新的社交网络的一部分，或者离开他们的网络，改变网络中的节点。不断发展的网络概念建立在已有的网络理论基础之上，现在正被引入到许多不同领域的网络研究中。
==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.
对网络的研究可以追溯到图论的发展，1736年 Leonhard Euler 首先分析了图论，当时他写了著名的柯尼斯堡七桥问题。概率网络理论是在八篇著名的随机图研究论文的基础上发展起来的。Erd s-r nyi 模型(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 '''β'''.<ref name=WS>{{cite journal
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 name=WS>{{cite journal
尽管 ER 模型的简单性帮助它找到了许多应用程序，但它并不能准确地描述许多真实世界的网络。Er 模型不能像现实网络中常见的那样产生局部聚类和三元闭包。为此，提出了 Watts-Strogatz 模型，将网络构造成规则的环网格，然后根据一定的概率重新布线节点。 引用名称 ws { cite journal
| author1 = Watts, D.J.
| author1 = Watts, D.J.
1 Watts，d.j.
| author2 = Strogatz, S.H.
| author2 = Strogatz, S.H.
2 Strogatz，s.h.
| year = 1998
| year = 1998
1998年
| title = Collective dynamics of 'small-world' networks
| title = Collective dynamics of 'small-world' networks
| 题目“小世界”网络的集体动态
| journal = Nature
| journal = Nature
自然》杂志
| volume = 393
| volume = 393
第393卷
| issue = 6684
| issue = 6684
第6684期
| pages = 409–10
| pages = 409–10
第409-10页
| doi = 10.1038/30918
| doi = 10.1038/30918
10.1038 / 30918
| pmid = 9623998
| pmid = 9623998
9623998
| bibcode=1998Natur.393..440W
| bibcode=1998Natur.393..440W
| bibcode 1998 / natur. 393. . 440 w
}}</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.<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>
}}</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 这会产生一个局部聚集的网络，并显著减少平均路径长度，创建网络，代表在许多现实世界网络中观察到的小世界现象。
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 模型都未能解释在许多现实世界网络中观察到的集线器的形成。模型中的度分布遵循泊松分佈，而 Watts 和 Strogatz 模型生成的图在度上是均匀的。许多网络是无标度的，这意味着它们的学位分布遵循一种形式的幂定律:
: <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 <ref name=Barabasi2000>{{Cite journal
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 name=Barabasi2000>{{Cite journal
对于许多现实世界的网络来说，这个指数大约是3，然而，它不是一个通用常数，并且连续地依赖于网络的参数，例如 barabasi2000{ Cite journal
| url = http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf
| url = http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf
Http://nd.edu/~networks/publication%20categories/03%20journal%20articles/physics/universality_physical%20rev%20ltrs%2085,%205234%20(2000).pdf
| author1 = R. Albert
| author1 = R. Albert
1 r. Albert
| author2 = A.-L. Barabási
| author2 = A.-L. Barabási
| author2 A.-L. barab si
| title = Topology of Evolving Networks: Local Events and Universality
| title = Topology of Evolving Networks: Local Events and Universality
演化网络的拓扑结构: 局部事件与普适性
| journal = [[Physical Review Letters]]
| journal = Physical Review Letters
物理评论快报
| volume = 85
| volume = 85
第85卷
| issue = 24
| issue = 24
第24期
| pages = 5234–5237
| pages = 5234–5237
第5234-5237页
| year = 2000
| year = 2000
2000年
| doi = 10.1103/PhysRevLett.85.5234
| doi = 10.1103/PhysRevLett.85.5234
10.1103 / physrvlett. 85.5234
| pmid = 11102229
| pmid = 11102229
11102229
|arxiv = cond-mat/0005085 |bibcode = 2000PhRvL..85.5234A | hdl = 2047/d20000695
|arxiv = cond-mat/0005085 |bibcode = 2000PhRvL..85.5234A | hdl = 2047/d20000695
| arxiv cond-mat / 0005085 | bibcode 2000PhRvL. . 85.5234 a | hdl 2047 / d20000695
}}</ref>
}}</ref>
{} / 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 (BA)模型是第一个被广泛接受的产生无标度网络的模型。这是通过合并优先连接和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他高度分布的节点。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>
数学，数学，数学
==Additions to BA model==
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.
英国广播公司模型是第一个根据网络的构建方式推导出网络拓扑广播模型的模型，随着时间的推移，网络中的节点和链路不断增加。然而，这个模型只做了最简单的假设，而这些假设对无尺度网络的出现是必要的，即存在线性增长和线性优先连接。这个最小模型没有捕捉度分布形状的变化，度指数的变化，或大小无关的集聚系数。
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.
因此，通过引入一些新的性质，对原有的模型进行了修改，以更充分地捕捉演化网络的性质。
===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.<ref>
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>
Ba 模型的一个关注点是每个节点的度分布经历强正反馈，即最早的高度分布节点继续无限期地主宰网络。但是，可以通过为每个节点引入一个适应度来缓解这个问题，该适应度可以修改用该节点创建新链接的概率，甚至可以修改到该节点的链接被删除的概率。 裁判
Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", ''Reviews of Modern Physics'' 74, 47 (2002)
Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 74, 47 (2002)
和 barab si a.-l. ，“复杂网络的统计力学” ，《现代物理学评论》74,47(2002)
</ref>
</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 模型中的优先连接，该适应度乘以基于度分布的优先连接，得到连接到节点的连接的真实概率。
: <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> \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>
数学 / 数学随着数学 / 数学的增长而增长-数学
===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.
增加一个内部链接。
Prob q: delete a link.
Prob q: delete a link.
问题: 删除链接。
Prob r: delete a node.
Prob r: delete a node.
删除一个节点。
Prob 1-p-q-r: add a node.
Prob 1-p-q-r: add a node.
Prob1-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 <ref>{{cite journal
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 <ref>{{cite journal
在竞争性决策发生的网络系统中，博弈论经常被用来建立系统动力学模型，趋向均衡可以被认为是拓扑进化的驱动力。例如，Kasthurirathna 和 Piraveenan 参考{ cite journal
|last1=Kasthurirathna|first1=Dharshana
|last1=Kasthurirathna|first1=Dharshana
1 / 2010 / 01 / 01
|last2=Piraveenan |first2=Mahendra.
|last2=Piraveenan |first2=Mahendra.
2 Piraveenan | first2 Mahendra.
|title=Emergence of scale-free characteristics in socioecological systems with bounded rationality
|title=Emergence of scale-free characteristics in socioecological systems with bounded rationality
使用有限理性的社会生态系统中无尺度特性的出现
|journal=[[Scientific Reports (journal)|Scientific Reports]]
|journal=Scientific Reports
科学报告
|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.
|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 [[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.<ref name=EvolvingNetworksPDF>{{Cite journal
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.<ref name=EvolvingNetworksPDF>{{Cite journal
观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为个人静态图像组成一个电影。许多简单的参数用来描述一个静态网络(节点数、边、路径长度、连接组件) ，或者用来描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性分别作为时间序列进行研究
| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf
| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf
Http://liris.cnrs.fr/documents/liris-3669.pdf
| author1 = Pierre Borgnat
| author1 = Pierre Borgnat
作者: Pierre Borgnat
| author2 = Eric Fleury
| author2 = Eric Fleury
作者: Eric Fleury
| title = Evolving Networks
| title = Evolving Networks
标题演变中的网络
|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.
|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<ref name="Impact of human mobility on the
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<ref name="Impact of human mobility on the
将进化中的网络视为一系列快照，可能不能直接观察到这些特性，这一点可能很重要，例如节点之间的接触时间，参考名称“人类活动对网络的影响”
design of opportunistic forwarding algorithms">{{Cite journal
design of opportunistic forwarding algorithms">{{Cite journal
设计机会转发算法”{ Cite journal
| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf
| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf
Http://www.cl.cam.ac.uk/~ph315/publications/pid158626.pdf
| author1 = A. Chaintreau
| author1 = A. Chaintreau
| author1 a. Chaintreau
| author2 = P. Hui
| author2 = P. Hui
| author2 p Hui
| author3 = J. Crowcroft
| author3 = J. Crowcroft
作者: j. Crowcroft
| author4 = C. Diot
| author4 = C. Diot
4 c. Diot
| author5 = R. Gass
| author5 = R. Gass
5 r. Gass
| author6 = J. Scott
| author6 = J. Scott
作者: j · 斯科特
| journal = Infocom
| journal = Infocom
| journal = Infocom
| year = 2006
| year = 2006
2006年
| title = Impact of human mobility on the design of opportunistic forwarding algorithms
| title = Impact of human mobility on the design of opportunistic forwarding algorithms
人类移动性对机会转发算法设计的影响
}}</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> 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 name="Quantifying social group evolution">{{Cite journal
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
使用连续快照的另一个问题是，在网络拓扑中只有微小的变化可以对用于寻找社区的算法的结果产生巨大的影响。因此，有必要使用一个非古典的社区定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，跟随社区的演变。 量化社会群体进化{ Cite journal
| author1 = G. Palla
| author1 = G. Palla
1 g. Palla
| author2 = A. Barabasi
| author2 = A. Barabasi
2 a. Barabasi
| author3 = T. Vicsek
| author3 = T. Vicsek
3 t. Vicsek
| title = Quantifying social group evolution
| title = Quantifying social group evolution
社会群体进化的量化
| journal = Nature
| journal = Nature
自然》杂志
| volume = 446
| volume = 446
第446卷
| pages = 664–667
| pages = 664–667
第664-667页
| year = 2007
| year = 2007
2007年
| author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng
| author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng
作者: 纪耀华，朱，x。和 b.l。曾
| issue=7136
| issue=7136
第7136期
| doi=10.1038/nature05670
| doi=10.1038/nature05670
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
|pmid = 17410175|arxiv = 0704.0744 |bibcode = 2007Natur.446..664P }}</ref><ref name="Structural and temporal analysis of the blogosphere through community factorization">{{Cite book
17410175 | arxiv 0704.0744 | bibcode 2007Natur. 446. . 664 p } / ref name"通过社区因子分解对博客圈的结构和时间分析"{ Cite book
| url = http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
| url = http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
Http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
| author1 = Y. Chi, S. Zhu
| author1 = Y. Chi, S. Zhu
1 y. Chi，s. Zhu
| author2 = X. Song
| author2 = X. Song
2 x.歌曲
| author3 = J. Tatemura
| author3 = J. Tatemura
作者: j. Tatemura
| author4 = B.L. Tseng
| author4 = B.L. Tseng
| author4 b.l.曾
| title = Structural and temporal analysis of the blogosphere through community factorization
| 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
| journal = KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
2007: 第13届 ACM SIGKDD 国际知识发现和数据挖掘会议论文集
| pages = 163–172
| pages = 163–172
第163-172页
| year = 2007
| year = 2007
2007年
| doi = 10.1145/1281192.1281213
| doi = 10.1145/1281192.1281213
10.1145 / 1281192.1281213
| citeseerx = 10.1.1.69.6959
| citeseerx = 10.1.1.69.6959
10.1.1.69.6959
| isbn = 9781595936097
| isbn = 9781595936097
9781595936097
}}</ref>
}}</ref>
{} / ref
==Applications==
[[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.<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal
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.<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal
几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变上述各自的概率，可以使用扩展的 BA 模型来构造一个具有与许多观测网络几乎相同属性的网络。 生活中的网络: 比例特性和特征值谱{ Cite journal
|url = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf
|url = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf
Http://www.barabasilab.com/pubs/ccnr-alb_publications/200211-01_physa-networksinlife/200211-01_physa-networksinlife.pdf
|author1 = I. Farkas
|author1 = I. Farkas
1 i. Farkas
|author2 = I. Derenyi
|author2 = I. Derenyi
2 i. Derenyi
|author3 = H. Heong
|author3 = H. Heong
3 h Heong
|title = Networks in life: scaling properties and eigenvalue spectra
|title = Networks in life: scaling properties and eigenvalue spectra
生活中的网络: 标度特性和特征值谱
|journal = [[Physica A|Physica]]
|journal = Physica
物理学杂志
|volume = 314
|volume = 314
第314卷
|issue = 1–4
|issue = 1–4
第1-4期
|pages = 25–34
|pages = 25–34
第25-34页
|year = 2002
|year = 2002
2002年
|arxiv = cond-mat/0303106
|arxiv = cond-mat/0303106
|arxiv = cond-mat/0303106
|bibcode = 2002PhyA..314...25F
|bibcode = 2002PhyA..314...25F
2002 / phya. . 314... 25F
|doi = 10.1016/S0378-4371(02)01181-0
|doi = 10.1016/S0378-4371(02)01181-0
| doi 10.1016 / S0378-4371(02)01181-0
|display-authors = etal
|display-authors = etal
展示-作者金属
|access-date = 2011-04-21
|access-date = 2011-04-21
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-url = https://web.archive.org/web/20111004050804/http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf
| 档案-网址 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
|archive-date = 2011-10-04
| 档案-日期2011-10-04
|url-status = dead
|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.
}}</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.
==References==
<references />
{{DEFAULTSORT:Evolving Networks}}
[[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:待整理页面]]