Editing Small-world network (section)

==Construction of small-world networks==
{{See also|Diffusion-limited aggregation|Pattern formation}}

The main mechanism to construct small-world networks is the [[Watts and Strogatz Model|Watts–Strogatz mechanism]].

Small-world networks can also be introduced with time-delay,<ref>{{cite journal | vauthors = Yang XS | s2cid = 119109068 | title = Fractals in small-world networks with time-delay | journal = Chaos, Solitons & Fractals | volume = 13 | issue = 2 | pages = 215–219 | date = 2002 | doi = 10.1016/S0960-0779(00)00265-4 | bibcode = 2002CSF....13..215Y | arxiv = 1003.4949 }}</ref> which will not only produce fractals but also chaos<ref>{{cite journal | vauthors = Yang XS | s2cid = 38158445 | title = Chaos in small-world networks. | journal = Physical Review E | date = March 2001 | volume = 63 | issue = 4 | pages = 046206 | doi = 10.1103/PhysRevE.63.046206 | pmid = 11308929 | bibcode = 2001PhRvE..63d6206Y | arxiv = 1003.4940 }}</ref> under the right conditions, or transition to chaos in dynamics networks.<ref>{{cite journal | vauthors = Yuan WJ, Luo XS, Jiang PQ, Wang BH, Fang JQ | title = Transition to chaos in small-world dynamical network. | journal = Chaos, Solitons & Fractals | date = August 2008 | volume = 37 | issue = 3 | pages = 799–806 | doi = 10.1016/j.chaos.2006.09.077 | bibcode = 2008CSF....37..799Y }}</ref>

Soon after the publication of [[Watts and Strogatz Model|Watts–Strogatz mechanism]], approaches have been developed by [[Alireza Mashaghi|Mashaghi]] and co-workers to generate network models that exhibit high degree correlations, while preserving the desired degree distribution and small-world properties. These approaches are based on edge-dual transformation and can be used to generate analytically solvable small-world network models for research into these systems.<ref>A Ramezanpour, V Karimipour, A Mashaghi, Generating correlated networks from uncorrelated ones. Physical Review E 67(4 Pt 2):046107 (2003) doi: 10.1103/PhysRevE.67.046107</ref>

[[degree diameter|Degree–diameter]] graphs are constructed such that the number of neighbors each vertex in the network has is bounded, while the distance from any given vertex in the network to any other vertex (the [[Diameter (graph theory)|diameter]] of the network) is minimized. Constructing such small-world networks is done as part of the effort to find graphs of order close to the [[Moore graph|Moore bound]].

Another way to construct a small world network from scratch is given in Barmpoutis ''et al.'',<ref name=BarmpoutisMurray2010>{{cite arXiv | vauthors = Barmpoutis D, Murray RM | title = Networks with the Smallest Average Distance and the Largest Average Clustering | eprint = 1007.4031 | year = 2010 | class = q-bio.MN }}</ref> where a network with very small average distance and very large average clustering is constructed. A fast algorithm of constant complexity is given, along with measurements of the robustness of the resulting graphs. Depending on the application of each network, one can start with one such "ultra small-world" network, and then rewire some edges, or use several small such networks as subgraphs to a larger graph.

Small-world properties can arise naturally in social networks and other real-world systems via the process of [[dual-phase evolution]].  This is particularly common where time or spatial constraints limit the addition of connections between vertices The mechanism generally involves periodic shifts between phases, with connections being added during a "global" phase and  being reinforced or removed during a "local" phase.

Small-world networks can change from scale-free class to broad-scale class whose connectivity distribution has a sharp cutoff following a power law regime due to constraints limiting the addition of new links.<ref name="Classes networks">{{cite journal
|vauthors = Amaral LA, Scala A, Barthelemy M, Stanley HE
|title = Classes of small-world networks
|journal = Proceedings of the National Academy of Sciences of the United States of America|volume = 97|issue = 21|pages = 11149–52
|date = October 2000
|pmid = 11005838
|pmc = 17168
|doi = 10.1073/pnas.200327197
|arxiv = cond-mat/0001458
|bibcode = 2000PNAS...9711149A
|doi-access = free
}}</ref> For strong enough constraints, scale-free networks can even become single-scale networks whose connectivity distribution is characterized as fast decaying.<ref name="Classes networks" /> It was also shown analytically that scale-free networks are ultra-small, meaning that the distance scales according to <math>L \propto \log \log N</math>.<ref>{{cite journal | vauthors = Cohen R, Havlin S | title = Scale-free networks are ultrasmall | journal = Physical Review Letters | volume = 90 | issue = 5 | pages = 058701 | date = 2003 | doi = 10.1103/PhysRevLett.90.058701 | pmid = 12633404 | arxiv = cond-mat/0205476 | bibcode = 2003PhRvL..90e8701C | s2cid = 10508339 | url = https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.90.058701 }}</ref>