“WS小世界模型”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第1行: 第1行:
 
'''WS小世界模型 Watts–Strogatz model '''是一种[https://en.wikipedia.org/wiki/Random_graph 随机图]生成模型,其生成的图具有[[小世界属性]],包括较短的[https://en.wikipedia.org/wiki/Average_path_length 平均节点间距离]和高[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]。该模型由[https://en.wikipedia.org/wiki/Duncan_J._Watts 邓肯 J. 沃茨 Duncan J. Watts]和[https://en.wikipedia.org/wiki/Steven_Strogatz 斯蒂文·史楚盖兹 Steven Strogatz]在1998年两人联合发表于[https://en.wikipedia.org/wiki/Nature_(journal) 《自然》]的论文中提出
 
'''WS小世界模型 Watts–Strogatz model '''是一种[https://en.wikipedia.org/wiki/Random_graph 随机图]生成模型,其生成的图具有[[小世界属性]],包括较短的[https://en.wikipedia.org/wiki/Average_path_length 平均节点间距离]和高[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]。该模型由[https://en.wikipedia.org/wiki/Duncan_J._Watts 邓肯 J. 沃茨 Duncan J. Watts]和[https://en.wikipedia.org/wiki/Steven_Strogatz 斯蒂文·史楚盖兹 Steven Strogatz]在1998年两人联合发表于[https://en.wikipedia.org/wiki/Nature_(journal) 《自然》]的论文中提出
<ref name=WS>
+
<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>
{{Cite journal  
 
| last1 = Watts  
 
| first1 = D. J.  
 
| last2 = Strogatz  
 
| first2 = S. H.   
 
| 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>
 
 
。Watts在其广受欢迎的科学读物[https://en.wikipedia.org/wiki/Six_Degrees:_The_Science_of_a_Connected_Age 《Six Degrees》]中使用<math>\beta</math>来阐述该模型,这之后,该模型也被称为(沃茨)<math>\beta</math> 模型。
 
。Watts在其广受欢迎的科学读物[https://en.wikipedia.org/wiki/Six_Degrees:_The_Science_of_a_Connected_Age 《Six Degrees》]中使用<math>\beta</math>来阐述该模型,这之后,该模型也被称为(沃茨)<math>\beta</math> 模型。
  
第24行: 第6行:
 
==模型基本原理==
 
==模型基本原理==
 
对[https://en.wikipedia.org/wiki/随机图 Random_graph]的正式研究可追溯至 [https://en.wikipedia.org/wiki/Paul_Erd%C5%91s 保尔·厄多斯 Paul Erdős]和[https://en.wikipedia.org/wiki/Alfr%C3%A9d_R%C3%A9nyi 阿尔弗烈德·瑞利 Alfréd Rényi]的工作
 
对[https://en.wikipedia.org/wiki/随机图 Random_graph]的正式研究可追溯至 [https://en.wikipedia.org/wiki/Paul_Erd%C5%91s 保尔·厄多斯 Paul Erdős]和[https://en.wikipedia.org/wiki/Alfr%C3%A9d_R%C3%A9nyi 阿尔弗烈德·瑞利 Alfréd Rényi]的工作
<ref name=Erdos1960>
+
<ref name=Erdos1960>{{cite journal
{{cite journal
 
 
  | author = Erdos, P.
 
  | author = Erdos, P.
 
  | year = 1960
 
  | year = 1960
第32行: 第13行:
 
  | volume = 5
 
  | volume = 5
 
  | pages = 17
 
  | pages = 17
}}
+
}}</ref>  
</ref>
 
 
。他们所考虑的图,也就是现在所谓的经典图或[[ER随机图模型]],给许多应用提供了简单而强有力的模型。
 
。他们所考虑的图,也就是现在所谓的经典图或[[ER随机图模型]],给许多应用提供了简单而强有力的模型。
  
第40行: 第20行:
  
 
#不能生成局部集聚 local clustering 和[https://en.wikipedia.org/wiki/Triadic_closure 三元闭合] triadic closures(网络有三元闭合、三元闭包等释义)。相反,因为图中两个节点有恒定、随机且独立的概率彼此相连,[[ER随机图模型]]的[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]较低。
 
#不能生成局部集聚 local clustering 和[https://en.wikipedia.org/wiki/Triadic_closure 三元闭合] triadic closures(网络有三元闭合、三元闭包等释义)。相反,因为图中两个节点有恒定、随机且独立的概率彼此相连,[[ER随机图模型]]的[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]较低。
#不能解释中心节点 hub 的构成。在形式上,[[ER随机图模型]]的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]分布收敛于[https://en.wikipedia.org/wiki/泊松分布 Poisson_distribution ],而不是我们在现实世界中观测到的、[[无标度网络]] scale-free networks 的[[幂律分布]] power law<ref name=Ravasz2002>
+
#不能解释中心节点 hub 的构成。在形式上,[[ER随机图模型]]的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]分布收敛于[https://en.wikipedia.org/wiki/泊松分布 Poisson_distribution ],而不是我们在现实世界中观测到的、[[无标度网络]] scale-free networks 的[[幂律分布]] power law<ref name=Ravasz2002>{{cite journal|last1=Ravasz|first1=E.|title=Hierarchical Organization of Modularity in Metabolic Networks|journal=Science|date=30 August 2002|volume=297|issue=5586|pages=1551–1555|doi=10.1126/science.1073374|bibcode=2002Sci...297.1551R|arxiv=cond-mat/0209244|pmid=12202830}}</ref>
{{cite journal
 
|last1=Ravasz
 
|first1=E.
 
|title=Hierarchical Organization of Modularity in Metabolic Networks
 
|journal=Science
 
|url = https://arxiv.org/pdf/cond-mat/0209244.pdf
 
|date=30 August 2002
 
|volume=297
 
|issue=5586
 
|pages=1551–1555
 
|doi:10.1126/science.1073374
 
|bibcode:2002Sci...297.1551R
 
|arxiv:cond-mat/0209244}}
 
</ref>
 
  
  
 
WS模型是针对于第一条局限性来设计的最简可能模型。它在解释了集聚的同时保持了ER模型较短的平均节点间距离,这是通过在近似ER图的随机化结构和正则环[https://en.wikipedia.org/wiki/Lattice_(group) 点阵] regular ring lattice中进行内插得到的。因而,该模型至少能够部分解释许多网络中的“小世界”现象("small-world" phenomena),比如电网、[https://en.wikipedia.org/wiki/Caenorhabditis_elegans 秀丽隐杆线虫] C. elegans的神经网络、电影演员的社交网络、以及[https://en.wikipedia.org/wiki/Budding_yeast 芽殖酵母]脂肪代谢的信息交流
 
WS模型是针对于第一条局限性来设计的最简可能模型。它在解释了集聚的同时保持了ER模型较短的平均节点间距离,这是通过在近似ER图的随机化结构和正则环[https://en.wikipedia.org/wiki/Lattice_(group) 点阵] regular ring lattice中进行内插得到的。因而,该模型至少能够部分解释许多网络中的“小世界”现象("small-world" phenomena),比如电网、[https://en.wikipedia.org/wiki/Caenorhabditis_elegans 秀丽隐杆线虫] C. elegans的神经网络、电影演员的社交网络、以及[https://en.wikipedia.org/wiki/Budding_yeast 芽殖酵母]脂肪代谢的信息交流
<ref>
+
<ref>{{cite journal |doi=10.1371/journal.pcbi.1004264|pmid=26020510|title=Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network|journal=PLOS Computational Biology|volume=11|issue=5|pages=e1004264|year=2015|last1=Al-Anzi|first1=Bader|last2=Arpp|first2=Patrick|last3=Gerges|first3=Sherif|last4=Ormerod|first4=Christopher|last5=Olsman|first5=Noah|last6=Zinn|first6=Kai|bibcode=2015PLSCB..11E4264A|pmc=4447291}}</ref>
{{cite journal  
 
|doi:10.1371/journal.pcbi.1004264
 
|pmid:26020510
 
|title=Experimental and Computational Analysis of a Large Protein Network That Controls Fat Storage Reveals the Design Principles of a Signaling Network
 
|url = https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4447291
 
|journal=PLOS Computational Biology
 
|volume=11
 
|issue=5
 
|pages=e1004264
 
|year=2015
 
|last1=Al-Anzi
 
|first1=Bader
 
|last2=Arpp
 
|first2=Patrick
 
|last3=Gerges
 
|first3=Sherif
 
|last4=Ormerod
 
|first4=Christopher
 
|last5=Olsman
 
|first5=Noah
 
|last6=Zinn
 
|first6=Kai
 
|bibcode:2015PLSCB..11E4264A
 
|pmc:4447291
 
}}
 
</ref>
 
 
 
 +
  
 
==算法==
 
==算法==
第94行: 第35行:
 
#构建一个正则环点阵。该图有<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>,在该算法中不会出现)的情况。
 +
  
 
==特性==
 
==特性==
第113行: 第55行:
  
 
====集聚系数====
 
====集聚系数====
*对于环形点阵,[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]<ref name=AlbertBarabasi>
+
*对于环形点阵,[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]<ref name=AlbertBarabasi>{{cite journal
{{cite journal
 
 
  | author = Albert, R., Barabási, A.-L.
 
  | author = Albert, R., Barabási, A.-L.
 
  | year = 2002
 
  | year = 2002
 
  | title = Statistical mechanics of complex networks
 
  | title = Statistical mechanics of complex networks
  | arxiv:cond-mat/0106096
+
  | arxiv=cond-mat/0106096
 
  | journal = Reviews of Modern Physics
 
  | journal = Reviews of Modern Physics
 
  | volume = 74
 
  | volume = 74
 
  | issue = 1
 
  | issue = 1
 
  | pages = 47–97  
 
  | pages = 47–97  
  | doi : 10.1103/RevModPhys.74.47
+
  | doi = 10.1103/RevModPhys.74.47
| bibcode : 2002RvMP...74...47A
+
| bibcode = 2002RvMP...74...47A
  }}
+
  }}</ref> 为<math>C(0)=\frac{3(K-2)}{4(K-1)}</math>,因此随着K的增大趋向于<math>3/4</math>,且与系统规模无关;
</ref>为<math>C(0)=\frac{3(K-2)}{4(K-1)}</math>,因此随着K的增大趋向于<math>3/4</math>,且与系统规模无关;
 
 
*对于<math>\beta \rightarrow 1</math>的极限情况,集聚系数与经典随机图同阶,<math>C=\frac{K}{N-1}</math>,与系统规模成反比;区间内的集聚系数则十分接近于正则环点阵的系数值,只有在<math>\beta</math>相对较大时才会下降,这就导致了在一定区间范围内平均节点间距离下降迅速,而集聚系数保持相对恒定的情形,也就解释了“小世界”现象。
 
*对于<math>\beta \rightarrow 1</math>的极限情况,集聚系数与经典随机图同阶,<math>C=\frac{K}{N-1}</math>,与系统规模成反比;区间内的集聚系数则十分接近于正则环点阵的系数值,只有在<math>\beta</math>相对较大时才会下降,这就导致了在一定区间范围内平均节点间距离下降迅速,而集聚系数保持相对恒定的情形,也就解释了“小世界”现象。
*如果我们用巴拉特 Barrat和魏格特 Weigt的方法<ref name=Barrat2000>
+
*如果我们用巴拉特 Barrat和魏格特 Weigt的方法<ref name=Barrat2000>{{cite journal
{{cite journal
 
 
  | author = Barrat, A.
 
  | author = Barrat, A.
  | author2=Weigt, M.
+
  |author2=Weigt, M.
| year = 2000
+
  | year = 2000
 
  | title = On the properties of small-world network models
 
  | title = On the properties of small-world network models
 
  | journal = European Physical Journal B
 
  | journal = European Physical Journal B
第138行: 第77行:
 
  | issue = 3
 
  | issue = 3
 
  | pages = 547–560
 
  | pages = 547–560
  | url = http://www.springerlink.com/index/0HGUCD51T90CKB12.pdf
+
  | doi = 10.1007/s100510050067
| accessdate = 2008-02-26
+
| arxiv = cond-mat/9903411}}</ref>,即是用一个节点的相邻节点之间的平均边数和这些相邻节点之间可能的平均边数之商来定义集聚系数<math>C'(\beta)</math>,或者说:
| doi : 10.1007/s100510050067
 
| format=PDF
 
| arxiv : cond-mat/9903411
 
}}
 
</ref> ,即是用一个节点的相邻节点之间的平均边数和这些相邻节点之间可能的平均边数之商来定义集聚系数<math>C'(\beta)</math>,或者说:
 
 
   
 
   
 
::<math>C'(\beta)=\frac{3\times \text{number of triangles}}{\text{number of connected triples}}</math>
 
::<math>C'(\beta)=\frac{3\times \text{number of triangles}}{\text{number of connected triples}}</math>

2020年5月6日 (三) 11:28的版本

WS小世界模型 Watts–Strogatz model 是一种随机图生成模型,其生成的图具有小世界属性,包括较短的平均节点间距离和高集聚系数。该模型由邓肯 J. 沃茨 Duncan J. Watts斯蒂文·史楚盖兹 Steven Strogatz在1998年两人联合发表于《自然》的论文中提出 [1] 。Watts在其广受欢迎的科学读物《Six Degrees》中使用[math]\displaystyle{ \beta }[/math]来阐述该模型,这之后,该模型也被称为(沃茨)[math]\displaystyle{ \beta }[/math] 模型。


模型基本原理

Random_graph的正式研究可追溯至 保尔·厄多斯 Paul Erdős阿尔弗烈德·瑞利 Alfréd Rényi的工作 [2] 。他们所考虑的图,也就是现在所谓的经典图或ER随机图模型,给许多应用提供了简单而强有力的模型。


但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性:

  1. 不能生成局部集聚 local clustering 和三元闭合 triadic closures(网络有三元闭合、三元闭包等释义)。相反,因为图中两个节点有恒定、随机且独立的概率彼此相连,ER随机图模型集聚系数较低。
  2. 不能解释中心节点 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](假定K为偶数)和一个特殊的参数[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]条边的无向图

  1. 构建一个正则环点阵。该图有[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]
  2. 对于每个节点[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模型。


我们感兴趣的三个特性是平均节点间距离 average path length、集聚系数 clustering coefficient 和度分布degree distribution。

Watts–Strogatz 小世界模型,由igraph生成,Cytoscape 2.5进行可视化,100个节点
文件:Watts strogatz.svg
Watts_strogatz图


平均节点间距离

  • 对于环形点阵,平均节点间距离是[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]


度分布

[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模型也暗含了固定的节点数,所以也不能用来描述网络的生长。

参见


参考文献

  1. 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.
  2. Erdos, P. (1960). "Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Math. Inst. Hung. Acad. Sci. 5: 17.
  3. 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.
  4. 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.
  5. 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)
  6. 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.



本中文词条由用户Iceblaze9527参与编译,flynn审校,张江总审校,乐多多编辑,欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。