Network 'small-world-ness': A quantitative method for determining canonical network equivalence

Background: Many technological, biological, social and information networks fall into the broad class of 'small-world' networks: they how 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 awequivalent Canonical network model - the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS models 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 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 5 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-Strongatz (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. Conclusion/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. © 2008 Humphries, Gurney.