Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence

@article{citeulike:2896366, abstract = {Background: Many technological, biological, social, and information networks fall into the broad class of ‘small-world’ networks: they have tightly interconnected clusters of nodes, and a shortest mean path length that is similar to a matched random graph (same number of nodes and edges). This semi-quantitative definition leads to a categorical distinction (‘small/not-small’) rather than a quantitative, continuous grading of networks, and can lead to uncertainty about a network's small-world status. Moreover, systems described by small-world networks are often studied using an equivalent canonical network model – the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS model is imprecise and there is a pressing need to discover ways in which this equivalence may be quantified. Methodology/Principal Findings: We defined a precise measure of ‘small-world-ness’ S based on the trade off between high local clustering and short path length. A network is now deemed a ‘small-world’ if S>1 - an assertion which may be tested statistically. We then examined the behavior of S on a large data-set of real-world systems. We found that all these systems were linked by a linear relationship between their S values and the network size n. Moreover, we show a method for assigning a unique Watts-Strogatz (WS) model to any real-world network, and show analytically that the WS models associated with our sample of networks also show linearity between S and n. Linearity between S and n is not, however, inevitable, and neither is S maximal for an arbitrary network of given size. Linearity may, however, be explained by a common limiting growth process. Conclusions/Significance: We have shown how the notion of a small-world network may be quantified. Several key properties of the metric are described and the use of WS canonical models is placed on a more secure footing.}, author = {Humphries, Mark D. and Gurney, Kevin }, citeulike-article-id = {2896366}, doi = {10.1371/journal.pone.0002051}, journal = {PLoS ONE}, keywords = {2008, network, small-world}, month = {April}, number = {4}, pages = {e0002051+}, posted-at = {2008-07-18 12:30:45}, priority = {0}, publisher = {Public Library of Science}, title = {Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence}, url = {http://dx.doi.org/10.1371/journal.pone.0002051}, volume = {3}, year = {2008} }

TY - JOUR ID - citeulike:2896366 L3 - citeulike-article-id:2896366 TI - Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence JF - PLoS ONE VL - 3 IS - 4 SP - e0002051 PB - Public Library of Science N2 - Background: Many technological, biological, social, and information networks fall into the broad class of ‘small-world’ networks: they have tightly interconnected clusters of nodes, and a shortest mean path length that is similar to a matched random graph (same number of nodes and edges). This semi-quantitative definition leads to a categorical distinction (‘small/not-small’) rather than a quantitative, continuous grading of networks, and can lead to uncertainty about a network's small-world status. Moreover, systems described by small-world networks are often studied using an equivalent canonical network model – the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS model is imprecise and there is a pressing need to discover ways in which this equivalence may be quantified. Methodology/Principal Findings: We defined a precise measure of ‘small-world-ness’ S based on the trade off between high local clustering and short path length. A network is now deemed a ‘small-world’ if S>1 - an assertion which may be tested statistically. We then examined the behavior of S on a large data-set of real-world systems. We found that all these systems were linked by a linear relationship between their S values and the network size n. Moreover, we show a method for assigning a unique Watts-Strogatz (WS) model to any real-world network, and show analytically that the WS models associated with our sample of networks also show linearity between S and n. Linearity between S and n is not, however, inevitable, and neither is S maximal for an arbitrary network of given size. Linearity may, however, be explained by a common limiting growth process. Conclusions/Significance: We have shown how the notion of a small-world network may be quantified. Several key properties of the metric are described and the use of WS canonical models is placed on a more secure footing. KW - 2008 KW - network KW - small-world AU - Humphries, Mark AU - Gurney, Kevin PY - 2008/04/30/ UR - http://dx.doi.org/10.1371/journal.pone.0002051 ER -