集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

更改

WS小世界模型 (查看源代码)

2020年5月6日 (三) 10:46的版本

删除174字节 、 2020年5月6日 (三) 10:46
无编辑摘要
第3行： 第3行：       −
'''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 Duncan J. Watts]（邓肯 J. 沃茨）和[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/邓肯 J. 沃茨 Duncan_J._Watts 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  
 
{{Cite journal  
第24行： 第24行：  
</ref>
 
</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> 模型。
 +
 +
 
==模型基本原理==
 
==模型基本原理==
−
对[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
第36行： 第38行：  
}}
 
}}
 
</ref>
 
</ref>
−
。他们所考虑的图，也就是现在所谓的经典图或[http://wiki.swarma.net/index.php/ER随机图模型 Erdős–Rényi (ER) 图]，给许多应用提供了简单而强有力的模型。
+
。他们所考虑的图，也就是现在所谓的经典图或[[ER随机图模型]]，给许多应用提供了简单而强有力的模型。
 +
 
    
但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性：
 
但ER图并不具有我们观察到的许多实际网络所拥有的两个重要属性：
   −
#不能生成局部集聚（local clustering）和[https://en.wikipedia.org/wiki/Triadic_closure 三元闭合]（triadic closures，网络有三元闭合、三元闭包等释义）。相反，因为图中两个节点有恒定、随机且独立的概率彼此相连，[http://wiki.swarma.net/index.php/ER随机图模型 ER图]的[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]较低。
+
#不能生成局部集聚 local clustering 和[https://en.wikipedia.org/wiki/三元闭合 Triadic_closure]（triadic closures，网络有三元闭合、三元闭包等释义）。相反，因为图中两个节点有恒定、随机且独立的概率彼此相连，[[R随机图模型 ER图]的[https://en.wikipedia.org/wiki/Clustering_coefficient 集聚系数]]较低。
−
#不能解释中心节点（hub）的构成。在形式上，[http://wiki.swarma.net/index.php/ER随机图模型 ER图]的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]分布收敛于[https://en.wikipedia.org/wiki/Poisson_distribution 泊松分布]，而不是我们在现实世界中观测到的、[[无标度网络]]（scale-free networks）的[[幂律分布]]（power law）
+
#不能解释中心节点 hub 的构成。在形式上，[[ER随机图模型 ER图]]的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度]分布收敛于[https://en.wikipedia.org/wiki/泊松分布 Poisson_distribution ]，而不是我们在现实世界中观测到的、[[无标度网络]] scale-free networks 的[[幂律分布]] power law
 
<ref name=Ravasz2002>
 
<ref name=Ravasz2002>
 
{{cite journal
 
{{cite journal
第58行： 第61行：  
</ref>。
 
</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  
 
{{cite journal  
第87行： 第91行：  
</ref>
 
</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>，平均[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>\frac{NK}{2}</math>条边的[https://en.wikipedia.org/wiki/Undirected_graph#Undirected_graph 无向图]：
 
该模型以下述方式构建了一个具有<math>N</math>个节点，<math>\frac{NK}{2}</math>条边的[https://en.wikipedia.org/wiki/Undirected_graph#Undirected_graph 无向图]：
 +
    
#构建一个正则环点阵。该图有<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/Average_path_length 平均节点间距离]。其算法引入了大约<math>\beta \tfrac{NK}{2}</math>条非点阵边。改变<math>\beta</math>的值可以在正则环点阵（<math>\beta =0</math>）和接近[http://wiki.swarma.net/index.php/ER随机图模型 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 平均节点间距离]。其算法引入了大约<math>\beta \tfrac{NK}{2}</math>条非点阵边。改变<math>\beta</math>的值可以在正则环点阵（<math>\beta =0</math>）和接近[http://wiki.swarma.net/index.php/ER随机图模型 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）。
+
 
 +
我们感兴趣的三个特性是[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_strogatz.svg |200px|thumb|right|Watts_strogatz图]]
 
[[File:Watts_strogatz.svg |200px|thumb|right|Watts_strogatz图]]
 +
    
====平均节点间距离====
 
====平均节点间距离====
第109行： 第119行：  
   
 
   
 
*在区间<math>(0<\beta <1)</math>内，平均节点间距离随着<math>\beta</math>的增大迅速下降，并很快接近于其极限值。
 
*在区间<math>(0<\beta <1)</math>内，平均节点间距离随着<math>\beta</math>的增大迅速下降，并很快接近于其极限值。
 +
    
====集聚系数====
 
====集聚系数====
第126行： 第137行：  
</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.
第148行： 第160行：  
   
 
   
 
:可得出<math>C'(\beta)\sim C(0)(1-\beta)^{3}</math>
 
:可得出<math>C'(\beta)\sim C(0)(1-\beta)^{3}</math>
 +
    
====度分布====
 
====度分布====
第159行： 第172行：  
   
 
   
 
*网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。
 
*网络的拓扑相对而言是齐次的，也即所有的节点都有相同的度。
 +
    
==局限性==
 
==局限性==
第165行： 第179行：     
WS模型也暗含了固定的节点数，所以也不能用来描述网络的生长。
 
WS模型也暗含了固定的节点数，所以也不能用来描述网络的生长。
 +
    
==参见==
 
==参见==
第171行： 第186行：  
*[http://wiki.swarma.net/index.php/BA%E7%BD%91%E7%BB%9C%E6%A8%A1%E5%9E%8B Barabási–Albert模型]
 
*[http://wiki.swarma.net/index.php/BA%E7%BD%91%E7%BB%9C%E6%A8%A1%E5%9E%8B Barabási–Albert模型]
 
*[[社交网络]]
 
*[[社交网络]]
 +
    
==参考文献==
 
==参考文献==
乐多多
763

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/6838”