Editing Small-world network (section)

{{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).