198
个编辑
更改
跳到导航
跳到搜索
第397行：
第397行： + + + + + + + + +
→Watts–Strogatz 小世界模型
=== Watts–Strogatz 小世界模型 ===
=== Watts–Strogatz 小世界模型 ===
[[File:Watts-Strogatz-rewire.png|thumb|The [[Watts and Strogatz model]] uses the concept of rewiring to achieve its structure. The model generator will iterate through each edge in the original lattice structure. An edge may changed its connected vertices according to a given rewiring probability. <math>\langle k\rangle = 4</math> in this example.]]
The [[Watts and Strogatz model]] is a random graph generation model that produces graphs with [[small-world properties]].
[[File:Watts-Strogatz-rewire.png|thumb|[[Watts–Strogatz 模型]]利用重连接的概念构造小世界网络结构。模型生成器会遍历初始的规则网络的所有边，每一条边会以给定的重连接概率改变它两端的节点，例如<math>\langle k\rangle = 4</math>。]]
[[File:Watts-Strogatz-rewire.png|thumb|[[Watts–Strogatz 模型]]利用重连接的概念构造小世界网络结构。模型生成器会遍历初始的规则网络的所有边，每一条边会以给定的重连接概率改变它两端的节点，例如<math>\langle k\rangle = 4</math>。]]
[[Watts–Strogatz 模型]]是一个随机图生成模型，能够产生具有[[小世界性质]]的网络。
[[Watts–Strogatz 模型]]是一个随机图生成模型，能够产生具有[[小世界性质]]的网络。
An initial lattice structure is used to generate a Watts–Strogatz model. Each node in the network is initially linked to its <math>\langle k\rangle</math> closest neighbors. Another parameter is specified as the rewiring probability. Each edge has a probability <math>p</math> that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is <math>pE = pN\langle k\rangle/2</math>.
Watts–Strogatz 模型在一个初始的规则网络的基础上生成，初始网络中每个节点与它的<math>\langle k\rangle</math>个最近邻节点连接。给定另外一个参数重连接概率，每条边以<math>p</math>的概率在图中随机重连。该模型中重连接边数的期望值为<math>pE = pN\langle k\rangle/2</math>。
Watts–Strogatz 模型在一个初始的规则网络的基础上生成，初始网络中每个节点与它的<math>\langle k\rangle</math>个最近邻节点连接。给定另外一个参数重连接概率，每条边以<math>p</math>的概率在图中随机重连。该模型中重连接边数的期望值为<math>pE = pN\langle k\rangle/2</math>。
As the Watts–Strogatz model begins as non-random lattice structure, it has a very high clustering coefficient along with high average path length. Each rewire is likely to create a shortcut between highly connected clusters. As the rewiring probability increases, the clustering coefficient decreases slower than the average path length. In effect, this allows the average path length of the network to decrease significantly with only slightly decreases in clustering coefficient. Higher values of p force more rewired edges, which in effect makes the Watts–Strogatz model a random network.
由于Watts–Strogatz 模型的初始网络具有非随机的规则结构，它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率<math>p</math>会导致更多的边重新连接，这实际上使Watts Strogatz模型趋于随机网络。
由于Watts–Strogatz 模型的初始网络具有非随机的规则结构，它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率<math>p</math>会导致更多的边重新连接，这实际上使Watts Strogatz模型趋于随机网络。