330
个编辑
更改
无编辑摘要
|description=小世界模型，集智
|description=小世界模型，集智
}}
}}
[[File:小世界网络图1.png|200px|缩略图|右|小世界网络的例子 中心比其他节点大 平均[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]3.833 平均最短路径长度1.803 [https://en.wikipedia.org/wiki/Clustering_coefficient 聚类系数]0.522]]
[[File:小世界网络图2.png|200px|缩略图|右|随机图 平均[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]2.833 平均最短路径长度2.109 [https://en.wikipedia.org/wiki/Clustering_coefficient 聚类系数]0.167]]
'''小世界网络'''是一种[https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) 数学图]。在此类图中，绝大多数节点彼此之间并不相邻，但任一给定节点的邻居们却很可能彼此是邻居，并且大多数节点都可以从任意其他节点，用较少的步或跳跃访问到。具体来说，小世界网络的定义如下：如果网络中随机选择的两个节点之间的距离<i>L</i>（即访问彼此所需要的步数），与网络中节点数量<i>N</i>的对数成比例增长，（即<ref name="a1">http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html</ref>: <math>L \propto \log N</math>），且网络的[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]（Clustering Coefficient）不小，那么，这样的网络就是小世界网络。在社交网络中，这种网络属性意味着一些彼此并不相识的人，可以通过一条很短的[https://en.wikipedia.org/wiki/Acquaintance 熟人]链条被联系在一起，这也就是[[小世界现象]]。许多经验网络图都展示出了[[小世界现象]]，例如[https://en.wikipedia.org/wiki/Social_networks 社交网络]、[https://en.wikipedia.org/wiki/Internet 互联网]的底层架构、诸如Wikipedia的百科类网站以及[https://en.wikipedia.org/wiki/Gene_regulatory_network 基因网络]等等。
1998年，[https://en.wikipedia.org/wiki/Duncan_J._Watts Duncan Watts]和[https://en.wikipedia.org/wiki/Steven_Strogatz Steven Strogatz]提出，小世界网络是一类[https://en.wikipedia.org/wiki/Random_graph 随机图]<ref name="a2">Watts, Duncan J.; [https://en.wikipedia.org/wiki/Steven_Strogatz Strogatz, Steven H.] (June 1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. [https://en.wikipedia.org/wiki/Bibcode Bibcode]:[http://adsabs.harvard.edu/abs/1998Natur.393..440W 1998Natur.393..440W]. [https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[https://doi.org/10.1038/30918 10.1038/30918]. [https://en.wikipedia.org/wiki/PubMed_Identifier PMID] [https://www.ncbi.nlm.nih.gov/pubmed/9623998 9623998]. Papercore Summary http://www.papercore.org/Watts1998</ref>。他们指出，这类网络图可以通过两个独立的结构特征，即[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]和平均节点间[https://en.wikipedia.org/wiki/Distance_(graph_theory) 距离]（也称作平均[https://en.wikipedia.org/wiki/Shortest_path 最短路径]长度）来进行识别。根据[https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős-Rényi（ER）]模型构造的纯随机图，会展现出较小的最短路径长度（通常随着节点数对数值的变化而变化）以及较小的集聚系数。[https://en.wikipedia.org/wiki/Duncan_J._Watts Watts]和[https://en.wikipedia.org/wiki/Steven_Strogatz Strogatz]验证了这一点，事实上，现实世界中很多网络的平均最短路径长度都较短，而集聚系数又远高于普通随机图。Watts和Strogatz随后提出了一种新的图模型（即现在的[https://en.wikipedia.org/wiki/Watts_and_Strogatz_model Watts-Strogatz模型]），该模型具备两个特征：(1)平均最短路径长度较小，(2)集聚系数较大。1999年，Barthelemy和Amaral最先描述出了Watts-Strogatz模型中“大世界”（诸如栅格网络）与小世界的交叉点性质<ref name="a3">#Barthelemy, M.; Amaral, LAN (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82 (15): 3180–3183. [https://en.wikipedia.org/wiki/ArXiv arXiv]:[https://arxiv.org/abs/cond-mat/9903108 cond-mat/9903108]. Bibcode:1999PhRvL..82.3180B. doi:10.1103/PhysRevLett.82.3180.</ref>。在此之后，学界又涌现出了大量的相关研究，其中不乏一些较为精确的度量结果 (Barrat and Weigt, 1999; Dorogovtsev and [https://en.wikipedia.org/wiki/Jos%C3%A9_Fernando_Ferreira_Mendes Mendes]; Barmpoutis and Murray, 2010)。 Braunstein发现<ref name="a4">#Braunstein, Lidia A.; Buldyrev, Sergey V.; Cohen, Reuven; Havlin, Shlomo; Stanley, H. Eugene (2003). "Optimal Paths in Disordered Complex Networks". Physical Review Letters. 91 (16). arXiv:cond-mat/0305051 Freely accessible. Bibcode:2003PhRvL..91p8701B. doi:10.1103/PhysRevLett.91.168701. ISSN 0031-9007.</ref>，对于权值分布非常广的加权ER网络，最佳路径长度会显著增长，其增长速度为<math>N^{\frac{1}{3}}</math>.
'''WS小世界模型 Watts–Strogatz model '''是一种[[随机图]]生成模型，其生成的图具有[[小世界属性]]，包括较短的平均节点间距离 average path length和高集聚系数clustering coefficient。该模型由[[邓肯·瓦茨 Duncan J. Watts]]和[[史蒂夫·斯托加茨 Steven Strogatz]]在1998年两人联合发表于《Nature》的论文中提出
'''WS小世界模型 Watts–Strogatz model '''是一种[[随机图]]生成模型，其生成的图具有[[小世界属性]]，包括较短的平均节点间距离 average path length和高集聚系数clustering coefficient。该模型由[[邓肯·瓦茨 Duncan J. Watts]]和[[史蒂夫·斯托加茨 Steven Strogatz]]在1998年两人联合发表于《Nature》的论文中提出
<ref name=WS>{{Cite journal | last1 = Watts | first1 = D. J. | authorlink1 = | last2 = Strogatz | first2 = S. H. | authorlink2 = | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 440–442 | doi = 10.1038/30918 | year = 1998 | url = http://worrydream.com/refs/Watts-CollectiveDynamicsOfSmallWorldNetworks.pdf | pmid = 9623998 | pmc = | bibcode = 1998Natur.393..440W }}</ref>
<ref name=WS>{{Cite journal | last1 = Watts | first1 = D. J. | authorlink1 = | last2 = Strogatz | first2 = S. H. | authorlink2 = | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 440–442 | doi = 10.1038/30918 | year = 1998 | url = http://worrydream.com/refs/Watts-CollectiveDynamicsOfSmallWorldNetworks.pdf | pmid = 9623998 | pmc = | bibcode = 1998Natur.393..440W }}</ref>