Editing Small-world network

{{Short description|Graph where most nodes are reachable in a small number of steps}}

{{Multiple image
 | width = 130
 | header = Small-world network example<br>''Hubs'' are bigger than other nodes
 | image1 = Small-world-network-example.png
 | alt1 = 
 | caption1 = Average [[Degree (graph theory)|degree]]= 3.833<br />Average shortest path length = 1.803.<br />[[Clustering coefficient]] = 0.522 
 | image2 = Random graph gephi.png
 | alt2 = 
 | caption2 = Random graph<br/>Average [[Degree (graph theory)|degree]] = 2.833 <br/>Average shortest path length = 2.109.<br/>[[Clustering coefficient]] = 0.167
}}

{{Network Science}}

A '''small-world network''' is a [[Graph (discrete mathematics)|graph]] characterized by a high [[clustering coefficient]] and low [[Distance (graph theory)|distances]]. In an example of the social network, high clustering implies the high probability that two friends of one person are friends themselves. The low distances, on the other hand, mean that there is a short chain of social connections between any two people (this effect is known as [[six degrees of separation]]).<ref>{{Cite book |last=Downey |first=Allen B. |url=https://greenteapress.com/complexity2/thinkcomplexity2.pdf |title=Think Complexity |publisher=[[Green Tea Press]] |year=2016 |location=Needham, Massachusetts |page=27 |chapter=3}}</ref> Specifically, a small-world network is defined to be a network where the [[Expected value|typical]] distance ''L'' between two randomly chosen nodes (the number of steps required) grows proportionally to the [[logarithm]] of the number of nodes ''N'' in the network, that is:<ref>{{cite journal | vauthors = Watts DJ, Strogatz SH | title = Collective dynamics of 'small-world' networks | language = En | journal = Nature | volume = 393 | issue = 6684 | pages = 440–2 | date = June 1998 | pmid = 9623998 | doi = 10.1038/30918 | bibcode = 1998Natur.393..440W | s2cid = 4429113 }}</ref>

:<math>L \propto \log N</math>

while the [[clustering coefficient|global clustering coefficient]] is not small.  

In the context of a social network, this results in the [[Small-world experiment|small world phenomenon]] of strangers being linked by a short chain of [[acquaintance]]s.  Many empirical graphs show the small-world effect, including [[Social network analysis|social networks]], wikis such as Wikipedia, [[gene regulatory network|gene networks]], and even the underlying architecture of the [[Internet]].  It is the inspiration for many [[Network on a chip|network-on-chip]] architectures in contemporary [[computer hardware]].<ref name=":02">{{cite book |title=Network-on-chip: the Next Generation of System-on-Chip Integration |last1=Kundu |first1=Santanu |last2=Chattopadhyay |first2=Santanu | name-list-style = vanc |publisher=CRC Press|year=2014|isbn=9781466565272|edition=1st|location=Boca Raton, FL|oclc=895661009}}</ref>

A certain category of small-world networks were identified as a class of [[random graph]]s by [[Duncan J. Watts|Duncan Watts]] and [[Steven Strogatz]] in 1998.<ref>{{cite journal | vauthors = Watts DJ, Strogatz SH | title = Collective dynamics of 'small-world' networks | journal = Nature | volume = 393 | issue = 6684 | pages = 440–2 | date = June 1998 | pmid = 9623998 | doi = 10.1038/30918 | author2-link = Steven Strogatz | bibcode = 1998Natur.393..440W | s2cid = 4429113 }}</ref> They noted that graphs could be classified according to two independent structural features, namely the [[clustering coefficient]], and average node-to-node [[distance (graph theory)|distance]] (also known as [[average path length|average shortest path length]]).  Purely random graphs, built according to the [[Erdős–Rényi model|Erdős–Rényi (ER) model]], exhibit a small average shortest path length (varying typically as the logarithm of the number of nodes) along with a small clustering coefficient. Watts and Strogatz measured that in fact many real-world networks have a small average shortest path length, but also a clustering coefficient significantly higher than expected by random chance. Watts and Strogatz then proposed a novel graph model, currently named the [[Watts and Strogatz model]], with (i) a small average shortest path length, and (ii) a large clustering coefficient. The crossover in the Watts–Strogatz model between a "large world" (such as a lattice) and a small world was first described by Barthelemy and Amaral in 1999.<ref>{{cite journal | vauthors = Barthelemy M, Amaral LA | year = 1999 | title = Small-world networks: Evidence for a crossover picture | journal =  Physical Review Letters| volume = 82 | issue = 15| pages = 3180–3183 | doi=10.1103/PhysRevLett.82.3180 | bibcode=1999PhRvL..82.3180B|arxiv = cond-mat/9903108 | s2cid = 119398712 }}</ref> This work was followed by many studies, including exact results (Barrat and Weigt, 1999; Dorogovtsev and [[José Fernando Ferreira Mendes|Mendes]]; Barmpoutis and Murray, 2010).

==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" />

==Examples of small-world networks==
Small-world properties are found in many real-world phenomena, including websites with navigation menus, food webs, electric power grids, metabolite processing networks, [[biological neural network|networks of brain neurons]], 
voter networks, telephone call graphs, and airport networks.<ref>{{cite journal | vauthors = Yang YC |date=1972 |title=Terminal Road Bridges for San Francisco International Airport Airport |journal= ACI Journal Proceedings|volume=69 |issue=10 |doi=10.14359/7189 }}</ref>  Cultural networks<ref>{{cite journal | vauthors = Senekal BA | title = 'n Kwantifisering van kleinwêreldsheid in Afrikaanse kultuurnetwerke in vergelyking met ander komplekse netwerke: natuurwetenskappe. | trans-title = A quantification of small worlds in African cultural networks compared to other complex networks: natural sciences. | language = af | publisher = Litnet Akademies | journal ='n Joernaal vir die Geesteswetenskappe, Natuurwetenskappe, Regte en Godsdienswetenskappe | date = December 2015 | volume = 12 | issue = 3 | pages = 665–88 | url = http://www.litnet.co.za/n-kwantifisering-van-kleinwereldsheid-in-afrikaanse-kultuurnetwerke-in-vergelyking-met-ander-komplekse-netwerke/ }}</ref> and word [[co-occurrence network]]s<ref>{{cite journal | vauthors = Senekal B, Kotzé E | title = Die statistiese eienskappe van geskrewe Afrikaans as'n komplekse netwerk. | trans-title = The statistical properties of written Afrikaans as a complex network | language = af | publisher = Litnet Akademies | journal = 'n Joernaal vir die Geesteswetenskappe, Natuurwetenskappe, Regte en Godsdienswetenskappe | date = 2017 | volume = 14 | issue = 1 | pages = 27–59 | url = http://www.litnet.co.za/die-statistiese-eienskappe-van-geskrewe-afrikaans-n-komplekse-netwerk/ }}</ref> have also been shown to be small-world networks.

Networks of [[protein–protein interaction|connected proteins]] have small world properties such as power-law obeying degree distributions.<ref>{{cite journal | vauthors = Bork P, Jensen LJ, von Mering C, Ramani AK, Lee I, Marcotte EM | title = Protein interaction networks from yeast to human | journal = Current Opinion in Structural Biology | volume = 14 | issue = 3 | pages = 292–9 | date = June 2004 | pmid = 15193308 | doi = 10.1016/j.sbi.2004.05.003 | url = http://marcottelab.org/paper-pdfs/cosb-review.pdf }}</ref> Similarly [[transcriptional regulation|transcriptional network]]s, in which the nodes are [[gene]]s, and they are linked if one gene has an up or down-regulatory genetic influence on the other, have small world network properties.<ref>{{cite journal | vauthors = van Noort V, Snel B, Huynen MA | title = The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model | journal = EMBO Reports | volume = 5 | issue = 3 | pages = 280–4 | date = March 2004 | pmid = 14968131 | pmc = 1299002 | doi = 10.1038/sj.embor.7400090 }}</ref>

==Examples of non-small-world networks==
In another example, the famous theory of "[[six degrees of separation]]" between people tacitly presumes that the [[domain of discourse]] is the set of people alive at any one time. The number of degrees of separation between [[Albert Einstein]] and [[Alexander the Great]] is almost certainly greater than 30<ref>Einstein and Alexander the Great lived 2202 years apart. Assuming an age difference of 70 years between any two connected people in the chain that connects the two, this would necessitate at least 32 connections between Einstein and Alexander the Great.</ref> and this network does not have small-world properties. A similarly constrained network would be the "went to school with" network: if two people went to the same college ten years apart from one another, it is unlikely that they have acquaintances in common amongst the student body.

Similarly, the number of relay stations through which a message must pass was not always small. In the days when the post was carried by hand or on horseback, the number of times a letter changed hands between its source and destination would have been much greater than it is today. The number of times a message changed hands in the days of the visual telegraph (circa 1800–1850) was determined by the requirement that two stations be connected by line-of-sight.

Tacit assumptions, if not examined, can cause a bias in the literature on graphs in favor of finding small-world networks (an example of the [[File drawer problem#File drawer effect|file drawer effect resulting from the publication bias]]).

==Network robustness==
It is hypothesized by some researchers, such as [[Albert-László Barabási]], that the prevalence of small world networks in biological systems may reflect an evolutionary advantage of such an architecture. One possibility is that small-world networks are more robust to perturbations than other network architectures. If this were the case, it would provide an advantage to biological systems that are subject to damage by [[mutation]] or [[virus|viral infection]].

In a small world network with a degree distribution following a [[power-law]], deletion of a random node rarely causes a dramatic increase in [[mean-shortest path]] length (or a dramatic decrease in the [[clustering coefficient]]). This follows from the fact that most shortest paths between nodes flow through [[Hub (network science)|hubs]], and if a peripheral node is deleted it is unlikely to interfere with passage between other peripheral nodes. As the fraction of peripheral nodes in a small world network is much higher than the fraction of [[spoke–hub distribution paradigm|hubs]], the probability of deleting an important node is very low. For example, if the small airport in [[Sun Valley, Idaho]] was shut down, it would not increase the average number of flights that other passengers traveling in the United States would have to take to arrive at their respective destinations. However, if random deletion of a node hits a hub by chance, the average path length can increase dramatically. This can be observed annually when northern hub airports, such as Chicago's [[O'Hare International Airport|O'Hare airport]], are shut down because of snow; many people have to take additional flights.

By contrast, in a random network, in which all nodes have roughly the same number of connections, deleting a random node is likely to increase the mean-shortest path length slightly but significantly for almost any node deleted. In this sense, random networks are vulnerable to random perturbations, whereas small-world networks are robust. However, small-world networks are vulnerable to targeted attack of hubs, whereas random networks cannot be targeted for catastrophic failure.

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

== Applications ==

=== Applications to sociology ===
The advantages to small world networking for [[social movement| social movement groups]] are their resistance to change due to the filtering apparatus of using highly connected nodes, and its better effectiveness in relaying information while keeping the number of links required to connect a network to a minimum.<ref name = "shirky">{{cite book | vauthors = Shirky C | author-link = Clay Shirky | title = Here Comes Everybody: the power of organizing without organizations | publisher = Penguin Press | date = 2008 | isbn = 978-1-59420-153-0 | oclc = 168716646 | url-access = registration | url = https://archive.org/details/herecomeseverybo0000shir }}</ref>

The small world network model is directly applicable to [[affinity group]] theory represented in sociological arguments by [[William Finnegan]]. Affinity groups are social movement groups that are small and semi-independent pledged to a larger goal or function. Though largely unaffiliated at the node level, a few members of high connectivity function as connectivity nodes, linking the different groups through networking. This small world model has proven an extremely effective protest organization tactic against police action.<ref name ="finnegan">Finnegan, William "Affinity Groups and the Movement Against Corporate Globalization"</ref> [[Clay Shirky]] argues that the larger the social network created through small world networking, the more valuable the nodes of high connectivity within the network.<ref name= "shirky"/> The same can be said for the affinity group model, where the few people within each group connected to outside groups allowed for a large amount of mobilization  and adaptation. A practical example of this is small world networking through affinity groups that William Finnegan outlines in reference to the [[1999 Seattle Protests|1999 Seattle WTO protests]].

=== Applications to earth sciences ===

Many networks studied in geology and geophysics have been shown to have characteristics of small-world networks.  Networks defined in fracture systems and porous substances have demonstrated these characteristics.<ref>{{cite journal | vauthors = Yang XS | s2cid = 118655139 | title = Small-world networks in geophysics. | journal = Geophysical Research Letters | date = July 2001 | volume = 28 | issue = 13 | pages = 2549–52 | doi = 10.1029/2000GL011898 | bibcode = 2001GeoRL..28.2549Y | arxiv = 1003.4886 }}(2001)</ref>  The seismic network in the Southern California region may be a small-world network.<ref>{{cite journal | vauthors = Jiménez A, Tiampo KF, Posadas AM | title = Small world in a seismic network: the California case. | journal = Nonlinear Processes in Geophysics | date = May 2008 | volume = 15 | issue = 3 | pages = 389–95 | url = https://core.ac.uk/download/pdf/26891534.pdf | doi = 10.5194/npg-15-389-2008 | bibcode = 2008NPGeo..15..389J | doi-access = free }}</ref>  The examples above occur on very different spatial scales, demonstrating the [[scale invariance]] of the phenomenon in the earth sciences.

=== Applications to computing ===

Small-world networks have been used to estimate the usability of information stored in large databases.  The measure is termed the Small World Data Transformation Measure.<ref>{{Cite web | first1 = Robert | last1 = Hillard | first2 = Sean | last2 = McClowry | first3 = Brenda | last3 = Somich | name-list-style = vanc | url = http://mike2.openmethodology.org/wiki/Small_Worlds_Data_Transformation_Measure | title = Small Worlds Data Transformation Measure | work = MIKE2.0, the open source methodology for Information Development | access-date = 2012-01-05 | archive-date = 2015-09-12 | archive-url = https://web.archive.org/web/20150912023744/http://mike2.openmethodology.org/wiki/Small_Worlds_Data_Transformation_Measure | url-status = live }}</ref><ref>{{cite book |last=Hillard |first=Robert | name-list-style = vanc | title = Information-Driven Business |year=2010|publisher=Wiley|isbn=978-0-470-62577-4}}</ref> The greater the database links align to a small-world network the more likely a user is going to be able to extract information in the future.  This usability typically comes at the cost of the amount of information that can be stored in the same repository.

The [[Freenet]] peer-to-peer network has been shown to form a small-world network in simulation,<ref>{{cite thesis | last = Sandberg | first = Oskar | name-list-style = vanc | degree = Ph.D. | title = Searching in a Small World | url = https://freenetproject.org/papers/lic.pdf | publisher = Chalmers University of Technology and Göteborg University | location = Göteborg, Sweden | date = 2005 | access-date = 2013-12-12 | archive-date = 2012-03-16 | archive-url = https://web.archive.org/web/20120316102141/https://freenetproject.org/papers/lic.pdf | url-status = live }}</ref> allowing information to be stored and retrieved in a manner that scales efficiency as the network grows.

[[Nearest neighbor search|Nearest Neighbor Search]] solutions like [[Hierarchical Navigable Small World graphs|HNSW]] use small-world networks to efficiently find the information in large item corpuses.<ref>{{Cite web |title=Hierarchical Navigable Small Worlds (HNSW) {{!}} Pinecone |url=https://www.pinecone.io/learn/series/faiss/hnsw/ |access-date=2024-03-05 |website=www.pinecone.io |language=en}}</ref><ref>{{Cite web |title=Understanding Hierarchical Navigable Small Worlds (HNSW) |url=https://www.datastax.com/guides/hierarchical-navigable-small-worlds |access-date=2024-03-05 |website=DataStax |language=en}}</ref>

=== Small-world neural networks in the brain ===
Both anatomical connections in the [[brain]]<ref>{{cite journal | vauthors = Sporns O, Chialvo DR, Kaiser M, Hilgetag CC | s2cid = 2855338 | title = Organization, development and function of complex brain networks | journal = Trends in Cognitive Sciences | volume = 8 | issue = 9 | pages = 418–25 | date = September 2004 | pmid = 15350243 | doi = 10.1016/j.tics.2004.07.008 }}</ref>  and the synchronization networks of cortical neurons<ref>{{cite journal | vauthors = Yu S, Huang D, Singer W, Nikolic D | title = A small world of neuronal synchrony | journal = Cerebral Cortex | volume = 18 | issue = 12 | pages = 2891–901 | date = December 2008 | pmid = 18400792 | pmc = 2583154 | doi = 10.1093/cercor/bhn047 }}</ref> exhibit small-world topology.

Structural and functional connectivity in the brain has also been found to reflect the small-world topology of short path length and high clustering.<ref>{{Cite journal|last1=Bassett|first1=Danielle S.|last2=Bullmore|first2=Edward T.|date=2017-10-23|title=Small-World Brain Networks Revisited|url= |journal=The Neuroscientist|language=en|volume=23|issue=5|pages=499–516|doi=10.1177/1073858416667720|issn=1073-8584|pmc=5603984|pmid=27655008}}</ref> The network structure has been found in the mammalian cortex across species as well as in large scale imaging studies in humans.<ref>{{Cite journal|last1=Bettencourt|first1=Luís M. A.|last2=Stephens|first2=Greg J.|last3=Ham|first3=Michael I.|last4=Gross|first4=Guenter W.|date=2007-02-23|title=Functional structure of cortical neuronal networks grown in vitro|url=https://link.aps.org/doi/10.1103/PhysRevE.75.021915|journal=Physical Review E|language=en|volume=75|issue=2|pages=021915|doi=10.1103/PhysRevE.75.021915|pmid=17358375|issn=1539-3755|arxiv=q-bio/0703018|bibcode=2007PhRvE..75b1915B|s2cid=14757568}}</ref> Advances in [[connectomics]] and [[network neuroscience]], have found the small-worldness of neural networks to be associated with efficient communication.<ref name="Economy brain organization">{{Cite journal
|last1=Bullmore|first1=Ed
|last2=Sporns|first2=Olaf
|date=2012-04-13
|title=The economy of brain network organization
|url=https://pubmed.ncbi.nlm.nih.gov/22498897
|journal=Nature Reviews. Neuroscience|volume=13|issue=5|pages=336–349
|doi=10.1038/nrn3214
|issn=1471-0048
|pmid=22498897
|s2cid=16174225}}</ref>

In neural networks, short pathlength between nodes and high clustering at network hubs supports efficient communication between brain regions at the lowest energetic cost.<ref name="Economy brain organization" /> The brain is constantly processing and adapting to new information and small-world network model supports the intense communication demands of neural networks.<ref>{{Cite journal|last1=Bassett|first1=D. S.|last2=Bullmore|first2=E.|last3=Verchinski|first3=B. A.|last4=Mattay|first4=V. S.|last5=Weinberger|first5=D. R.|last6=Meyer-Lindenberg|first6=A.|date=2008-09-10|title=Hierarchical Organization of Human Cortical Networks in Health and Schizophrenia|url= |journal=Journal of Neuroscience|language=en|volume=28|issue=37|pages=9239–9248|doi=10.1523/JNEUROSCI.1929-08.2008|issn=0270-6474|pmc=2878961|pmid=18784304}}</ref> High clustering of nodes forms local networks which are often functionally related. Short path length between these hubs supports efficient global communication.<ref>{{Cite journal|last1=Voss|first1=Michelle W.|last2=Wong|first2=Chelsea N.|last3=Baniqued|first3=Pauline L.|last4=Burdette|first4=Jonathan H.|last5=Erickson|first5=Kirk I.|last6=Prakash|first6=Ruchika Shaurya|last7=McAuley|first7=Edward|last8=Laurienti|first8=Paul J.|last9=Kramer|first9=Arthur F.|date=2013-11-06|editor-last=Sathian|editor-first=Krish|title=Aging Brain from a Network Science Perspective: Something to Be Positive About?|journal=PLOS ONE|language=en|volume=8|issue=11|pages=e78345|doi=10.1371/journal.pone.0078345|issn=1932-6203|pmc=3819386|pmid=24223147|bibcode=2013PLoSO...878345V|doi-access=free}}</ref> This balance enables the efficiency of the global network while simultaneously equipping the brain to handle disruptions and maintain homeostasis, due to local subsystems being isolated from the global network.<ref name="Symptoms brain vulnerability">{{Cite journal
|last1=Levit-Binnun|first1=Nava
|last2=Davidovitch|first2=Michael
|last3=Golland|first3=Yulia
|date=2013-09-24
|title=Sensory and motor secondary symptoms as indicators of brain vulnerability
|journal=Journal of Neurodevelopmental Disorders
|volume=5
|issue=1
|pages=26
|doi=10.1186/1866-1955-5-26
|issn=1866-1947
|pmc=3849186
|pmid=24063566
|doi-access=free
}}</ref> Loss of small-world network structure has been found to indicate changes in cognition and increased risk of psychological disorders.<ref name=":1" />

In addition to characterizing whole-brain functional and structural connectivity, specific neural systems, such as the visual system, exhibit small-world network properties.<ref name="D. Humphries, K 1639" />

A small-world network of neurons can exhibit [[short-term memory]]. A computer model developed by [[Sara Solla]]<ref>{{cite web | last = Cohen | first = Philip | name-list-style = vanc | url = https://www.newscientist.com/article.ns?id=dn5012 | title = Small world networks key to memory | work = New Scientist | date = 26 May 2004 }}</ref><ref>{{cite journal | first = Sara | last = Solla | author-link = Sara Solla | s2cid = 14272272 | name-list-style = vanc | url = http://online.itp.ucsb.edu/online/brain04/solla/ | journal = Physical Review Letters | publisher = UC Santa Barbara, Kavli Institute for Theoretical Physics | title = Self-Sustained Activity in a Small-World Network of Excitable Neurons | year = 2004 | volume = 92 | issue = 19 | page = 198101 | doi = 10.1103/PhysRevLett.92.198101 | pmid = 15169447 | arxiv = nlin/0309067 | bibcode = 2004PhRvL..92s8101R | access-date = 2006-03-06 | archive-date = 2016-09-14 | archive-url = https://web.archive.org/web/20160914210640/http://online.itp.ucsb.edu/online/brain04/solla/ | url-status = live }}</ref> had two stable states, a property (called [[bistability]]) thought to be important in [[memory]] storage.  An activating pulse generated self-sustaining loops of communication activity among the neurons. A second pulse ended this activity.  The pulses switched the system between stable states: flow (recording a "memory"), and stasis (holding it). Small world neuronal networks have also been used as models to understand [[seizures]].<ref>{{cite journal | vauthors = Ponten SC, Bartolomei F, Stam CJ | title = Small-world networks and epilepsy: graph theoretical analysis of intracerebrally recorded mesial temporal lobe seizures | journal = Clinical Neurophysiology | volume = 118 | issue = 4 | pages = 918–27 | date = April 2007 | pmid = 17314065 | doi = 10.1016/j.clinph.2006.12.002 | s2cid = 35927833 }}</ref>

== See also ==
*{{annotated link|Barabási–Albert model}}
*{{annotated link|Climate as complex networks}}
*{{annotated link|Dual-phase evolution}}
*{{annotated link|Dunbar's number}}
*{{annotated link|Erdős number}}
*{{annotated link|Erdős–Rényi model|Erdős–Rényi (ER) model}}
*[[Local World Evolving Network Models]]
*{{annotated link|Percolation theory}}
*{{annotated link|Network science}} - mathematical theory  of networks
*{{annotated link|Scale-free network}}
*{{annotated link|Six Degrees of Kevin Bacon|Six degrees of Kevin Bacon}}
*{{annotated link|Small-world experiment}}
*{{annotated link|Social network}}
*{{annotated link|Watts–Strogatz model}}
*{{annotated link|Network on a chip}} – [[System on a chip|systems on chip]] modeled on small-world networks
*[[Zachary's karate club]]

== References ==
{{reflist}}

== Further reading ==

===Books===
{{refbegin|30em}}
* {{cite book | last = Buchanan | first =  Mark | name-list-style = vanc | title=Nexus: Small Worlds and the Groundbreaking Theory of Networks | publisher=Norton, W. W. & Company, Inc | year=2003 | isbn=978-0-393-32442-6 | url-access=registration | url=https://archive.org/details/nexus00mark }}
* {{cite book | vauthors = Dorogovtsev SN, Mendes JF | title=Evolution of Networks: from biological networks to the Internet and WWW | publisher=Oxford University Press | year=2003 | isbn=978-0-19-851590-6}}
* {{cite book | vauthors = Watts DJ | year=1999 | title=Small Worlds: The Dynamics of Networks Between Order and Randomness | publisher=Princeton University Press | isbn=978-0-691-00541-6}}
* {{cite book | vauthors = Fowler JH | author-link = James H. Fowler | date = 2005 | chapter = Turnout in a Small World | veditors = Zuckerman A | title = Social Logic of Politics | publisher = Temple University Press | pages = 269–287 }}
{{refend}}

===Journal articles===
{{refbegin|30em}}
* {{cite journal | vauthors = Albert R, Barabási AL | title= Statistical mechanics of complex networks | journal=Rev. Mod. Phys. | year=2002 | volume=74 |issue=1 | pages=47–97 | doi= 10.1103/RevModPhys.74.47 | bibcode=2002RvMP...74...47A|arxiv = cond-mat/0106096 | s2cid= 60545 }}
* {{cite journal | vauthors = Barabasi AL, Albert R | title = Emergence of scaling in random networks | journal = Science | volume = 286 | issue = 5439 | pages = 509–12 | date = October 1999 | pmid = 10521342 | doi = 10.1126/science.286.5439.509 | arxiv = cond-mat/9910332 | bibcode = 1999Sci...286..509B | s2cid = 524106 }}
* {{cite journal | vauthors = Barthelemy M, Amaral LA | title= Small-world networks: Evidence for a crossover picture| journal=Phys. Rev. Lett. | year=1999 | volume=82 | pages=3180–3183 | doi= 10.1103/PhysRevLett.82.3180 | issue=15 | bibcode=1999PhRvL..82.3180B|arxiv = cond-mat/9903108 | s2cid= 119398712}}
* {{cite journal | vauthors = Dorogovtsev SN, Mendes JF | s2cid= 11334862| title= Exactly solvable analogy of small-world networks| journal=Europhys. Lett. | year=2000 | volume=50 |issue=1 | pages=1–7 | doi= 10.1209/epl/i2000-00227-1|arxiv = cond-mat/9907445 |bibcode = 2000EL.....50....1D }}
* {{cite journal | vauthors= Milgram S | title=The Small World Problem | journal=Psychology Today | year=1967 | volume=1 | issue=1 |pages=60–67| author-link=Stanley Milgram }}
* {{cite journal | vauthors = Newman M | s2cid=65837 | title=The Structure and Function of Complex Networks | journal=SIAM Review | year=2003 | volume=45 | pages=167–256 | doi=10.1137/S003614450342480 | issue=2|arxiv = cond-mat/0303516 |bibcode = 2003SIAMR..45..167N }} [http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf pdf] {{Webarchive|url=https://web.archive.org/web/20210314182247/http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf |date=2021-03-14 }}
* {{cite journal | vauthors = Ravid D, Rafaeli S |s2cid=6388295 |author2-link=Sheizaf Rafaeli | title=Asynchronous discussion groups as Small World and Scale Free Networks | journal=First Monday | year=2004 | volume=9 | issue=9 | doi=10.5210/fm.v9i9.1170 |doi-access=free }} [http://firstmonday.org/issues/issue9_9/ravid/index.html]
{{refend}}

== External links ==
* [http://demonstrations.wolfram.com/DynamicProximityNetworks/ Dynamic Proximity Networks] by Seth J. Chandler, [[The Wolfram Demonstrations Project]].
* [http://www.scholarpedia.org/article/Small-world_network Small-World Networks] entry on Scholarpedia (by Mason A. Porter)

{{Social networking}}
{{Online social networking}}

[[Category:Networks]]
[[Category:Graph families]]

[[fr:Petit monde]]