| 第3行： |
第3行： |
| | |description=小世界模型，集智 | | |description=小世界模型，集智 |
| | }} | | }} |
| − | [[File:图上.png|200px|缩略图|右|小世界网络的例子 中心比其他节点大 平均[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]3.833 平均最短路径长度1.803 [https://en.wikipedia.org/wiki/Clustering_coefficient 聚类系数]0.522]]
| |
| − | [[File:图下.png|200px|缩略图|右|随机图 平均[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]2.833 平均最短路径长度2.109 [https://en.wikipedia.org/wiki/Clustering_coefficient 聚类系数]0.167]]
| |
| − | '''WS小世界模型 Watts–Strogatz model '''是一种[[随机图]]生成模型，其生成的图具有[[小世界属性]]，包括较短的平均节点间距离 average path length和高集聚系数clustering coefficient。在此类图中，绝大多数节点彼此之间并不相邻，但任一给定节点的邻居们却很可能彼此是邻居，并且大多数节点都可以从任意其他节点，用较少的步或跳跃访问到。具体来说，小世界网络的定义如下：如果网络中随机选择的两个节点之间的距离<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 基因网络]等等。
| |
| | | | |
| | 该模型由[[邓肯·瓦茨 Duncan J. Watts]]和[[史蒂夫·斯托加茨 Steven Strogatz]]在1998年两人联合发表于《Nature》的论文中提出 | | 该模型由[[邓肯·瓦茨 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> |
| − | 。他们指出，这类网络图可以通过两个独立的结构特征，即[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在其广受欢迎的科学读物[https://en.wikipedia.org/wiki/Six_Degrees:_The_Science_of_a_Connected_Age 《Six Degrees》]中使用<math>\beta</math>来阐述该模型，这之后，该模型也被称为（沃茨）<math>\beta</math> 模型。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>.
| + | 。Watts和Strogatz随后提出了一种新的图模型（即现在的[https://en.wikipedia.org/wiki/Watts_and_Strogatz_model Watts-Strogatz模型]），该模型具备两个特征：(1)平均最短路径长度较小， |
| | | | |
| | | | |
| 第42行： |
第39行： |
| | #构建一个正则环点阵。该图有<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>，在该算法中不会出现）的情况。 |
| − | ==构建小世界网络==
| |
| − |
| |
| − |
| |
| − | 构建小世界网络的主要机制是[https://en.wikipedia.org/wiki/Watts_and_Strogatz_Model Watts-Strogatz机制]。
| |
| − |
| |
| − | 小世界网络也可引入延时<ref name="a18">#X. S. Yang, Fractals in small-world networks with time-delay, Chaos, Solitons & Fractals, vol. 13, 215–219 (2002)
| |
| − | </ref>，这不仅会产生分形，而且在特定条件下，还会形成混沌<ref name="a19">#X. S. Yang, Chaos in small-world networks, Phys. Rev. E 63, 046206 (2001)
| |
| − | </ref>，或者在动态网络中转变为混沌<ref name="a20">#W. Yuan, X. S. Luo, P. Jiang, B. Wang, J. Fang, Transition to chaos in small-world dynamical network
| |
| − | </ref>。
| |
| − |
| |
| − | 构造[https://en.wikipedia.org/wiki/Degree_diameter 度直径图]（Degree–diameter graph）的方法是：网络中每个顶点的邻居数量是有界的，而网络中从任意给定顶点到其他顶点（网络[https://en.wikipedia.org/wiki/Distance_(graph_theory) 直径]）是最小的。构建这样的小世界网络，其实是为寻找临近[https://en.wikipedia.org/wiki/Moore_graph 摩尔边界]的图的秩，而做出的一部分努力。
| |
| − |
| |
| − | Barmpoutis等人给出的从零开始构建小世界网络的另外一种方法<ref name="a21">#[https://en.wikipedia.org/wiki/D.Barmpoutis_and_R.M._Murray D.Barmpoutis and R.M. Murray] (2010). "Networks with the Smallest Average Distance and the Largest Average Clustering". arXiv:1007.4031 Freely accessible [q-bio.MN].</ref>，构建了一种平均距离极小且平均集聚度极高的网络。他们提到了一种复杂度恒定的快速算法，以及不同生成图鲁棒性的度量。根据每个网络的应用，可以从一个这样的“超小世界”网络开始，然后重新连接一些边，或者使用几个这样的小网络作为子图，构筑一个更大的图。
| |
| − |
| |
| − | 通过[https://en.wikipedia.org/wiki/Dual-phase_evolution 双相演化](dual-phase evolution)过程，小世界属性可以在社交网络和其他现实世界系统中自然产生。在顶点之间的连接增长受到时间或空间的制约时，小世界网络尤其常见。该机制通常涉及相位之间的周期性变换，其中，在“全局”阶段——连接建立，而在“本地”阶段——连接被移除。
| |
| − |
| |
| − | 参考：[https://en.wikipedia.org/wiki/Diffusion-limited_aggregation 扩散限制凝聚]，[https://en.wikipedia.org/wiki/Pattern_formation 模式构成]。
| |
| − |
| |
| − | === 代码实现 ===
| |
| − | ==== 使用networkx生成小世界网络 ====
| |
| − | <syntaxhighlight lang="python">
| |
| − |
| |
| − | import networkx as nx
| |
| − | import matplotlib.pyplot as plt
| |
| − |
| |
| − | # WS network
| |
| − | # 生成20个节点的小世界网络
| |
| − | # 每个节点有四个邻居
| |
| − | # 每条连边以0.3的概率随机重置链接
| |
| − | WS = nx.random_graphs.watts_strogatz_graph(20, 4, 0.3)
| |
| − | pos = nx.circular_layout(WS)
| |
| − | nx.draw(WS, pos, with_labels = False, node_size = 30)
| |
| − | plt.show()
| |
| − |
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | 此时得到的图片是下图所示:<br />
| |
| − | [[File:图1.png|400px]]
| |
| − |
| |
| − |
| |
| − | ====使用原生方法x生成小世界网络====
| |
| − | <syntaxhighlight lang="python">
| |
| − | G = nx.Graph()
| |
| − | node_num = 20
| |
| − | neighbour_num = 4
| |
| − | probility = 0.3
| |
| − | # 节点与邻居相连
| |
| − | for i in range(node_num):
| |
| − | from_node = i
| |
| − | for j in range(neighbour_num):
| |
| − | to_node = (i+j) % node_num - neighbour_num / 2
| |
| − | if to_node >= 0:
| |
| − | to_node += 1
| |
| − | G.add_edge(from_node,to_node)
| |
| − | # 连边随机重连
| |
| − | edges = copy.deepcopy(G.edges())
| |
| − | for edge in edges:
| |
| − | if random.random() < probility:
| |
| − | G.remove_edge(edge[0],edge[1])
| |
| − | ran_edge = np.random.randint(node_num,size=2).tolist()
| |
| − | G.add_edge(ran_edge[0],ran_edge[1])
| |
| − | # 绘图
| |
| − | pos = nx.circular_layout(G)
| |
| − | nx.draw(G, pos, with_labels = False, node_size = 30)
| |
| − | plt.show()
| |
| − | </syntaxhighlight>
| |
| − |
| |
| − | 此时得到的图片如下图所示：
| |
| − | <br />
| |
| − | [[File:图2.png|400px]]
| |
| − |
| |
| − | ==小世界网络的性质==
| |
| − |
| |
| − | 小世界网络中往往会包含[https://en.wikipedia.org/wiki/Clique_(graph_theory) 团]（cliques）以及临近团（near-cliques）——此处的“团”，指的是内部几乎任意两个节点之间都存在连接的子网络。这遵循[https://en.wikipedia.org/wiki/Clustering_coefficient 高集聚系数]的定义属性。其次，大多数节点对之间，都至少存在一条短路径。这遵循平均最短路径较小的定义属性。许多其他属性，通常也会与小世界网络有所关联。通常情况下，网络中会存在很多的中心（hub）——它们是具有很高连接数的节点（即高[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]（Degree）节点）。这些中心扮演了公共连接的角色，缩短了其他边之间的短路径长度。通过对比，航空航班的小世界网络，都体现出了较短的平均路径长度（例如，在任意两个城市之间飞行，你通常可能只需要乘坐三程或更少的航班数），因为很多航线都可以通过枢纽城市进行中转。这一属性的分析，通常要考虑网络中，具有相同入度的节点的比例（网络的度的分布）。网络具有较多中心（hub），意味着度值较大的节点占比会更高，因此，在这种网络的度分布中，高度值分布更高，即俗称的[https://en.wikipedia.org/wiki/Fat-tailed_distribution 厚尾分布]（fat-tailed distribution）。具有不同拓扑结构的图，只要满足上述两个定义，就可以被定义为小世界网络。
| |
| − |
| |
| − | 网络的小世界性被量化为一个系数 σ，可以通过比较给定网络与具备相同度分布的等价网络的集聚系数与路径长度，计算得出<ref name="a5">#The brainstem reticular formation is a small-world, not scale-free, network M. D. Humphries, K. Gurney and T. J. Prescott, Proc. Roy. Soc. B 2006 273, 503–511, doi:10.1098/rspb.2005.3354</ref><ref name="a6">#Humphries and Gurney (2008). "[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2323569 Network 'Small-World-Ness': A Quantitative Method for Determining Canonical Network Equivalence]". PLOS ONE. 3 (4): e0002051. doi:10.1371/journal.pone.0002051. PMC 2323569 Freely accessible. PMID 18446219.</ref>。
| |
| − |
| |
| − | <math>\sigma = \cfrac { \frac {C} {C_r} } { \frac {L} {L_r} } </math>
| |
| − |
| |
| − | 如果<math> \sigma > {1}</math>( <math> C \gg C_r </math>，且<math>L \approx L_r</math>), 网络即为小世界网络
| |
| − |
| |
| − | 另一个量化网络小世界性的方法，是利用小世界网络的原始定义，比较给定网络与等价随机网格网络的集聚系数及路径长度<ref name="a7">#The ubiquity of small-world networks Q.K. Telesford, K.E. Joyce, S. Hayasaka, J.H. Burdette, P.J. Laurienti, Brain Connect. 2011;1(5):367–75, doi:10.1089/brain.2011.0038</ref>。小世界所用的度量（ω）定义如下<ref name="a8">#Telesford, Joyce, Hayasaka, Burdette, and Laurienti (2011). "[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3604768 The Ubiquity of Small-World Networks]". Brain Connectivity. 1 (0038): 367–75. doi:10.1089/brain.2011.0038. PMC 3604768 Freely accessible. PMID 22432451.</ref>：
| |
| − |
| |
| − | <math> \omega = \frac{L_r}{L}-\frac{C}{C_l} </math>
| |
| − |
| |
| − | 其中，对于所选受测网络而言，<i>L</i>是特征路径长度，<i>C</i>是集聚系数。<math>C_l</math>是等价栅格网络的集聚系数， 而<math>L_r</math>则是等价随机网络的的特征路径长度。
| |
| − |
| |
| − | R. Cohen和[https://en.wikipedia.org/wiki/Shlomo_Havlin Havlin]分析出<ref name="a9">#R. Cohen, S. Havlin, and D. ben-Avraham (2002). "[http://havlin.biu.ac.il/Publications.php?keyword=Structural+properties+of+scale+free+networks&year=*&match=all Structural properties of scale free networks]". Handbook of graphs and networks. Wiley-VCH, 2002 (Chap. 4).</ref><ref name="a10">#R. Cohen, S. Havlin (2003). "[http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall++&year=*&match=all Scale-free networks are ultrasmall]". Phys. Rev. Lett. 90 (5): 058701. arXiv:cond-mat/0205476. Bibcode:2003PhRvL..90e8701C. doi:10.1103/PhysRevLett.90.058701. PMID 12633404.</ref>，[https://en.wikipedia.org/wiki/Scale-free_networks 无标度网络]是超小世界。在这种情况下，由于中心的存在，最短路径会变得非常小，并且满足如下关系：
| |
| − |
| |
| − | <math> L \propto \log{\log N}</math>
| |
| − |
| |
| − | 结果表明，在存在[https://en.wikipedia.org/wiki/White_noise 白噪音]的小世界网络中，会出现随机同步，这意味着，白噪音有助于系统针对中等噪声强度进行更好地同步，而非减少噪音<ref name="a11">#Reihaneh Kouhi Esfahani, Farhad Shahbazi, Keivan Aghababaei Samani (2012). "[https://journals.aps.org/pre/abstract/10.1103/PhysRevE.86.036204 Noise-induced synchronization in small-world networks of phase oscillators]". Physical Review E. American Physical Society (3).</ref><ref name="a12">#Rodrigues, Francisco A and Peron, Thomas K DM and Ji, Peng and Kurths, J{\"u}rgen} (2016). "[https://www.sciencedirect.com/science/article/pii/S0370157315004408 The Kuramoto model in complex networks]". Physics Reports. Elsevier.</ref>。这种现象，与白噪音在[https://en.wikipedia.org/wiki/Random_graph 随机图]或[https://en.wikipedia.org/wiki/Scale-free_network 无标度网络]中的效果形成了鲜明的对比，即应用噪声会降低这些网络中的同步幅度。
| |
| − |
| |
| − | ===局限性 ===
| |
| − | 该模型的主要局限性是会产生不符实际的度分布。相较而言，现实中的网络通常是非齐次的[[无标度网络]]，有中心节点的存在和无标度的度分布。考虑到此，这样的网络可以用[[偏好依附模型 preferential attachment model]]来更好的描述，比如[[BA网络模型]]。（另一方面，BA模型没有产生真实网络中出现的高集聚特性，而这个弱点是WS小世界模型所不具备的。因此，WS小世界模型和BA模型均不应被看成是完全符合实际的。）WS小世界模型也暗含了固定的节点数，所以也不能用来描述网络的生长。
| |
| − |
| |
| − | === 网络鲁棒性（Network robustness） ===
| |
| − |
| |
| − | [https://en.wikipedia.org/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si Barabási]等研究人员提出假设，认为小世界网络在生物系统中的普遍存在，可能反映了这种结构的进化优势。一种可能性是，小世界网络相比其他网络架构，对扰动的鲁棒性更强。如果这种假设成立，小世界网络将为受到[https://en.wikipedia.org/wiki/Mutation 突变]或[https://en.wikipedia.org/wiki/Virus 病毒感染]损害的生物系统提供优势。
| |
| − |
| |
| − | 在一个具备遵循[[幂律分布]]现象的度分布的小世界网络中，随机删除节点，极少能导致[https://en.wikipedia.org/wiki/Mean-shortest_path 平均最短路径]长度显著增加（或[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]的显著降低）。这是因为，节点之间的最短路径通过[https://en.wikipedia.org/wiki/Hub_(network_science) 中心]点流动，而且，如果一个外围节点被删除，不太可能干扰其他外围节点之间的通路。由于小世界网络中，外围节点的比例要远高于[https://en.wikipedia.org/wiki/Hub_(network_science) 中心]的比例，因此，删除重要节点的概率非常低。例如，如果[https://en.wikipedia.org/wiki/Sun_Valley,_Idaho 爱达荷州太阳谷]的小型机场被关闭，不会增加在美国旅行的其他乘客到达各自目的地所需的平均航次。但是，如果随机删除的节点是中心枢纽，那么平均路径长度就会急剧增加。每年都可以看到，当芝加哥[https://en.wikipedia.org/wiki/O%27Hare_International_Airport 奥黑尔机场]等北部枢纽因大雪关闭时，经常会出现这种状况；许多乘客不得不搭乘更多航班，以达到目的地。
| |
| − |
| |
| − | 相反，在随机网络中，所有节点具有数量大致相同的连接，随机删除节点可能会略微增加平均最短距离，但删除任意节点都会带来这样的影响。从这个意义上来讲，随机网络容易受到随机扰动的影响，而小世界网络则具备鲁棒性。但是，小世界网络容易受到针对中心的攻击，而目标攻击无法对随机网络造成灾难性故障。
| |
| − |
| |
| − | 病毒已经进化到可以干扰中枢蛋白的活动，诸如[https://en.wikipedia.org/wiki/P53 p53]，并因此产生有利于病毒复制的细胞行为的巨大变化。渗流理论是分析网络鲁棒性的一个有效方法。
| |
| | | | |
| | ==特性== | | ==特性== |
| 第206行： |
第98行： |
| | *网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。 | | *网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。 |
| | | | |
| − | ==例子==
| |
| − | ===小世界网络例子===
| |
| − | 在现实世界的很多现象中，都能够看到小世界属性，这包括网络中的导航菜单、食物网、电网、代谢处理网络(metabolite processing networks)、[https://en.wikipedia.org/wiki/Biological_neural_network 脑神经网络]、选民网络、电话呼叫图、社交影响网络等等。文化网络<ref name="a13">#" 'n [http://www.litnet.co.za/n-kwantifisering-van-kleinwereldsheid-in-afrikaanse-kultuurnetwerke-in-vergelyking-met-ander-komplekse-netwerke/ Kwantifisering van kleinwêreldsheid in Afrikaanse kultuurnetwerke in vergelyking met ander komplekse netwerke | LitNet]". LitNet. 2015-11-05. Retrieved 2017-02-27.</ref>与单词共现网络<ref name="a14">#"[http://www.litnet.co.za/die-statistiese-eienskappe-van-geskrewe-afrikaans-n-komplekse-netwerk/ Die statistiese eienskappe van geskrewe Afrikaans as 'n komplekse netwerk | LitNet]". LitNet. 2017-02-09. Retrieved 2017-02-27.</ref>也被证明是小世界网络。
| |
| − |
| |
| − | 相连的蛋白质网络同样具有小世界性质，例如遵从幂律的度分布。<ref name="a15">#Bork, P.; Jensen, LJ; von Mering, C.; Ramani, A.; Lee, I.; Marcotte, EM. (2004). "[http://marcottelab.org/paper-pdfs/cosb-review.pdf Protein interaction networks from yeast to human]" (PDF). Current Opinion in Structural Biology. 14 (3): 292–299. doi:10.1016/j.sbi.2004.05.003. PMID 15193308.</ref>类似地还有[https://en.wikipedia.org/wiki/Transcriptional_regulation 转录网络]，其节点为[https://en.wikipedia.org/wiki/Gene 基因]，如果某一个基因对另一个基因有上调或下调的遗传影响，且这些基因彼此相连，这一网络就具有小世界网络的性质。<ref name="a16">#Van Noort, V; Snel, B; Huynen, MA. (Mar 2004). "[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1299002 The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model]". EMBO Rep. 5 (3): 280–4. doi:10.1038/sj.embor.7400090. PMC 1299002 Freely accessible. PMID 14968131.</ref>
| |
| − |
| |
| − | ===非小世界网络例子===
| |
| − | 另一个例子就是人与人之间的“[https://en.wikipedia.org/wiki/Six_degrees_of_separation 六度分离]”理论，这里默认的适用[https://en.wikipedia.org/wiki/Domain_of_discourse 领域]是一群在任意时刻都活着的人。[https://en.wikipedia.org/wiki/Albert_Einstein 阿尔伯特·爱因斯坦]与[https://en.wikipedia.org/wiki/Alexander_the_Great 亚历山大大帝]之间的分离度，几乎肯定是大于30的<ref name="a17">#Einstein and Alexander the Great lived 2202 years apart. Assuming an age difference of 70 years between any two connected people in the chain that connects the two, this would necessitate at least 32 connections between Einstein and Alexander the Great.</ref>，而且这个世界并不具备小世界属性。一个同样不具备小世界性质的网络还有“曾去同一家学校上学”的网络：如果两个人加入某一所大学的时间差了10年，他们不太可能在学生团体中有共同的熟人。
| |
| − |
| |
| − | 类似的，消息传播过程中必须要通过的中继站点的数量并不总是很小的。回溯到邮件还需要手工投递或骑马寄送的时期，一封信件从它的起点到终点所需要转手的次数，会比现在大上很多。可视电报（约存在于1800-1850年）时代，消息易手的次数，要由两个站点之间是否是在视线连接范围内决定。
| |
| − |
| |
| − | 如果没有检验隐含假设，可能会对图“望图生义”，偏向于寻找小世界网络（一个例子就是发表性偏倚导致的[https://en.wikipedia.org/wiki/File_drawer_problem#File_drawer_effect 文件抽屉问题]（file drawer））。
| |
| − |
| |
| − |
| |
| − | ==应用==
| |
| − | ===社会学应用===
| |
| − |
| |
| − | 小世界网络对[https://en.wikipedia.org/wiki/Social_movement 社会运动群体]的优势在于，它们由于采用了高度互联的节点的过滤设备，因而对变化具有一定的抗性，以及它有效地实现了，在中继信息的同时，保持了连接网络所需的最少链路数”。<ref name="a22">#Shirky, Clay. 2008. [https://en.wikipedia.org/wiki/Here_Comes_Everybody Here Comes Everybody]</ref>
| |
| − |
| |
| − | [https://en.wikipedia.org/wiki/William_Finnegan William Finnegan]在社会学论证提出，小世界网络可直接适用于[https://en.wikipedia.org/wiki/Affinity_group 亲和团体]（Affinity Group）理论。亲和团体指的是旨在实现某个较大目标或功能的小型半独立社会运动团体。虽然在节点级别上并没有严格的隶属架构，但作为连接节点的少数高连接性成员，能够通过网络连接组织内的不同群体。这种小世界网络已被证明是一种极其有效的抗议警察行动的组织策略。<ref name="a23">#Finnegan, William "Affinity Groups and the Movement Against Corporate Globalization"</ref>[https://en.wikipedia.org/wiki/Clay_Shirky Clay Shirky]认为，通过小世界网络创造的社交网络越大，高连接性结点在网络内的价值就越高。<ref name="a22"></ref>同理可适用于亲和团体模型，即每个团体内只有少数人与外部团体相联系，从而极大提高了灵活性和适应性。这方面的一个实践案例是William Finnegan在概括[https://en.wikipedia.org/wiki/1999_Seattle_Protests 1999年西雅图世贸组织抗议活动]时，所提到的亲和团体中的小世界网络。
| |
| − |
| |
| − | ===地球科学应用===
| |
| − |
| |
| − | 许多研究地质学和地球物理学的网络，已被证明具有小世界网络的特征。在裂缝系统和多空物质中被定义的网络，已经显示出了这些特征。<ref name="a24">#X. S. Yang, Small-world networks in geophysics, Geophys. Res. Lett., 28(13), 2549–2552 (2001)
| |
| − | </ref>南加州地区的地震网络或许就是一个小世界网络。<ref name="a25">#A. Jimenez, K. F. Tiampo, and A. M. Posadas, Small-world in a seismic network: the California case, Nonlin. Processes Geophys., 15, 389–395 (2008)</ref>上述提及的例子所发生的空间尺度大相径庭，也证明了在地球科学中，这一现象不受空间尺度大小所影响，具备[https://en.wikipedia.org/wiki/Scale_invariance 尺度不变性]（scale invariance）。气候网络或许也可被视作小世界网络，其中的联系具备长度不一的尺度。<ref name="a26">#Gozolchiani, A.; Havlin, S.; Yamasaki, K. (2011). "Emergence of El Niño as an Autonomous Component in the Climate Network". Physical Review Letters. 107 (14): 148501. arXiv:1010.2605 Freely accessible. Bibcode:2011PhRvL.107n8501G. doi:10.1103/PhysRevLett.107.148501. ISSN 0031-9007. PMID 22107243.
| |
| − | </ref>
| |
| − |
| |
| − | ===计算应用===
| |
| | | | |
| − | 小世界网络已被用于估算存储于大型数据库中信息的可用性。这种度量方法被称为“小世界数据变换法”<ref name="a27"># http://mike2.openmethodology.org/wiki/Small_Worlds_Data_Transformation_Measure</ref><ref name="a28">#Hillard, Robert (2010). Information-Driven Business. Wiley. ISBN 978-0-470-62577-4.</ref>数据库链接与小世界网络对齐度越高，用户越有可能在将来提取到信息。这种可用性通常以牺牲存储在同等空间中的信息量为代价来取得。
| |
| − |
| |
| − | [https://en.wikipedia.org/wiki/Freenet Freenet]和[https://en.wikipedia.org/wiki/Bitcoin_Cash 比特币]点对点网络已经被证明在模拟中构筑了小世界网络<ref name="a29">#Sandberg, Oskar. "[https://freenetproject.org/papers/lic.pdf Searching in a Small World]" (PDF).
| |
| − | </ref>，使得信息的存储和提取，能够随着网络扩展，而有效扩张。
| |
| − |
| |
| − | ===大脑中的小世界网络===
| |
| − |
| |
| − | 大脑中连接<ref name="a30">#Sporns, Olaf; Chialvo DR; Kaiser M; Hilgetag CC (2004). "Organization, development and function of complex brain networks". Trends Cogn Sci. 8 (9): 418–425. doi:10.1016/j.tics.2004.07.008. PMID 15350243.
| |
| − | </ref>与皮层神经元的同步网络<ref name="a31">#Yu, Shan; D. Huang; W. Singer; D. Nikolić (2008). "[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2583154 A Small World of Neuronal Synchrony]". Cerebral Cortex. 18 (12): 2891–2901. doi:10.1093/cercor/bhn047. PMC 2583154 Freely accessible. PMID 18400792.</ref>都体现出了小世界拓扑结构。
| |
| − |
| |
| − | 小世界神经元网络可以呈现出[https://en.wikipedia.org/wiki/Short-term_memory 短期记忆]。Solla等人提出的计算机模型具有两个稳定状态<ref name="a32">#Cohen, Philip. [https://www.newscientist.com/article.ns?id=dn5012 Small world networks key to memory]. New Scientist. 26 May 2004.</ref><ref name="a33">#Sara Solla's [http://online.itp.ucsb.edu/online/brain04/solla/ Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons]</ref>——一种被认为在[https://en.wikipedia.org/wiki/Memory 记忆]存储中十分重要的特性（被称为[https://en.wikipedia.org/wiki/Bistability 双稳态]）。激活脉冲在神经元之间产生自我维持的通信活动循环。第二波脉冲则终止这一活动。脉冲让这一系统在稳定状态间切换：流动（记录“记忆”）以及停滞（保留记忆）。小世界神经元网络也被用于建模，了解[https://en.wikipedia.org/wiki/Seizures 病情发作]的原理。<ref name="a34">#Ponten, S.C.; Bartolomei, F.; Stam, C.J. (April 2007). "Small-world networks and epilepsy: Graph theoretical analysis of intracerebrally recorded mesial temporal lobe seizures". Clinical Neurophysiology. 118 (4): 918–927. doi:10.1016/j.clinph.2006.12.002.</ref>
| |
| − |
| |
| − | 在更一般的层次上，大脑中的许多大规模神经网络，例如视觉系统和脑干，都体现出了小世界特性。
| |
| | | | |
| | ==参见== | | ==参见== |
| 第254行： |
第105行： |
| | *[[BA网络模型]] | | *[[BA网络模型]] |
| | *[[社交网络]] | | *[[社交网络]] |
| − | *[[气候网络]]
| |
| − | *[[双相演化（Dual-phase evolution）]]
| |
| − | *[[Dunbar数]]
| |
| − | *[[Erdős数]]
| |
| − | *[[ 渗透理论（Percolation theory）]]
| |
| − | *[[ 无标度网络]]
| |
| − | *[[ Kevin Bacon的六度理论]]
| |
| − | *[[ Watts Strogatz模型]]
| |
| | | | |
| | ==参考文献== | | ==参考文献== |
| | <references /> | | <references /> |
| − | ===书籍===
| |
| − |
| |
| − | *Buchanan, Mark (2003). Nexus: Small Worlds and the Groundbreaking Theory of Networks. Norton, W. W. & Company, Inc. ISBN 0-393-32442-7.
| |
| − | *Dorogovtsev, S.N. & Mendes, J.F.F. (2003). Evolution of Networks: from biological networks to the Internet and WWW. Oxford University Press. ISBN 0-19-851590-1.
| |
| − | *Watts, D. J. (1999). Small Worlds: The Dynamics of Networks Between Order and Randomness. Princeton University Press. ISBN 0-691-00541-9.
| |
| − | *Fowler, JH. (2005) "Turnout in a Small World," in Alan Zuckerman, ed., Social Logic of Politics, Temple University Press, 269–287
| |
| − | *Reuven Cohen and Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.
| |
| − |
| |
| − | ===期刊===
| |
| − |
| |
| − | *Albert, R.; Barabási A.L. (2002). "Statistical mechanics of complex networks". Rev. Mod. Phys. 74: 47–97. arXiv:cond-mat/0106096 Freely accessible. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47.
| |
| − | *Albert, R.; Barabási A.L. (1999). "Emergence of scaling in random networks". Science. 286 (5439): 509–12. arXiv:cond-mat/9910332 Freely accessible. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342.
| |
| − | *Barthelemy, M.; Amaral, LAN. (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82 (15): 3180–3183. arXiv:cond-mat/9903108 Freely accessible. Bibcode:1999PhRvL..82.3180B. doi:10.1103/PhysRevLett.82.3180.
| |
| − | *Dorogovtsev, S.N.; Mendes, J.F.F. (2000). "Exactly solvable analogy of small-world networks". Europhys. Lett. 50: 1–7. arXiv:cond-mat/9907445 Freely accessible. Bibcode:2000EL.....50....1D. doi:10.1209/epl/i2000-00227-1.
| |
| − | *Milgram, Stanley (1967). "The Small World Problem". Psychology Today. 1 (1): 60–67.
| |
| − | *Newman, Mark (2003). "The Structure and Function of Complex Networks". SIAM Review. 45 (2): 167–256. arXiv:cond-mat/0303516 Freely accessible. Bibcode:2003SIAMR..45..167N. doi:10.1137/S003614450342480. pdf
| |
| − | *Ravid, D.; Rafaeli, S. (2004). "Asynchronous discussion groups as Small World and Scale Free Networks". First Monday. 9 (9). doi:10.5210/fm.v9i9.1170. [1]
| |
| − | *R. Parshani, S.V. Buldyrev, S. Havlin (2011). "Critical effect of dependency groups on the function of networks". PNAS. 108: 1007–1010. arXiv:1010.4498 Freely accessible. *Bibcode:2011PNAS..108.1007P. doi:10.1073/pnas.1008404108. PMC 3024657 Freely accessible. PMID 21191103.
| |
| − | *S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–8. arXiv:0907.1182 Freely accessible. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. PMID 20393559.
| |
| − |
| |
| − | ==相关链接==
| |
| − |
| |
| − | *[http://demonstrations.wolfram.com/DynamicProximityNetworks 动态临近网络] Seth J. Chandler, [https://en.wikipedia.org/wiki/The_Wolfram_Demonstrations_Project Wolfram展示项目]
| |
| − | *[http://www.scholarpedia.org/article/Small-world_network 小世界网络]词条, Scholarpedia (Mason A. Porter)
| |
| | | | |
| | ==编者推荐== | | ==编者推荐== |