小世界网络

来自集智百科
跳转到: 导航搜索


该词条由 【Sherimon】 翻译编辑,由【高飞】审校,【张江】总审校,翻译自Wikipedia词条Small-world_network



小世界网络的例子 中心比其他节点大 平均3.833 平均最短路径长度1.803 聚类系数0.522
随机图 平均2.833 平均最短路径长度2.109 聚类系数0.167

小世界网络是一种数学图。在此类图中,绝大多数节点彼此之间并不相邻,但任一给定节点的邻居们却很可能彼此是邻居,并且大多数节点都可以从任意其他节点,用较少的步或跳跃访问到。具体来说,小世界网络的定义如下:如果网络中随机选择的两个节点之间的距离L(即访问彼此所需要的步数),与网络中节点数量N的对数成比例增长,(即[1]: L \propto \log N),且网络的集聚系数(Clustering Coefficient)不小,那么,这样的网络就是小世界网络。在社交网络中,这种网络属性意味着一些彼此并不相识的人,可以通过一条很短的熟人链条被联系在一起,这也就是小世界现象。许多经验网络图都展示出了小世界现象,例如社交网络互联网的底层架构、诸如Wikipedia的百科类网站以及基因网络等等。

1998年,Duncan WattsSteven Strogatz提出,小世界网络是一类随机图[2]。他们指出,这类网络图可以通过两个独立的结构特征,即集聚系数和平均节点间距离(也称作平均最短路径长度)来进行识别。根据Erdős-Rényi(ER)模型构造的纯随机图,会展现出较小的最短路径长度(通常随着节点数对数值的变化而变化)以及较小的集聚系数。WattsStrogatz验证了这一点,事实上,现实世界中很多网络的平均最短路径长度都较短,而集聚系数又远高于普通随机图。Watts和Strogatz随后提出了一种新的图模型(即现在的Watts-Strogatz模型),该模型具备两个特征:(1)平均最短路径长度较小,(2)集聚系数较大。1999年,Barthelemy和Amaral最先描述出了Watts-Strogatz模型中“大世界”(诸如栅格网络)与小世界的交叉点性质[3]。在此之后,学界又涌现出了大量的相关研究,其中不乏一些较为精确的度量结果 (Barrat and Weigt, 1999; Dorogovtsev and Mendes; Barmpoutis and Murray, 2010)。 Braunstein发现[4],对于权值分布非常广的加权ER网络,最佳路径长度会显著增长,其增长速度为N^{\frac{1}{3}}.

目录

小世界网络的性质

小世界网络中往往会包含(cliques)以及临近团(near-cliques)——此处的“团”,指的是内部几乎任意两个节点之间都存在连接的子网络。这遵循高集聚系数的定义属性。其次,大多数节点对之间,都至少存在一条短路径。这遵循平均最短路径较小的定义属性。许多其他属性,通常也会与小世界网络有所关联。通常情况下,网络中会存在很多的中心(hub)——它们是具有很高连接数的节点(即高(Degree)节点)。这些中心扮演了公共连接的角色,缩短了其他边之间的短路径长度。通过对比,航空航班的小世界网络,都体现出了较短的平均路径长度(例如,在任意两个城市之间飞行,你通常可能只需要乘坐三程或更少的航班数),因为很多航线都可以通过枢纽城市进行中转。这一属性的分析,通常要考虑网络中,具有相同入度的节点的比例(网络的度的分布)。网络具有较多中心(hub),意味着度值较大的节点占比会更高,因此,在这种网络的度分布中,高度值分布更高,即俗称的厚尾分布(fat-tailed distribution)。具有不同拓扑结构的图,只要满足上述两个定义,就可以被定义为小世界网络。

网络的小世界性被量化为一个系数 σ,可以通过比较给定网络与具备相同度分布的等价网络的集聚系数与路径长度,计算得出[5][6]

\sigma = \cfrac { \frac {C} {C_r} } { \frac {L} {L_r} }

如果  \sigma > {1}(  C \gg C_r ,且L \approx L_r), 网络即为小世界网络

另一个量化网络小世界性的方法,是利用小世界网络的原始定义,比较给定网络与等价随机网格网络的集聚系数及路径长度[7]。小世界所用的度量(ω)定义如下[8]

 \omega =  \frac{L_r}{L}-\frac{C}{C_l}

