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

Humphries MD, Gurney K. · 2008

Read Network 'small-world-ness': a quantitative method for determining canonical network equivalence. by Humphries MD, Gurney K. (2008) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc2323569.txt.

Introduction

Humphries and Gurney tackled a measurement problem in network science in 2008. Many networks, from brain wiring to social ties, are called small-world. That means nodes cluster tightly, yet any two nodes stay a few steps apart. Until then the label was a yes-or-no call, with no graded score.

They defined a score, S, that balances strong local clustering against short path length. A network counts as small-world when S is above 1, and that claim can be tested with statistics. Across a large set of real networks, S rose in a straight-line pattern with network size. They also showed how to assign one matching standard model, the Watts-Strogatz model, to any real network. That put model comparisons on firmer ground.

Catalog record

CREATORHumphries MD, Gurney K.
YEAR2008
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC2323569

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence By Mark D Humphries, Kevin Gurney, Olaf Sporns Published in: PLoS ONE DOI: 10.1371/journal.pone.0002051 ABSTRACT 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. INTRODUCTION Networks are widely used to both represent real-world systems for topological study [1] and as a substrate for modeling their dynamics [2]. Many real technological, biological, social, and information networks fall into the broad class of ‘small-world’ networks [3], a middle ground between regular and random networks: they have high local clustering of elements, like regular networks, but also short path lengths between elements, like random networks. Membership of the ‘small-world’ network class also implies that the corresponding systems have dynamic properties different from those of equivalent random or regular networks [3]–[7]. One popular method for studying small-world networks is to use an equivalent network model to generate other similar instances of the class of systems under study. Such generating models may also possess analytic properties that, we assume, may be extrapolated to the target system. One canonical model used as a candidate for network equivalence is the original Watts-Strogatz (WS) model, which has been used as a substrate for studying dynamics in the diverse fields of ecology [8], economics [9], [10], epidemiology [11], [12], and neuroscience [13]. However, the existing ‘small-world’ definition is a categorical one, and breaks the continuum of network topologies into the three classes of regular, random, and small-world networks, with the latter being the broadest. It is unclear to what extent the real-world systems in the small-world class have common network properties and to what specific point in the “middle-ground” (between random and regular) a network generating model must be tuned to genuinely capture the topology of such systems. Here we explore a continuous, quantitative, measure of ‘small-world-ness’, with the aim of overcoming these inadequacies in the current theory of small-world networks. Network formalism When describing a real-world system as a network, each element of the system is represented by a vertex or node, and relationships or interactions between elements are represented by edges between nodes. Two nodes are said to be neighbors if they are connected by an edge, and the degree ki of node i is the number of neighbors it has. The minimum path length between two nodes is the minimum number of edges that must be traversed to get from one node to the other. The mean value of the minimum path length over all node pairs will be denoted by L. A key concept in defining small-worlds networks is that of ‘clustering’ which measures the extent to which the neighbors of a node are also interconnected. Watts and Strogatz [3] defined the clustering coefficient of node i by [formula: (1)] where Ei is the number of edges between the neighbors of i. The clustering coefficient of the network C ws is then the mean of over all nodes. An alternative definition of network clustering in common use [14], based on transitivity, is expressed by [formula: (2)] where a ‘triangle’ is a set of three nodes in which each contacts the other two. Both capture intuitive notions of clustering but, though often in good agreement, values for C ws and C Δ can differ by an order of magnitude for some networks. We consider mainly C Δ here, but report where using C ws leads to different results. A network G with n nodes and m edges is a small-world network [3] if it has a similar path length but greater clustering of nodes than an equivalent Erdös-Rényi (E–R) random graph [15] with the same m and n (an E–R graph is constructed by uniquely assigning each edge to a node pair with uniform probability). More formally, let Lg be the mean shortest path length of G and its clustering coefficient using (2). Let Lrand and be the corresponding quantities for the corresponding E–R random graph. These ideas may be used to supply a semi-quantitative categorical definition of a small world network [3] Definition 1 The network G is said to be a small-world network if Lg≥Lrand and . Here a similar definition applies if we use (1) to define clustering coefficients. New measures of small-world-ness Put [formula: (3)] and [formula: (4)] We then define a quantitative metric of ‘small-world-ness’ S Δ according to [formula: (5)] In a similar way, putting [formula: (6)] we define S ws [formula: (7)] The categorical definition of small-world network above implies λg≥1 and , which, in turn, gives S Δ>1. We can, therefore, now make a quantitative categorical definition of a ‘small-world’ network Definition 2 A network is said to be a small-world network if S Δ>1 A similar definition may also be given with respect to S ws. However, notwithstanding the new categorical definition, we wish to emphasize here the utility of using a continuously graded notion of small-world-ness. We go on, therefore, to analyze the properties of the new metrics, and apply them to real-world data for the first time (in [16] we originally proposed this metric as a tool for comparing theoretical neuroanatomy models; its subsequent adoption by others [17], [18], [19] motivated us to consider its theoretical and empirical applications as a universal metric). RESULTS New metrics behave as required with the Watts-Strogatz model We first checked that the metric S Δ behaves as required on the canonical Watts-Strogatz (WS) model of small-world generation [3]. The WS model begins with a ring of n nodes, each node connected

Read the complete text