更改

删除956字节 、 2020年5月6日 (三) 20:26
无编辑摘要
第3行: 第3行:  
|description=小世界模型,集智
 
|description=小世界模型,集智
 
}}
 
}}
'''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 '''是一种[[随机图]]生成模型,其生成的图具有[[小世界属性]],包括较短的平均节点间距离 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>
 
。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> 模型。
第23行: 第23行:  
但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性:
 
但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性:
   −
#不能生成局部集聚 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随机图模型]]的集聚系数较低。
#不能解释中心节点 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>
+
#不能解释中心节点 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>
      −
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,比如电网、秀丽隐杆线虫 C. elegans的神经网络、电影演员的社交网络、以及芽殖酵母脂肪代谢的信息交流
 
<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>
 
<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>
 
 
    
==算法==
 
==算法==
假设所期望的节点数为<math>N</math>,平均[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]为<math>K</math>(假定K为偶数)和一个特殊的参数<math>\beta</math> ,满足<math>0\leq \beta \leq 1</math>,且<math>N\gg K\gg lnN\gg 1</math>。
+
假设所期望的节点数为<math>N</math>,平均度为<math>K</math>(假定K为偶数)和一个特殊的参数<math>\beta</math> ,满足<math>0\leq \beta \leq 1</math>,且<math>N\gg K\gg lnN\gg 1</math>。
      第41行: 第41行:     
==特性==
 
==特性==
该模型基础的点阵图结构产生了局部集聚的网络,而随机的重新连接则大大减少了[https://en.wikipedia.org/wiki/Average_path_length 平均节点间距离]。其算法引入了大约<math>\beta \tfrac{NK}{2}</math>条非点阵边。改变<math>\beta</math>的值可以在正则环点阵(<math>\beta =0</math>)和接近[[ER随机图]]的结构<math>(\beta =</math><math>1</math>,<math>G</math><math>(N,p)</math>满足<math>p=\frac {K}{N-1})</math>间进行内插。由于每一个节点都与至少<math>K/2</math>个其他节点相连,该模型并没符合真实的ER模型。
+
该模型基础的点阵图结构产生了局部集聚的网络,而随机的重新连接则大大减少了平均节点间距离。其算法引入了大约<math>\beta \tfrac{NK}{2}</math>条非点阵边。改变<math>\beta</math>的值可以在正则环点阵(<math>\beta =0</math>)和接近[[ER随机图]]的结构<math>(\beta =</math><math>1</math>,<math>G</math><math>(N,p)</math>满足<math>p=\frac {K}{N-1})</math>间进行内插。由于每一个节点都与至少<math>K/2</math>个其他节点相连,该模型并没符合真实的ER模型。
      −
我们感兴趣的三个特性是[https://en.wikipedia.org/wiki/Average_path_length 平均节点间距离] average path length、[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数] clustering coefficient [https://en.wikipedia.org/wiki/Degree_distribution 度分布]degree distribution。
+
我们感兴趣的三个特性是'''平均节点间距离'''、'''集聚系数''''''度分布'''。
 
[[File:Watts-Strogatz_small-world_model_100nodes.png|200px|thumb|right|Watts–Strogatz 小世界模型,由igraph生成,Cytoscape 2.5进行可视化,100个节点]]
 
[[File:Watts-Strogatz_small-world_model_100nodes.png|200px|thumb|right|Watts–Strogatz 小世界模型,由igraph生成,Cytoscape 2.5进行可视化,100个节点]]
 
[[File:Watts_strogatz1.png |200px|thumb|right|Watts_strogatz图]]
 
[[File:Watts_strogatz1.png |200px|thumb|right|Watts_strogatz图]]
第52行: 第52行:  
*对于环形点阵,平均节点间距离是<math>\ell(0)=N/2K\gg 1</math>,且随系统规模线性变化;
 
*对于环形点阵,平均节点间距离是<math>\ell(0)=N/2K\gg 1</math>,且随系统规模线性变化;
 
   
 
   
*对于[https://en.wikipedia.org/wiki/Limiting_case_(mathematics) 极限情况]<math>(\beta \rightarrow 1)</math>,该图趋近于随机图,平均节点间距离<math>\ell(1)=\frac{lnN}{lnK}</math>,但实际上不收敛于此;
+
*对于极限情况<math>(\beta \rightarrow 1)</math>,该图趋近于随机图,平均节点间距离<math>\ell(1)=\frac{lnN}{lnK}</math>,但实际上不收敛于此;
 
   
 
   
 
*在区间<math>(0<\beta <1)</math>内,平均节点间距离随着<math>\beta</math>的增大迅速下降,并很快接近于其极限值。
 
*在区间<math>(0<\beta <1)</math>内,平均节点间距离随着<math>\beta</math>的增大迅速下降,并很快接近于其极限值。
第58行: 第58行:     
====集聚系数====
 
====集聚系数====
*对于环形点阵,[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]<ref name=AlbertBarabasi>{{cite journal
+
*对于环形点阵,集聚系数<ref name=AlbertBarabasi>{{cite journal
 
  | author = Albert, R., Barabási, A.-L.
 
  | author = Albert, R., Barabási, A.-L.
 
  | year = 2002
 
  | year = 2002
第101行: 第101行:     
==局限性==
 
==局限性==
该模型的主要局限性是会产生不符实际的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]分布。相较而言,现实中的网络通常是非齐次的[[无标度网络]],有中心节点的存在和无标度的度分布。考虑到此,这样的网络可以用[[偏好依附模型]] preferential attachment model来更好的描述,比如[[BA网络模型]]
+
该模型的主要局限性是会产生不符实际的度分布。相较而言,现实中的网络通常是非齐次的[[无标度网络]],有中心节点的存在和无标度的度分布。考虑到此,这样的网络可以用[[偏好依附模型 preferential attachment model]]来更好的描述,比如[[BA网络模型]]。(另一方面,BA模型没有产生真实网络中出现的高集聚特性,而这个弱点是WS模型所不具备的。因此,WS模型和BA模型均不应被看成是完全符合实际的。)WS模型也暗含了固定的节点数,所以也不能用来描述网络的生长。
(另一方面,BA模型没有产生真实网络中出现的高集聚特性,而这个弱点是WS模型所不具备的。因此,WS模型和BA模型均不应被看成是完全符合实际的。)
  −
 
  −
WS模型也暗含了固定的节点数,所以也不能用来描述网络的生长。
        第110行: 第107行:  
*[[小世界网络]]
 
*[[小世界网络]]
 
* [[ER随机图模型]]
 
* [[ER随机图模型]]
*[http://wiki.swarma.net/index.php/BA%E7%BD%91%E7%BB%9C%E6%A8%A1%E5%9E%8B Barabási–Albert模型]
+
*[[BA网络模型]]
 
*[[社交网络]]
 
*[[社交网络]]
  
7,129

个编辑