Watts–Strogatz model

<h2 id="rationale-for-the-model">Rationale for the model</h2>
<p>The formal study of <a href="/facts/Random_graph/gfQhq1Sz">random graphs</a> dates back to the work of <a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Paul Erdős</a> and <a href="/facts/Alfr%25C3%25A9d_R%25C3%25A9nyi/q7Dx7fgB">Alfréd Rényi</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> The graphs they considered, now known as the classical or <a href="/facts/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model/F6BQ8gIj">Erdős–Rényi (ER)</a> graphs, offer a simple and powerful model with many applications.
</p><p>However the <a href="/facts/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model/F6BQ8gIj">ER</a> graphs do not have two important properties observed in many real-world networks:
</p>
<ol><li>They do not generate local clustering and <a href="/facts/Triadic_closure/g2mwv9p7">triadic closures</a>. Instead, because they have a constant, random, and independent probability of two nodes being connected, ER graphs have a low <a href="/facts/Clustering_coefficient/yB6Q3gk2">clustering coefficient</a>.</li>
<li>They do not account for the formation of hubs. Formally, the <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> distribution of ER graphs converges to a <a href="/facts/Poisson_distribution/CvCzXkHr">Poisson distribution</a>, rather than a <a href="/facts/Power_law/DhAjYwwz">power law</a> observed in many real-world, <a href="/facts/Scale-free_networks/2ENlcjX3">scale-free networks</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ol>
<p>The Watts and Strogatz model was designed as the simplest possible model that addresses the first of the two limitations. It accounts for clustering while retaining the short average path lengths of the ER model. It does so by interpolating between a randomized structure close to ER graphs and a regular ring <a href="/facts/Lattice_(group)/2ls9Iv9N">lattice</a>. Consequently, the model is able to at least partially explain the "small-world" phenomena in a variety of networks, such as the power grid, neural network of <a href="/facts/Caenorhabditis_elegans/XJVJzPn2">C. elegans</a>, networks of movie actors, or fat-metabolism communication in <a href="/facts/Budding_yeast/sX9MGFrz">budding yeast</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="algorithm">Algorithm</h2>

<p>Given the desired number of nodes 
  
    
      
        N
      
    
    {\displaystyle N}
  
, the mean <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 
  
    
      
        K
      
    
    {\displaystyle K}
  
 (assumed to be an even integer), and a parameter 
  
    
      
        β
      
    
    {\displaystyle \beta }
  
, all satisfying 
  
    
      
        0
        ≤
        β
        ≤
        1
      
    
    {\displaystyle 0\leq \beta \leq 1}
  
 and 
  
    
      
        N
        ≫
        K
        ≫
        ln
        ⁡
        N
        ≫
        1
      
    
    {\displaystyle N\gg K\gg \ln N\gg 1}
  
, the model constructs an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> with 
  
    
      
        N
      
    
    {\displaystyle N}
  
 nodes and 
  
    
      
        
          
            
              N
              K
            
            2
          
        
      
    
    {\displaystyle {\frac {NK}{2}}}
  
 edges in the following way:
</p>
<ol><li>Construct a regular ring lattice, a graph with 
  
    
      
        N
      
    
    {\displaystyle N}
  
 nodes each connected to 
  
    
      
        K
      
    
    {\displaystyle K}
  
 neighbors, 
  
    
      
        K
        
          /
        
        2
      
    
    {\displaystyle K/2}
  
 on each side. That is, if the nodes are labeled  
  
    
      
        0
        …
        
          N
          −
          1
        
      
    
    {\displaystyle 0\ldots {N-1}}
  
, there is an edge 
  
    
      
        (
        i
        ,
        j
        )
      
    
    {\displaystyle (i,j)}
  
 if and only if 
  
    
      
        0
        <
        
          |
        
        i
        −
        j
        
          |
        
         
        
          m
          o
          d
        
         
        
          (
          
            N
            −
            1
            −
            
              
                K
                2
              
            
          
          )
        
        ≤
        
          
            K
            2
          
        
        .
      
    
    {\displaystyle 0<|i-j|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.}
  
