“WS小世界模型”的版本间的差异
（→模型基本原理） |
（→算法） |
||
| 第32行： | 第32行： | ||
==算法== | ==算法== | ||
| − | 假设所期望的节点数为<math>N</math>，平均度为<math>K</math> | + | 假设所期望的节点数为<math>N</math>，平均度为<math>K</math>（假定<math>K</math>为偶数）和一个特殊的参数<math>\beta</math> ，满足<math>0\leq \beta \leq 1</math>，且<math>N\gg K\gg lnN\gg 1</math>。 |
| 第38行： | 第38行： | ||
#构建一个正则环点阵。该图有<math>N</math>个节点，每个节点和<math>K</math>个相邻的节点相连，其中每一侧有<math>K/2</math>个。即是，若每个节点用<math>n_{0},...,n_{N-1}</math>标示，当且仅当<math>0< \left | i-j \right |\mod(N-1-\frac{K}{2})\leq \frac{K}{2}</math>时，存在边<math>(n_{i},n_{j})</math>。 | #构建一个正则环点阵。该图有<math>N</math>个节点，每个节点和<math>K</math>个相邻的节点相连，其中每一侧有<math>K/2</math>个。即是，若每个节点用<math>n_{0},...,n_{N-1}</math>标示，当且仅当<math>0< \left | i-j \right |\mod(N-1-\frac{K}{2})\leq \frac{K}{2}</math>时，存在边<math>(n_{i},n_{j})</math>。 | ||
#对于每个节点<math>n_{i}=n_{0},...,n_{N-1}</math>，选出其与最右侧第<math>K/2</math>相邻节点之间的边，即满足<math>n_{i} < n_{j} \leq n_{i} + K/2</math>的所有边 <math>(n_{i},n_{j}\mod N)</math> ，以概率<math>\beta</math>将其重新连接。重新连接的过程是把边 <math>(n_{i},n_{j}\mod N)</math> 替换为边 <math>(n_{i},n_{k})</math> ，其中<math>k</math>以一致的随机性从所有可能的节点选出，并且避免出现自回路<math>(k\neq i)</math>和重复连接（边 <math>(n_{i},n_{{k}'})</math> ，其中<math>{k}'=k</math>，在该算法中不会出现）的情况。 | #对于每个节点<math>n_{i}=n_{0},...,n_{N-1}</math>，选出其与最右侧第<math>K/2</math>相邻节点之间的边，即满足<math>n_{i} < n_{j} \leq n_{i} + K/2</math>的所有边 <math>(n_{i},n_{j}\mod N)</math> ，以概率<math>\beta</math>将其重新连接。重新连接的过程是把边 <math>(n_{i},n_{j}\mod N)</math> 替换为边 <math>(n_{i},n_{k})</math> ，其中<math>k</math>以一致的随机性从所有可能的节点选出，并且避免出现自回路<math>(k\neq i)</math>和重复连接（边 <math>(n_{i},n_{{k}'})</math> ，其中<math>{k}'=k</math>，在该算法中不会出现）的情况。 | ||
| − | |||
==特性== | ==特性== | ||
2020年5月6日 (三) 20:39的版本
WS小世界模型 Watts–Strogatz model 是一种随机图生成模型，其生成的图具有小世界属性，包括较短的平均节点间距离 average path length和高集聚系数clustering coefficient。该模型由邓肯·瓦茨 Duncan J. Watts和史蒂夫·斯托加茨 Steven Strogatz在1998年两人联合发表于《自然 Nature》的论文中提出 [1] 。Watts在其广受欢迎的科学读物《Six Degrees》中使用[math]\displaystyle{ \beta }[/math]来阐述该模型，这之后，该模型也被称为（沃茨）[math]\displaystyle{ \beta }[/math] 模型。
模型基本原理
对随机图的正式研究可追溯至 保尔·厄多斯 Paul Erdős和阿尔弗烈德·瑞利 Alfréd Rényi的工作 [2] 。他们所考虑的图，也就是现在所谓的经典图或ER随机图模型，给许多应用提供了简单而强有力的模型。
但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性：
- 不能生成局部集聚 local clustering 和三元闭合 triadic closures(网络有三元闭合、三元闭包等释义）。相反，因为图中两个节点有恒定、随机且独立的概率彼此相连，ER随机图模型的集聚系数较低。
- 不能解释中心节点 hub 的构成。在形式上，ER随机图模型的度分布收敛于泊松分布 Poisson distribution ，而不是我们在现实世界中观测到的、无标度网络 scale-free networks 的幂律分布 power law[3]
WS模型是针对于第一条局限性来设计的最简可能模型。它在解释了集聚的同时保持了ER模型较短的平均节点间距离，这是通过在近似ER图的随机化结构和正则环点阵 regular ring lattice中进行内插得到的。因而，该模型至少能够部分解释许多网络中的“小世界”现象 "small-world" phenomena，比如电网、秀丽隐杆线虫 C. elegans的神经网络、电影演员的社交网络、以及芽殖酵母脂肪代谢的信息交流
[4]
。
算法
假设所期望的节点数为[math]\displaystyle{ N }[/math]，平均度为[math]\displaystyle{ K }[/math]（假定[math]\displaystyle{ K }[/math]为偶数）和一个特殊的参数[math]\displaystyle{ \beta }[/math] ，满足[math]\displaystyle{ 0\leq \beta \leq 1 }[/math]，且[math]\displaystyle{ N\gg K\gg lnN\gg 1 }[/math]。
该模型以下述方式构建了一个具有[math]\displaystyle{ N }[/math]个节点，[math]\displaystyle{ \frac{NK}{2} }[/math]条边的无向图：
- 构建一个正则环点阵。该图有[math]\displaystyle{ N }[/math]个节点，每个节点和[math]\displaystyle{ K }[/math]个相邻的节点相连，其中每一侧有[math]\displaystyle{ K/2 }[/math]个。即是，若每个节点用[math]\displaystyle{ n_{0},...,n_{N-1} }[/math]标示，当且仅当[math]\displaystyle{ 0\lt \left | i-j \right |\mod(N-1-\frac{K}{2})\leq \frac{K}{2} }[/math]时，存在边[math]\displaystyle{ (n_{i},n_{j}) }[/math]。
- 对于每个节点[math]\displaystyle{ n_{i}=n_{0},...,n_{N-1} }[/math]，选出其与最右侧第[math]\displaystyle{ K/2 }[/math]相邻节点之间的边，即满足[math]\displaystyle{ n_{i} \lt n_{j} \leq n_{i} + K/2 }[/math]的所有边 [math]\displaystyle{ (n_{i},n_{j}\mod N) }[/math] ，以概率[math]\displaystyle{ \beta }[/math]将其重新连接。重新连接的过程是把边 [math]\displaystyle{ (n_{i},n_{j}\mod N) }[/math] 替换为边 [math]\displaystyle{ (n_{i},n_{k}) }[/math] ，其中[math]\displaystyle{ k }[/math]以一致的随机性从所有可能的节点选出，并且避免出现自回路[math]\displaystyle{ (k\neq i) }[/math]和重复连接（边 [math]\displaystyle{ (n_{i},n_{{k}'}) }[/math] ，其中[math]\displaystyle{ {k}'=k }[/math]，在该算法中不会出现）的情况。
特性
该模型基础的点阵图结构产生了局部集聚的网络，而随机的重新连接则大大减少了平均节点间距离。其算法引入了大约[math]\displaystyle{ \beta \tfrac{NK}{2} }[/math]条非点阵边。改变[math]\displaystyle{ \beta }[/math]的值可以在正则环点阵（[math]\displaystyle{ \beta =0 }[/math]）和接近ER随机图的结构[math]\displaystyle{ (\beta = }[/math][math]\displaystyle{ 1 }[/math]，[math]\displaystyle{ G }[/math][math]\displaystyle{ (N,p) }[/math]满足[math]\displaystyle{ p=\frac {K}{N-1}) }[/math]间进行内插。由于每一个节点都与至少[math]\displaystyle{ K/2 }[/math]个其他节点相连，该模型并没符合真实的ER模型。
我们感兴趣的三个特性是平均节点间距离、集聚系数和度分布。
平均节点间距离
- 对于环形点阵，平均节点间距离是[math]\displaystyle{ \ell(0)=N/2K\gg 1 }[/math]，且随系统规模线性变化；
- 对于极限情况[math]\displaystyle{ (\beta \rightarrow 1) }[/math]，该图趋近于随机图，平均节点间距离[math]\displaystyle{ \ell(1)=\frac{lnN}{lnK} }[/math]，但实际上不收敛于此；
- 在区间[math]\displaystyle{ (0\lt \beta \lt 1) }[/math]内，平均节点间距离随着[math]\displaystyle{ \beta }[/math]的增大迅速下降，并很快接近于其极限值。
集聚系数
- 对于环形点阵，集聚系数[5] 为[math]\displaystyle{ C(0)=\frac{3(K-2)}{4(K-1)} }[/math]，因此随着K的增大趋向于[math]\displaystyle{ 3/4 }[/math]，且与系统规模无关；
- 对于[math]\displaystyle{ \beta \rightarrow 1 }[/math]的极限情况，集聚系数与经典随机图同阶，[math]\displaystyle{ C=\frac{K}{N-1} }[/math]，与系统规模成反比；区间内的集聚系数则十分接近于正则环点阵的系数值，只有在[math]\displaystyle{ \beta }[/math]相对较大时才会下降，这就导致了在一定区间范围内平均节点间距离下降迅速，而集聚系数保持相对恒定的情形，也就解释了“小世界”现象。
- 如果我们用巴拉特 Barrat和魏格特 Weigt的方法[6]，即是用一个节点的相邻节点之间的平均边数和这些相邻节点之间可能的平均边数之商来定义集聚系数[math]\displaystyle{ C'(\beta) }[/math]，或者说:
- [math]\displaystyle{ C'(\beta)=\frac{3\times \text{number of triangles}}{\text{number of connected triples}} }[/math]
- 可得出[math]\displaystyle{ C'(\beta)\sim C(0)(1-\beta)^{3} }[/math]
度分布
- 正则环点阵的度分布即以K为中心的狄拉克[math]\displaystyle{ \delta }[/math]函数，在[math]\displaystyle{ 0\lt \beta \lt 1 }[/math]内的度分布可记为：
- [math]\displaystyle{ P(k) = \sum_{n=0}^{f(k,K)} {{K/2}\choose{n}} (1-\beta)^n \beta^{K/2-n} \frac{(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!} e^{-\beta K/2} }[/math]
- [math]\displaystyle{ k_{i} }[/math]是第[math]\displaystyle{ i }[/math]个节点的边数或称为度。这里[math]\displaystyle{ k\geq K/2 }[/math]，[math]\displaystyle{ f(k,K)=min(k-K/2,K/2) }[/math]。
- 度分布的形状类似于随机图，在[math]\displaystyle{ k }[/math][math]\displaystyle{ = }[/math][math]\displaystyle{ K }[/math]处取得明显峰值，对于较大的[math]\displaystyle{ \left | k-K\right | }[/math]呈指数衰减。
- 网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。
局限性
该模型的主要局限性是会产生不符实际的度分布。相较而言，现实中的网络通常是非齐次的无标度网络，有中心节点的存在和无标度的度分布。考虑到此，这样的网络可以用偏好依附模型 preferential attachment model来更好的描述，比如BA网络模型。（另一方面，BA模型没有产生真实网络中出现的高集聚特性，而这个弱点是WS模型所不具备的。因此，WS模型和BA模型均不应被看成是完全符合实际的。）WS模型也暗含了固定的节点数，所以也不能用来描述网络的生长。
参见
参考文献
- ↑ Watts, D. J.; Strogatz, S. H. (1998). "Collective dynamics of 'small-world' networks" (PDF). Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998.
- ↑ Erdos, P. (1960). "Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Math. Inst. Hung. Acad. Sci. 5: 17.
- ↑ Ravasz, E. (30 August 2002). "Hierarchical Organization of Modularity in Metabolic Networks". Science. 297 (5586): 1551–1555. arXiv:cond-mat/0209244. Bibcode:2002Sci...297.1551R. doi:10.1126/science.1073374. PMID 12202830.
- ↑ Al-Anzi, Bader; Arpp, Patrick; Gerges, Sherif; Ormerod, Christopher; Olsman, Noah; Zinn, Kai (2015). "Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network". PLOS Computational Biology. 11 (5): e1004264. Bibcode:2015PLSCB..11E4264A. doi:10.1371/journal.pcbi.1004264. PMC 4447291. PMID 26020510.
- ↑ Albert, R., Barabási, A.-L. (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74 (1): 47–97. arXiv:cond-mat/0106096. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ↑ Barrat, A.; Weigt, M. (2000). "On the properties of small-world network models". European Physical Journal B. 13 (3): 547–560. arXiv:cond-mat/9903411. doi:10.1007/s100510050067.
编者推荐
书籍推荐
复杂网络理论及其应用
《复杂网络理论及其应用》由汪小帆，李翔，陈关荣联袂编著，是一本致力于系统地介绍复杂网络的基础知识和研究进展经典书籍。本书系统地介绍复杂网络的基础知识和研究进展。由于复杂网络研究具有很强的跨学科特色，并且新的问题和研究成果不断涌现，因此本书着眼于复杂网络研究中已经取得的主要研究进展。
文献推荐
小世界网络的集体动力学 Collective dynamics of ‘small-world’ networks
该文章于在1998年发表于 Nature，首次提出“小世界网络”的数学模型，并引起了来自社会科学、信息科学和自然科学等领域对这一模型的关注和应用。本文主要从数学上定义了小世界网络，对模型的全局性质和局部性质进行定量分析，并将其特征与现实生活中的例子联系。作者还通过分析简化的传染病传播模型，试图推广这一数学模型在动力学过程研究中的应用。
课程推荐
复杂网络2020
本课程是对复杂性科学的一个概述，包含10个章节，每节都会涵盖复杂系统的一个主要概念。
集智相关文章
从复杂网络小世界、无标度、高聚类特性看新型冠状病毒肺炎
这篇文章的提纲于2020年1月22日（武汉封城的前一天）发在科学网。基于复杂网络最基本的三大特点——小世界、无标度、高聚类，来分析新型冠状病毒肺炎这一场突如其来的灾难。文章指出，现代化交通工具是一把双刃剑，让世界变得越来越小的同时也让疾病传播变得更加容易；无标度特性表明采用隔离和切断传播途径是遏制疾病传播最有效的方法，警惕超级传播者的出现；潜伏期（传播时滞）给发现和切断传播途径带来的困难；社会网络高聚类系数使得新型肺炎的传播具有很强的聚集性。目前来看，利用复杂网络理论来指导抗击新冠疾病具有极其重要的现实意义。
本中文词条由用户Iceblaze9527参与编译，flynn审校，张江总审校，乐多多编辑，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。