Editing Small-world network (section)

==Properties of small-world networks==
Small-world networks tend to contain [[clique (graph theory)|cliques]], and near-cliques, meaning sub-networks which have connections between almost any two nodes within them. This follows from the defining property of a high [[clustering coefficient]]. Secondly, most pairs of nodes will be connected by at least one short path. This follows from the defining property that the mean-shortest path length be small. Several other properties are often associated with small-world networks. Typically there is an over-abundance of ''hubs'' – nodes in the network with a high number of connections (known as high [[degree (graph theory)|degree]] nodes). These hubs serve as the common connections mediating the short path lengths between other edges. By analogy, the small-world network of airline flights has a small mean-path length (i.e. between any two cities you are likely to have to take three or fewer flights) because many flights are routed through [[airline hub|hub]] cities. This property is often analyzed by considering the fraction of nodes in the network that have a particular number of connections going into them (the degree distribution of the network). Networks with a greater than expected number of hubs will have a greater fraction of nodes with high degree, and consequently the degree distribution will be enriched at high degree values. This is known colloquially as a [[fat-tailed distribution]]. Graphs of very different topology qualify as small-world networks as long as they satisfy the two definitional requirements above.

Network small-worldness has been quantified by a small-coefficient, <math>\sigma</math>, calculated by comparing clustering and path length of a given network to an [[Erdős–Rényi model]] with same degree on average.<ref name="D. Humphries, K 1639">{{cite journal | doi = 10.1098/rspb.2005.3354 | volume=273 | title=The brainstem reticular formation is a small-world, not scale-free, network | year=2006 | journal=Proceedings of the Royal Society B: Biological Sciences | pages=503–511 | vauthors=Humphries MD| issue=1585 | pmid=16615219 | pmc=1560205 }}</ref><ref>{{cite journal | vauthors = Humphries MD, Gurney K | title = Network 'small-world-ness': a quantitative method for determining canonical network equivalence | journal = PLOS ONE | volume = 3 | issue = 4 | pages = e0002051 | date = April 2008 | pmid = 18446219 | pmc = 2323569 | doi = 10.1371/journal.pone.0002051 | bibcode = 2008PLoSO...3.2051H | doi-access = free }}</ref>

:<math>\sigma = \frac \frac C {C_r} \frac L {L_r}</math> 
:if <math>\sigma > 1</math> (<math display="inline">C \gg C_r</math> and <math display="inline">L \approx {L_r}</math>), network is small-world. However, this metric is known to perform poorly because it is heavily influenced by the network's size.<ref name=":0" /><ref name=":1">{{Cite journal
|last=Neal|first=Zachary P.
|name-list-style = vanc
|date=2017
|title=How small is it? Comparing indices of small worldliness
|journal=Network Science
|language=en
|volume=5
|issue=1
|pages=30–44
|doi=10.1017/nws.2017.5
|s2cid=3844585
|issn=2050-1242}}</ref>

Another method for quantifying network small-worldness utilizes the original definition of the small-world network comparing the clustering of a given network to an equivalent lattice network and its path length to an equivalent random network. The small-world measure (<math>\omega</math>) is defined as<ref name=":0">{{cite journal | vauthors = Telesford QK, Joyce KE, Hayasaka S, Burdette JH, Laurienti PJ | title = The ubiquity of small-world networks | journal = Brain Connectivity | volume = 1 | issue = 5 | pages = 367–75 | year = 2011 | pmid = 22432451 | pmc = 3604768 | doi = 10.1089/brain.2011.0038 | arxiv = 1109.5454 | bibcode = 2011arXiv1109.5454T }}</ref>

:<math>\omega = \frac{L_r} L - \frac C {C_\ell}</math>

Where the characteristic path length ''L'' and clustering coefficient ''C'' are calculated from the network you are testing, ''C''<sub>''ℓ''</sub> is the clustering coefficient for an equivalent lattice network and ''L''<sub>''r''</sub> is the characteristic path length for an equivalent random network.

Still another method for quantifying small-worldness normalizes both the network's clustering and path length relative to these characteristics in equivalent lattice and random networks. The Small World Index (SWI) is defined as<ref name=":1" />

: <math> \text{SWI} = \frac{L-L_\ell}{L_r-L_\ell}\times\frac{C-C_r}{C_\ell-C_r}</math>

Both ''ω''&prime; and SWI range between 0 and 1, and have been shown to capture aspects of small-worldness. However, they adopt slightly different conceptions of ideal small-worldness. For a given set of constraints (e.g. size, density, degree distribution), there exists a network for which ''ω''&prime; = 1, and thus ''ω'' aims to capture the extent to which a network with given constraints as small worldly as possible. In contrast, there may not exist a network for which SWI&nbsp;=&nbsp;1, thus SWI aims to capture the extent to which a network with given constraints approaches the theoretical small world ideal of a network where ''C'' ≈ ''C''<sub>''ℓ''</sub> and ''L'' ≈ ''L''<sub>''r''</sub>.<ref name=":1" />