</li>
<li>For every node 
  
    
      
        i
        =
        0
        ,
        …
        ,
        
          N
          −
          1
        
      
    
    {\displaystyle i=0,\dots ,{N-1}}
  
 take every edge connecting 
  
    
      
        i
      
    
    {\displaystyle i}
  
 to its 
  
    
      
        K
        
          /
        
        2
      
    
    {\displaystyle K/2}
  
 rightmost neighbors, that is every edge 
  
    
      
        (
        i
        ,
        j
        )
      
    
    {\displaystyle (i,j)}
  
 such that 
  
    
      
        0
        <
        (
        j
        −
        i
        )
         
        
          m
          o
          d
        
         
        N
        ≤
        K
        
          /
        
        2
      
    
    {\displaystyle 0<(j-i)\ \mathrm {mod} \ N\leq K/2}
  
, and rewire it with probability 
  
    
      
        β
      
    
    {\displaystyle \beta }
  
. Rewiring is done by replacing 
  
    
      
        (
        i
        ,
        j
        )
      
    
    {\displaystyle (i,j)}
  
 with 
  
    
      
        (
        i
        ,
        k
        )
      
    
    {\displaystyle (i,k)}
  
 where 
  
    
      
        k
      
    
    {\displaystyle k}
  
 is chosen uniformly at random from all possible nodes while avoiding self-loops (
  
    
      
        k
        ≠
        i
      
    
    {\displaystyle k\neq i}
  
) and link duplication (there is no edge 
  
    
      
        (
        i
        ,
        
          
            k
            ′
          
        
        )
      
    
    {\displaystyle (i,{k'})}
  
 with 
  
    
      
        
          k
          ′
        
        =
        k
      
    
    {\displaystyle k'=k}
  
 at this point in the algorithm).</li></ol>
<h2 id="properties">Properties</h2>
<p>The underlying lattice structure of the model produces a locally clustered network, while the randomly rewired links dramatically reduce the <a href="/facts/Average_path_length/kksqv8wG">average path lengths</a>. The algorithm introduces about 
  
    
      
        β
        
          
            
              N
              K
            
            2
          
        
      
    
    {\displaystyle \beta {\frac {NK}{2}}}
  
 of such non-lattice edges. Varying 
  
    
      
        β
      
    
    {\displaystyle \beta }
  
 makes it possible to interpolate between a regular lattice (
  
    
      
        β
        =
        0
      
    
    {\displaystyle \beta =0}
  
) and a structure close to an <a href="/facts/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model/F6BQ8gIj">Erdős–Rényi random graph</a> 
  
    
      
        G
        (
        N
        ,
        p
        )
      
    
    {\displaystyle G(N,p)}
  
 with 
  
    
      
        p
        =
        
          
            K
            
              N
              −
              1
            
          
        
      
    
    {\displaystyle p={\frac {K}{N-1}}}
  
 at 
  
    
      
        β
        =
        1
      
    
    {\displaystyle \beta =1}
  
. It does not approach the actual ER model since every node will be connected to at least 
  
    
      
        K
        
          /
        
        2
      
    
    {\displaystyle K/2}
  
 other nodes.
</p><p>The three properties of interest are the <a href="/facts/Average_path_length/kksqv8wG">average path length</a>, the <a href="/facts/Clustering_coefficient/yB6Q3gk2">clustering coefficient</a>, and the <a href="/facts/Degree_distribution/qVlXFfbA">degree distribution</a>.
</p>
<h3>Average path length</h3>
<p>For a ring lattice, the average path length<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> is 
  
    
      
        ℓ
        (
        0
        )
        ≈
        N
        
          /
        
        2
        K
        ≫
        1
      
    
    {\displaystyle \ell (0)\approx N/2K\gg 1}
  
 and scales linearly with the system size. In the <a href="/facts/Limiting_case_(mathematics)/UEehGCom">limiting case</a> of 
  
    
      
        β
        →
        1
      
    
    {\displaystyle \beta \rightarrow 1}
  
, the graph approaches a random graph with 
  
    
      
        ℓ
        (
        1
        )
        ≈
        
          
            
              ln
              ⁡
              N
            
            
              ln
              ⁡
              K
            
          
        
      
    
    {\displaystyle \ell (1)\approx {\frac {\ln N}{\ln K}}}
  
, while not actually converging to it. In the intermediate region 
  
    
      
        0
        <
        β
        <
        1
      
    
    {\displaystyle 0<\beta <1}
  
, the average path length falls very rapidly with increasing 
  
    
      
        β
      
    
    {\displaystyle \beta }
  
, quickly approaching its limiting value.
</p>
<h3>Clustering coefficient</h3>
<p>For the ring lattice the <a href="/facts/Clustering_coefficient/yB6Q3gk2">clustering coefficient</a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> 
  
    
      
        C
        (
        0
        )
        =
        
          
            
              3
              (
              K
              −
              2
              )
            
            
              4
              (
              K
              −
              1
              )
            
          
        
      
    
    {\displaystyle C(0)={\frac {3(K-2)}{4(K-1)}}}
  
, and so tends to 
  
    
      
        3
        
          /
        
        4
      
    
    {\displaystyle 3/4}
  
 as 
  
    
      
        K
      
    
    {\displaystyle K}
  
 grows, independently of the system size.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> In the limiting case of 
  
    
      
        β
        →
        1
      
    
    {\displaystyle \beta \rightarrow 1}
  
 the clustering coefficient is of the same order as the clustering coefficient for classical random graphs, 
  
    
      
        C
        =
        K
        
          /
        
        (
        N
        −
        1
        )
      
    
    {\displaystyle C=K/(N-1)}
  
 and is thus inversely proportional to the system size. In the intermediate region the clustering coefficient remains quite close to its value for the regular lattice, and only falls at relatively high 
  
    
      
        β
      
    
    {\displaystyle \beta }
  
. This results in a region where the average path length falls rapidly, but the clustering coefficient does not, explaining the "small-world" phenomenon.
</p>
If we use the Barrat and Weigt<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> measure for clustering 
  
    
      
        
          C
          ′
        
        (
        β
        )
      
    
    {\displaystyle C'(\beta )}
  
 defined as the fraction between the average number of edges between the neighbors of a node and the average number of possible edges between these neighbors, or, alternatively,

C
          ′
        
        (
        β
        )
        ≡
        
          
            
              3
              ×
              
                number of triangles
              
            
            number of connected triples
          
        
      
    
    {\displaystyle C'(\beta )\equiv {\frac {3\times {\text{number of triangles}}}{\text{number of connected triples}}}}

then we get 
  
    
      
        
          C
          ′
        
        (
        β
        )
        ∼
        C
        (
        0
        )
        (
        1
        −
        β
        
          )
          
            3
          
        
        .
      
    
    {\displaystyle C'(\beta )\sim C(0)(1-\beta )^{3}.}

<h3>Degree distribution</h3>
<p>The degree distribution in the case of the ring lattice is just a <a href="/facts/Dirac_delta_function/V8PjRP8T">Dirac delta function</a> centered at 
  
    
      
        K
      
    
    {\displaystyle K}
  
. The degree distribution for a large number of nodes and 
  
    
      
        0
        <
        β
        <
        1
      
    
    {\displaystyle 0<\beta <1}
  
 can be written as,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>
</p>

P
        (
        k
        )
        ≈
        
          ∑
          
            n
            =
            0
          
          
            f
            (
            k
            ,
            K
            )
          
        
        
          
            
              (
            
            
              
                K
                
                  /
                
                2
              
              
                n
              
            
            
              )
            
          
        
        (
        1
        −
        β
        
          )
          
            n
          
        
        
          β
          
            K
            
              /
            
            2
            −
            n
          
        
        
          
            
              (
              β
              K
              
                /
              
              2
              
                )
                
                  k
                  −
                  K
                  
                    /
                  
                  2
                  −
                  n
                
              
            
            
              (
              k
              −
              K
              
                /
              
              2
              −
              n
              )
              !
            
          
        
        
          e
          
            −
            β
            K
            
              /
            
            2
          
        
        ,
      
    
    {\displaystyle P(k)\approx \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},}

<p>where 
  
    
      
        
          k
          
            i
          
        
      
    
    {\displaystyle k_{i}}
  
 is the number of edges that the 
  
    
      
        
          i
          
            th
          
        
      
    
    {\displaystyle i^{\text{th}}}
  
 node has or its degree. Here  
  
    
      
        k
        ≥
        K
        
          /
        
        2
      
    
    {\displaystyle k\geq K/2}
  
, and 
  
    
      
        f
        (
        k
        ,
        K
        )
        =
        min
        (
        k
        −
        K
        
          /
        
        2
        ,
        K
        
          /
        
        2
        )
      
    
    {\displaystyle f(k,K)=\min(k-K/2,K/2)}
  
. The shape of the degree distribution is similar to that of a random graph and has a pronounced peak at 
  
    
      
        k
        =
        K
      
    
    {\displaystyle k=K}
  
 and decays exponentially for large 
  
    
      
        
          |
        
        k
        −
        K
        
          |
        
      
    
    {\displaystyle |k-K|}
  
. The topology of the network is relatively homogeneous, meaning that all nodes are of similar degree.
</p>
<h2 id="limitations">Limitations</h2>
<p>The major limitation of the model is that it produces an unrealistic <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> distribution. In contrast, real networks are often <a href="/facts/Scale-free_networks/2ENlcjX3">scale-free networks</a> inhomogeneous in degree, having hubs and a scale-free degree distribution. Such networks are better described in that respect by the <a href="/facts/Preferential_attachment/9u0eN8nd">preferential attachment</a> family of models, such as the <a href="/facts/BA_model/lNqLTRsP">Barabási–Albert (BA) model</a>. (On the other hand, the Barabási–Albert model fails to produce the high levels of clustering seen in real networks, a shortcoming not shared by the Watts and Strogatz model. Thus, neither the Watts and Strogatz model nor the Barabási–Albert model should be viewed as fully realistic.)
</p><p>The Watts and Strogatz model also implies a fixed number of nodes and thus cannot be used to model network growth.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Small-world_networks/dALPpt9m">Small-world networks</a></li>
<li><a href="/facts/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model/F6BQ8gIj">Erdős–Rényi (ER) model</a></li>
<li><a href="/facts/Barab%25C3%25A1si%25E2%2580%2593Albert_model/lNqLTRsP">Barabási–Albert model</a></li>
<li><a href="/facts/Social_network_analysis/CsJIFjVw">Social networks</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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. S2CID 4429113. Archived (PDF) from the original on 2020-10-26. Retrieved 2018-05-18. <a href="/wiki/Duncan_J._Watts" target="_blank">/wiki/Duncan_J._Watts</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Erdos, P. (1960). "Publications Mathematicae 6, 290 (1959); P. Erdos, A. Renyi". Publ. Math. Inst. Hung. Acad. Sci. 5: 17. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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. S2CID 14452443. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>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. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4447291" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4447291</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>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. S2CID 4429113. Archived (PDF) from the original on 2020-10-26. Retrieved 2018-05-18. <a href="/wiki/Duncan_J._Watts" target="_blank">/wiki/Duncan_J._Watts</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>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. S2CID 60545.{{cite journal}}:  CS1 maint: multiple names: authors list (link) <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>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. S2CID 13483229. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>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. S2CID 13483229. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>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. S2CID 13483229. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
</ol>

Watts–Strogatz model open-in-new

Watts–Strogatz model