“小世界网络”的版本间的差异

来自集智百科
跳转到: 导航搜索
非小世界网络例子
网络鲁棒性(Network robustness)
第47行: 第47行:
  
  
[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/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/Power-law  幂律]现象的度分布的小世界网络中,随机删除节点,极少能导致[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/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 奥黑尔机场]等北部枢纽因大雪关闭时,经常会出现这种状况;许多乘客不得不搭乘更多航班,以达到目的地。
  
 
 相反,在随机网络中,所有节点具有数量大致相同的连接,随机删除节点可能会略微增加平均最短距离,但删除任意节点都会带来这样的影响。从这个意义上来讲,随机网络容易受到随机扰动的影响,而小世界网络则具备鲁棒性。但是,小世界网络容易受到针对中心的攻击,而目标攻击无法对随机网络造成灾难性故障。
 
 相反,在随机网络中,所有节点具有数量大致相同的连接,随机删除节点可能会略微增加平均最短距离,但删除任意节点都会带来这样的影响。从这个意义上来讲,随机网络容易受到随机扰动的影响,而小世界网络则具备鲁棒性。但是,小世界网络容易受到针对中心的攻击,而目标攻击无法对随机网络造成灾难性故障。

2018年7月31日 (二) 15:00的版本

小世界网络的例子 中心比其他节点大 平均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)模型构造的纯随机图,会展现出较小的最短路径长度(通常随着节点数对数值的变化而变化)以及较小的集聚系数。瓦茨和斯特罗加茨验证了这一点,事实上,现实世界中很多网络的平均最短路径长度都较短,而集聚系数又远高于普通随机图。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), 网络即为小世界网络

另一个量化网络小世界性的方法,是