更改

'''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> 模型。

==模型基本原理==

==模型基本原理==

对[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

  | volume = 5

  | volume = 5

  | pages = 17

  | pages = 17

}}

}}</ref>  

</ref>

。他们所考虑的图，也就是现在所谓的经典图或[[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随机图模型]]的[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

|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

|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>个节点，每个节点和<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/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

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