其中,对于所选受测网络而言,L是特征路径长度,C是集聚系数。C_l是等价栅格网络的集聚系数, 而L_r则是等价随机网络的的特征路径长度。

R. Cohen和Havlin分析出[9][10]无标度网络是超小世界。在这种情况下,由于中心的存在,最短路径会变得非常小,并且满足如下关系:

 L \propto \log{\log N}

结果表明,在存在白噪音的小世界网络中,会出现随机同步,这意味着,白噪音有助于系统针对中等噪声强度进行更好地同步,而非减少噪音[11][12]。这种现象,与白噪音在随机图无标度网络中的效果形成了鲜明的对比,即应用噪声会降低这些网络中的同步幅度。

小世界网络例子

在现实世界的很多现象中,都能够看到小世界属性,这包括网络中的导航菜单、食物网、电网、代谢处理网络(metabolite processing networks)、脑神经网络、选民网络、电话呼叫图、社交影响网络等等。文化网络[13]与单词共现网络[14]也被证明是小世界网络。

相连的蛋白质网络同样具有小世界性质,例如遵从幂律的度分布。[15]类似地还有转录网络,其节点为基因,如果某一个基因对另一个基因有上调或下调的遗传影响,且这些基因彼此相连,这一网络就具有小世界网络的性质。[16]

非小世界网络例子

另一个例子就是人与人之间的“六度分离”理论,这里默认的适用领域是一群在任意时刻都活着的人。阿尔伯特·爱因斯坦亚历山大大帝之间的分离度,几乎肯定是大于30的[17],而且这个世界并不具备小世界属性。一个同样不具备小世界性质的网络还有“曾去同一家学校上学”的网络:如果两个人加入某一所大学的时间差了10年,他们不太可能在学生团体中有共同的熟人。

类似的,消息传播过程中必须要通过的中继站点的数量并不总是很小的。回溯到邮件还需要手工投递或骑马寄送的时期,一封信件从它的起点到终点所需要转手的次数,会比现在大上很多。可视电报(约存在于1800-1850年)时代,消息易手的次数,要由两个站点之间是否是在视线连接范围内决定。

如果没有检验隐含假设,可能会对图“望图生义”,偏向于寻找小世界网络(一个例子就是发表性偏倚导致的文件抽屉问题(file drawer))。

网络鲁棒性(Network robustness)

Barabási等研究人员提出假设,认为小世界网络在生物系统中的普遍存在,可能反映了这种结构的进化优势。一种可能性是,小世界网络相比其他网络架构,对扰动的鲁棒性更强。如果这种假设成立,小世界网络将为受到突变病毒感染损害的生物系统提供优势。

在一个具备遵循幂律分布现象的度分布的小世界网络中,随机删除节点,极少能导致平均最短路径长度显著增加(或集聚系数的显著降低)。这是因为,节点之间的最短路径通过中心点流动,而且,如果一个外围节点被删除,不太可能干扰其他外围节点之间的通路。由于小世界网络中,外围节点的比例要远高于中心的比例,因此,删除重要节点的概率非常低。例如,如果爱达荷州太阳谷的小型机场被关闭,不会增加在美国旅行的其他乘客到达各自目的地所需的平均航次。但是,如果随机删除的节点是中心枢纽,那么平均路径长度就会急剧增加。每年都可以看到,当芝加哥奥黑尔机场等北部枢纽因大雪关闭时,经常会出现这种状况;许多乘客不得不搭乘更多航班,以达到目的地。

相反,在随机网络中,所有节点具有数量大致相同的连接,随机删除节点可能会略微增加平均最短距离,但删除任意节点都会带来这样的影响。从这个意义上来讲,随机网络容易受到随机扰动的影响,而小世界网络则具备鲁棒性。但是,小世界网络容易受到针对中心的攻击,而目标攻击无法对随机网络造成灾难性故障。

病毒已经进化到可以干扰中枢蛋白的活动,诸如p53,并因此产生有利于病毒复制的细胞行为的巨大变化。渗流理论是分析网络鲁棒性的一个有效方法。

构建小世界网络

构建小世界网络的主要机制是Watts-Strogatz机制

