18
个编辑
更改
无编辑摘要
While the ER model's simplicity has helped it find many applications, it does not accurately describe many real world networks. The ER model fails to generate local clustering and [[triadic closure]]s as often as they are found in real world networks. Therefore, the [[Watts and Strogatz model]] was proposed, whereby a network is constructed as a regular ring lattice, and then nodes are rewired according to some probability '''β'''.
While the ER model's simplicity has helped it find many applications, it does not accurately describe many real world networks. The ER model fails to generate local clustering and [[triadic closure]]s as often as they are found in real world networks. Therefore, the [[Watts and Strogatz model]] was proposed, whereby a network is constructed as a regular ring lattice, and then nodes are rewired according to some probability '''β'''.
While the ER model's simplicity has helped it find many applications, it does not accurately describe many real world networks. The ER model fails to generate local clustering and triadic closures as often as they are found in real world networks. Therefore, the Watts and Strogatz model was proposed, whereby a network is constructed as a regular ring lattice, and then nodes are rewired according to some probability β.<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 β.
尽管ER模型的简单性帮助它找到了许多应用之处，但它并不能准确地描述许多真实世界的网络。ER模型无法像在现实世界网络中那样频繁地生成局部聚类和三元闭包。为此，提出了<font color="#ff8000">瓦茨-斯托加茨模型 Watts-Strogatz model</font>，将网络构造成规则的环网格，然后根据一定的概率β重新连接节点。<ref name=WS>{{cite journal | author1 = Watts, D.J. | author2 = Strogatz, S.H. | year = 1998 | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 409–10 | doi = 10.1038/30918 | pmid = 9623998 | bibcode=1998Natur.393..440W}}</ref>
尽管ER模型的简单性帮助它找到了许多应用之处，但它并不能准确地描述许多真实世界的网络。ER模型无法像在现实世界网络中那样频繁地生成局部聚类和三元闭包。为此，提出了<font color="#ff8000">瓦茨-斯托加茨模型 Watts-Strogatz model</font>，将网络构造成规则的环网格，然后根据一定的概率β重新连接节点。<ref name=WS>{{cite journal | author1 = Watts, D.J. | author2 = Strogatz, S.H. | year = 1998 | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 409–10 | doi = 10.1038/30918 | pmid = 9623998 | bibcode=1998Natur.393..440W}}</ref>
尽管取得了这样的成就，ER模型和Watts-Storgatz模型都未能解释在许多现实世界网络中观察到的中心节点的形成。ER模型中的度分布遵循<font color="#ff8000">泊松分布</font>，而Watts-Strogatz模型生成的图在<font color="#ff8000">度</font>上是<font color="#ff8000">同质的</font>。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的<font color="#ff8000">幂律分布</font>:
尽管取得了这样的成就，ER模型和Watts-Storgatz模型都未能解释在许多现实世界网络中观察到的中心节点的形成。ER模型中的度分布遵循<font color="#ff8000">泊松分布</font>，而Watts-Strogatz模型生成的图在<font color="#ff8000">度</font>上是<font color="#ff8000">同质的</font>。但是，许多网络是无标度的，这意味着它们的度分布遵循以下形式的<font color="#ff8000">幂律分布</font>:
: <math>P(k)\sim k^{-\gamma}</math>
: <math>P(k)\sim k^{-\gamma}</math>
巴拉巴西-阿尔伯特模型 Barabási–Albert model(BA模型)是第一个被广泛接受的产生<font color="#ff8000">无标度网络 scale-free network</font>的模型。这是通过<font color="#ff8000">偏好依附 preferential attachment</font>和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。BA模型首先应用于互联网的度分布，这两种影响都可以清楚地看到。随着时间的推移，新的网页会不断增加，并且每个新的网页都更有可能链接到像谷歌这样具有很高的度分布的高度可见的中心节点，而不是只有少量链接的节点。从形式上来说，这种偏好依附是:
巴拉巴西-阿尔伯特模型 Barabási–Albert model(BA模型)是第一个被广泛接受的产生<font color="#ff8000">无标度网络 scale-free network</font>的模型。这是通过<font color="#ff8000">偏好依附 preferential attachment</font>和增长来实现的，随着时间的推移，节点被添加到网络中，并且更有可能链接到其他度较大的节点。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>
===Convergence towards equilibria 趋向均衡===
===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 have shown that when individuals in a system display varying levels of rationality, improving the overall system rationality might be an evolutionary reason for the emergence of scale-free networks. They demonstrated this by applying evolutionary pressure on an initially random network which simulates a range of classic games, so that the network converges towards Nash equilibria while being allowed to re-wire. The networks become increasingly scale-free during this process.
In networked systems where competitive decision making takes place, game theory is often used to model system dynamics, and convergence towards equilibria can be considered as a driver of topological evolution. For example, Kasthurirathna and Piraveenan have shown that when individuals in a system display varying levels of rationality, improving the overall system rationality might be an evolutionary reason for the emergence of scale-free networks. They demonstrated this by applying evolutionary pressure on an initially random network which simulates a range of classic games, so that the network converges towards Nash equilibria while being allowed to re-wire. The networks become increasingly scale-free during this process.
在竞争性决策发生的网络系统中，博弈论经常被用来建模系统动力学，趋向均衡可以被认为是拓扑进化的驱动力。例如Kasthurirathna和Piraveenan<ref>{{cite journal |last1=Kasthurirathna|first1=Dharshana |last2=Piraveenan |first2=Mahendra. |title=Emergence of scale-free characteristics in socioecological systems with bounded rationality |journal=[[Scientific Reports (journal)|Scientific Reports]] |volume=In Press |date=2015}}</ref>表明，当一个系统中的个体表现出不同程度的理性时，提高整个系统的理性可能是无标度网络出现的进化原因。他们通过对一个最初的随机网络施加进化压力来模拟一系列经典博弈，当允许重新连接时，网络收敛到纳什均衡，从而证明了这一点。在这个过程中，网络变得越来越无标度。
|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 视演化网络为连续的静态网络快照===
===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 [[video|motion picture]]. Many simple parameters exist to describe a static network (number of nodes, edges, path length, connected components), or to describe specific nodes in the graph such as the number of links or the clustering coefficient. These properties can then individually be studied as a time series using signal processing notions. For example, we can track the number of links established to a server per minute by looking at the successive snapshots of the network and counting these links in each snapshot.
The most common way to view evolving networks is by considering them as successive static networks. This could be conceptualized as the individual still images which compose a motion picture. Many simple parameters exist to describe a static network (number of nodes, edges, path length, connected components), or to describe specific nodes in the graph such as the number of links or the clustering coefficient. These properties can then individually be studied as a time series using signal processing notions.<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. For example, we can track the number of links established to a server per minute by looking at the successive snapshots of the network and counting these links in each snapshot.
观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为组成电影的一个个静态图像。有许多简单的参数可以描述一个静态网络（节点数、边、路径长度、连通子图），或者描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性单独作为时间序列进行研究。
观察不断演化的网络最常用的方法是把它们看作连续的静态网络。这可以概念化为组成电影的一个个静态图像。有许多简单的参数可以描述一个静态网络（节点数、边、路径长度、连通子图），或者描述图中的特定节点，比如链接数或集聚系数。然后可以使用信号处理概念将这些属性单独作为时间序列进行研究。<ref name=EvolvingNetworksPDF>{{Cite journal| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf | author1 = Pierre Borgnat | author2 = Eric Fleury | title = Evolving Networks|display-authors=etal}}</ref> 例如，我们可以通过查看网络的连续快照并计算每个快照中的链接数量，来跟踪每分钟建立到服务器的链接数量。
| url = http://liris.cnrs.fr/Documents/Liris-3669.pdf
|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 定义动力学性质===
===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. Other similar properties can be defined and then it is possible to instead track these properties through the evolution of a network and visualize them directly.
It may be important to look at properties which cannot be directly observed by treating evolving networks as a sequence of snapshots, such as the duration of contacts between nodes. Other similar properties can be defined and then it is possible to instead track these properties through the evolution of a network and visualize them directly.
那些不能直接从将演化网络视为一系列快照中观察到的特性可能很重要，例如节点之间的接触时间。<ref name="Impact of human mobility on the design of opportunistic forwarding algorithms">{{Cite journal| url = http://www.cl.cam.ac.uk/~ph315/publications/PID158626.pdf | author1 = A. Chaintreau | author2 = P. Hui | author3 = J. Crowcroft | author4 = C. Diot | author5 = R. Gass | author6 = J. Scott | journal = Infocom | year = 2006 | title = Impact of human mobility on the design of opportunistic forwarding algorithms}}</ref>可以定义其他类似的属性，然后可以通过网络的演化来跟踪这些属性，并直接可视化它们。
Another issue with using successive snapshots is that only slight changes in network topology can have large effects on the outcome of algorithms designed to find communities. Therefore, it is necessary to use a non classical definition of communities which permits following the evolution of the community through a set of rules such as birth, death, merge, split, growth, and contraction.
Another issue with using successive snapshots is that only slight changes in network topology can have large effects on the outcome of algorithms designed to find communities. Therefore, it is necessary to use a non classical definition of communities which permits following the evolution of the community through a set of rules such as birth, death, merge, split, growth, and contraction.
使用连续快照的另一个问题是，在网络拓扑中微小的变化可以对用于寻找网络社团的算法的结果产生巨大的影响。因此，有必要使用一个非经典的社团定义，它允许通过一系列的规则，如出生、死亡、合并、分裂、生长和收缩，来跟随社团的演化。<ref name="Quantifying social group evolution">{{Cite journal| author1 = G. Palla | author2 = A. Barabasi | author3 = T. Vicsek | title = Quantifying social group evolution | journal = Nature | volume = 446 | pages = 664–667 | year = 2007 | author4 = Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng | issue=7136 | doi=10.1038/nature05670|pmid = 17410175|arxiv = 0704.0744 |bibcode = 2007Natur.446..664P }}</ref><ref name="Structural and temporal analysis of the blogosphere through community factorization">{{Cite book| url = http://portal.acm.org/ft_gateway.cfm? | author1 = Y. Chi, S. Zhuid=1281213&type=pdf | author2 = X. Song | author3 = J. Tatemura | author4 = B.L. Tseng | title = Structural and temporal analysis of the blogosphere through community factorization | journal = KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining | pages = 163–172 | year = 2007| doi = 10.1145/1281192.1281213 | citeseerx = 10.1.1.69.6959 | isbn = 9781595936097 }}</ref>
| author1 = G. Palla
|pmid = 17410175|arxiv = 0704.0744 |bibcode = 2007Natur.446..664P }}</ref><ref name="Structural and temporal analysis of the blogosphere through community factorization">{{Cite book
| url = http://portal.acm.org/ft_gateway.cfm?id=1281213&type=pdf
| doi = 10.1145/1281192.1281213
==Applications 应用==
==Applications 应用==
2009年世界预定商业航空交通路线图。这个网络随着新路线的计划或取消而不断演变。
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.
Almost all real world networks are evolving networks since they are constructed over time. By varying the respective probabilities described above, it is possible to use the expanded BA model to construct a network with nearly identical properties as many observed networks.
几乎所有真实世界的网络都是不断演化的网络，因为它们是随着时间的推移而构建的。通过改变上述各自的概率，可以使用扩展的BA模型来构造一个具有与许多观测网络几乎相同属性的网络。<ref name="Networks in life: scaling properties and eigenvalue spectra">{{Cite journal |url = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf |author1 = I. Farkas |author2 = I. Derenyi |author3 = H. Heong |title = Networks in life: scaling properties and eigenvalue spectra |journal = [[Physica A|Physica]] |volume = 314 |issue = 1–4 |pages = 25–34 |year = 2002 |arxiv = cond-mat/0303106 |bibcode = 2002PhyA..314...25F |doi = 10.1016/S0378-4371(02)01181-0 |display-authors = etal |access-date = 2011-04-21 |archive-url = https://web.archive.org/web/20111004050804/http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf |archive-date = 2011-10-04 |url-status = dead}}</ref>
Moreover, the concept of scale free networks shows us that time evolution is a necessary part of understanding the network's properties, and that it is difficult to model an existing network as having been created instantaneously. Real evolving networks which are currently being studied include [[social networks]], [[telecommunications network|communications networks]], the [[internet]], the [[Six Degrees of Kevin Bacon|movie actor network]], the [[world wide web]], and [[Transport network|transportation network]]s.
Moreover, the concept of scale free networks shows us that time evolution is a necessary part of understanding the network's properties, and that it is difficult to model an existing network as having been created instantaneously. Real evolving networks which are currently being studied include social networks, communications networks, the internet, the movie actor network, the world wide web, and transportation networks.
此外，无标度网络的概念告诉我们，时间演化是理解网络属性的必要组成部分，而且很难将现有网络模型化为瞬间创建的。目前正在研究的演化网络包括社交网络、通信网络、互联网、电影演员网络、万维网和交通网络。
此外，无标度网络的概念告诉我们，时间演化是理解网络属性的必要组成部分，而且很难将现有网络模型化为瞬间创建的。目前正在研究的演化网络包括社交网络、通信网络、互联网、电影演员网络、万维网和交通网络。