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

Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: ** Mark D. Humphries , Kevin Gurney **

Fuente: http://plos.srce.hr/