小世界网络也可引入延时[18],这不仅会产生分形,而且在特定条件下,还会形成混沌[19],或者在动态网络中转变为混沌[20]

构造度直径图(Degree–diameter graph)的方法是:网络中每个顶点的邻居数量是有界的,而网络中从任意给定顶点到其他顶点(网络直径)是最小的。构建这样的小世界网络,其实是为寻找临近摩尔边界的图的秩,而做出的一部分努力。

Barmpoutis等人给出的从零开始构建小世界网络的另外一种方法[21],构建了一种平均距离极小且平均集聚度极高的网络。他们提到了一种复杂度恒定的快速算法,以及不同生成图鲁棒性的度量。根据每个网络的应用,可以从一个这样的“超小世界”网络开始,然后重新连接一些边,或者使用几个这样的小网络作为子图,构筑一个更大的图。

通过双相演化(dual-phase evolution)过程,小世界属性可以在社交网络和其他现实世界系统中自然产生。在顶点之间的连接增长受到时间或空间的制约时,小世界网络尤其常见。该机制通常涉及相位之间的周期性变换,其中,在“全局”阶段——连接建立,而在“本地”阶段——连接被移除。

参考:扩散限制凝聚模式构成

构建小世界网络代码实现

使用networkx生成小世界网络

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()

此时得到的图片是下图所示:

Networksx包生成的小世界网络.png

使用原生方法x生成小世界网络

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()

此时得到的图片如下图所示:
原声方法生成的小世界网络.png

应用

社会学应用

小世界网络对社会运动群体的优势在于,它们由于采用了高度互联的节点的过滤设备,因而对变化具有一定的抗性,以及它有效地实现了,在中继信息的同时,保持了连接网络所需的最少链路数”。[22]

William Finnegan在社会学论证提出,小世界网络可直接适用于亲和团体(Affinity Group)理论。亲和团体指的是旨在实现某个较大目标或功能的小型半独立社会运动团体。虽然在节点级别上并没有严格的隶属架构,但作为连接节点的少数高连接性成员,能够通过网络连接组织内的不同群体。这种小世界网络已被证明是一种极其有效的抗议警察行动的组织策略。[23]Clay Shirky认为,通过小世界网络创造的社交网络越大,高连接性结点在网络内的价值就越高。[22]同理可适用于亲和团体模型,即每个团体内只有少数人与外部团体相联系,从而极大提高了灵活性和适应性。这方面的一个实践案例是William Finnegan在概括1999年西雅图世贸组织抗议活动时,所提到的亲和团体中的小世界网络。

地球科学应用

许多研究地质学和地球物理学的网络,已被证明具有小世界网络的特征。在裂缝系统和多空物质中被定义的网络,已经显示出了这些特征。[24]南加州地区的地震网络或许就是一个小世界网络。[25]上述提及的例子所发生的空间尺度大相径庭,也证明了在地球科学中,这一现象不受空间尺度大小所影响,具备尺度不变性(scale invariance)。气候网络或许也可被视作小世界网络,其中的联系具备长度不一的尺度。[26]

计算应用

小世界网络已被用于估算存储于大型数据库中信息的可用性。这种度量方法被称为“小世界数据变换法”[27][28]数据库链接与小世界网络对齐度越高,用户越有可能在将来提取到信息。这种可用性通常以牺牲存储在同等空间中的信息量为代价来取得。

Freenet比特币点对点网络已经被证明在模拟中构筑了小世界网络[29],使得信息的存储和提取,能够随着网络扩展,而有效扩张。

大脑中的小世界网络

大脑中连接[30]与皮层神经元的同步网络[31]都体现出了小世界拓扑结构。

小世界神经元网络可以呈现出短期记忆。Solla等人提出的计算机模型具有两个稳定状态[32][33]——一种被认为在记忆存储中十分重要的特性(被称为双稳态)。激活脉冲在神经元之间产生自我维持的通信活动循环。第二波脉冲则终止这一活动。脉冲让这一系统在稳定状态间切换:流动(记录“记忆”)以及停滞(保留记忆)。小世界神经元网络也被用于建模,了解病情发作的原理。[34]

在更一般的层次上,大脑中的许多大规模神经网络,例如视觉系统和脑干,都体现出了小世界特性。[5]

小世界的连接长度分布

