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

By Mark D. Humphries, Kevin N. Gurney. PLoS ONE, 2008

1,397 citations recorded by the source corpus.

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.

Subfields: Condensed Matter Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/33b9eeb55dfc486b602717a61e8a11336ca55c1f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Comparison of Characteristics between Region- and Voxel-Based Network Analyses in Resting-State fMRI Data (2009, neutral): “These two ratios are summarized in the small-world metric σ = γ/ λ, with σ > 1 indicating the small-world characteristic of a network (Humphries and Gurney 2008; Humphries, et al. 2006).”
Application of Graph Theory for Identifying Connectivity Patterns in Human Brain Networks: A Systematic Review (2019, background): “…displays an optimal balance between network segregation and integration, and is dedicated to graphs in which most nodes are not neighbors but can be reached by any other node with the minimum possible path length (Achard, 2006; Humphries et al., 2006; Humphries and Gurney, 2008; Figure 4C ).”
Structural Properties of the Caenorhabditis elegans Neuronal Network (2009, neutral): “Rényi random network as follows [50]:”
Functional neural network analysis in frontotemporal dementia and Alzheimer's disease using EEG and graph theory (2009, background): “When this ratio is larger than 1, a network is said to have Small-world properties [9].”
Complex network measures of brain connectivity: Uses and interpretations (2010, background): “Recently, a measure of small-worldness was proposed to capture this effect in a single statistic (Humphries and Gurney, 2008).”
How semantic memory structure and intelligence contribute to creative thought: a network science approach (2017, methodology): “An additional measure, (S), quantifies the “small-worldness” of a specific network (Humphries & Gurney, 2008) by computing the ratio between the CC and the ASPL, and it reflects the extent to which a network is “small-worlded” (a value greater than one indicates that the network is “small-worlded”).”
The Ubiquity of Small-World Networks (2011, methodology): “Because clustering in a random network is typically extremely low (Humphries and Gurney, 2008; Watts and Strogatz, 1998) the value of c can be unduly influenced by only small changes in Crand.”
Graph theoretical analysis of structural and functional connectivity MRI in normal and pathological brain networks (2010, background): “The ratio σ = γ /λ is often used and must be >1 to define the smallworldness of a network [24,25].”
Structure and flexibility: Investigating the relation between the structure of the mental lexicon, fluid intelligence, and creative achievement. (2016, methodology): “Finally, the S measure (Humphries & Gurney, 2008) was computed to quantitatively evaluate the small-world nature of the network.”
Networks of Value Added Trade (2017, neutral): “For a discussion of the small-world properties of a network, see Humphries and Gurney (2008) and Telesford et al.”
Investigating the structure of semantic networks in low and high creative persons (2014, methodology): “Finally, the S measure (Humphries and Gurney, 2008) was computed to quantitatively evaluate the small-world nature of each network.”
Optimal Hierarchical Modular Topologies for Producing Limited Sustained Activation of Neural Networks (2009, neutral): “The extent of a small-world organization can be characterized by the smallworld coeffi cient SW = (C/C rand )/(L/L rand ) (Humphries et al., 2006; Humphries and Gurney, 2008).”
On the use of correlation as a measure of network connectivity (2012, background): “1 also shows the ratio of these two ratios (black), which serves as a commonly used summary statistic of small-worldness (Humpheries and Gurney, 2008).”
State of the aRt personality research: A tutorial on network analysis of personality data in R (2015, neutral): “A network with a small-worldness value higher than three can be considered as having the small-world property, while a small-worldness between one and three is considered a borderline value (Humphries & Gurney, 2008).”