WS模型包含了一个长域连接的均匀分布。当连接长度的分布遵循“幂次现象”分布时,两个结点之间平均距离的变化,取决于分布的幂次。[35]

参见

参考

  1. http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html
  2. Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. Papercore Summary http://www.papercore.org/Watts1998
  3. #Barthelemy, M.; Amaral, LAN (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82 (15): 3180–3183. arXiv:cond-mat/9903108. Bibcode:1999PhRvL..82.3180B. doi:10.1103/PhysRevLett.82.3180.
  4. #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.
  5. 5.0 5.1 #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
  6. #Humphries and Gurney (2008). "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.
  7. #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
  8. #Telesford, Joyce, Hayasaka, Burdette, and Laurienti (2011). "The Ubiquity of Small-World Networks". Brain Connectivity. 1 (0038): 367–75. doi:10.1089/brain.2011.0038. PMC 3604768 Freely accessible. PMID 22432451.
  9. #R. Cohen, S. Havlin, and D. ben-Avraham (2002). "Structural properties of scale free networks". Handbook of graphs and networks. Wiley-VCH, 2002 (Chap. 4).
  10. #R. Cohen, S. Havlin (2003). "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.
  11. #Reihaneh Kouhi Esfahani, Farhad Shahbazi, Keivan Aghababaei Samani (2012). "Noise-induced synchronization in small-world networks of phase oscillators". Physical Review E. American Physical Society (3).
  12. #Rodrigues, Francisco A and Peron, Thomas K DM and Ji, Peng and Kurths, J{\"u}rgen} (2016). "The Kuramoto model in complex networks". Physics Reports. Elsevier.
  13. #" 'n Kwantifisering van kleinwêreldsheid in Afrikaanse kultuurnetwerke in vergelyking met ander komplekse netwerke | LitNet". LitNet. 2015-11-05. Retrieved 2017-02-27.
  14. #"Die statistiese eienskappe van geskrewe Afrikaans as 'n komplekse netwerk | LitNet". LitNet. 2017-02-09. Retrieved 2017-02-27.
  15. #Bork, P.; Jensen, LJ; von Mering, C.; Ramani, A.; Lee, I.; Marcotte, EM. (2004). "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.
  16. #Van Noort, V; Snel, B; Huynen, MA. (Mar 2004). "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.
  17. #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.
  18. #X. S. Yang, Fractals in small-world networks with time-delay, Chaos, Solitons & Fractals, vol. 13, 215–219 (2002)
  19. #X. S. Yang, Chaos in small-world networks, Phys. Rev. E 63, 046206 (2001)
  20. #W. Yuan, X. S. Luo, P. Jiang, B. Wang, J. Fang, Transition to chaos in small-world dynamical network
  21. #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].
  22. 22.0 22.1 #Shirky, Clay. 2008. Here Comes Everybody
  23. #Finnegan, William "Affinity Groups and the Movement Against Corporate Globalization"
  24. #X. S. Yang, Small-world networks in geophysics, Geophys. Res. Lett., 28(13), 2549–2552 (2001)
  25. #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)
  26. #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.
  27. # http://mike2.openmethodology.org/wiki/Small_Worlds_Data_Transformation_Measure
  28. #Hillard, Robert (2010). Information-Driven Business. Wiley. ISBN 978-0-470-62577-4.
  29. #Sandberg, Oskar. "Searching in a Small World" (PDF).
  30. #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.
  31. #Yu, Shan; D. Huang; W. Singer; D. Nikolić (2008). "A Small World of Neuronal Synchrony". Cerebral Cortex. 18 (12): 2891–2901. doi:10.1093/cercor/bhn047. PMC 2583154 Freely accessible. PMID 18400792.
  32. #Cohen, Philip. Small world networks key to memory. New Scientist. 26 May 2004.
  33. #Sara Solla's Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons
  34. #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.
  35. #D. Li, K. Kosmidis, A. Bunde, S. Havlin (2011). "Dimension of spatially embedded networks". Nature Physics. 7: 481–484. Bibcode:2011NatPh...7..481D. doi:10.1038/nphys1932.

书籍

  • 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.

相关链接

本词条内容翻译自 wikipedia.org,遵守 CC3.0协议。


复杂系统

个人工具
名字空间
操作
导航
工具箱