Small-world property, small-word networks, and small-worldness

While the SW construct has enjoyed vast popularity in the neuroscience community, a careful look at the literature shows that the various studies resorted to three different though related definitions of SW, which turn out to be nested into each other.

The SW property designates networks in which the shortest path L (i.e., the average number of steps needed to go from a node to any other node in the network) is much smaller than the network size N (L N) (Milgram, 1967). In a SW network, few connecting links drastically shorten the distance between closely knit groups of nodes, so that L is low and grows very slowly with N (L ~ ln(N)), while the clustering coefficient C (i.e., the percentage of node's neighbors that are, in turn, linked between them) remains high (Watts and Strogatz, 1998). Finally, the SW-ness parameter σ is a continuous, quantitative, measure defined as:

i.e., the ratio between C and L normalized by the L_rand and C_rand of a set of equivalent random networks (Humphries and Gurney, 2008). In the remainder, attention is mostly focused on σ, which encompasses the two preceding constructs.

Pitfalls along the way: From brain recording to data interpretation

• 1. Brain recording devices and standard analyses used to construct networks from neural data can distort the extent to which a network may appear SW.

The basic ingredients of a SW network are its clustering coefficient C and the average shortest-path L. Estimates of these properties crucially depend on the way nodes and links are defined. Different definitions modify C and L, ultimately affecting the estimated SW character of the network.

Various sources of possible distortion arising at the first step, that of brain recording, have been illustrated in a number of studies (Bialonski et al., 2010; Zalesky et al., 2010a, 2012; van Wijk et al., 2010; Fornito et al., 2013), including problems due to parcellation and edge definition, spatial embedding, and edge density. For example, in classical electrophysiological methods, nodes are identified with sensors. The lattice-like sensor organization can lead to overestimating the extent to which a network is SW, as different sensors may measure the activity of the same region, ultimately increasing C (Bialonski et al., 2010).

Even supposing that brain activity is recorded with an error-free device, projecting brain data onto a network structure comes with its own problems. When dealing with magnetic resonance imaging data, defining nodes is highly non-trivial and may be carried out in different ways, each introducing its own bias, e.g., network reconstruction based on voxel-voxel correlations over-represents connectivity between neighboring voxels, increasing C, whereas parcellations based on different atlases lead to differences in the SW-ness parameter (Yao et al., 2015).

Estimate distortions also arise from the possible ways of defining links. While there is no well-established criterion to choose a connectivity metric out of the many existing ones, different metrics lead to different connectivity patterns, which may be associated with different basic topological properties, affecting SW evaluation. Moreover, limitations in the reliability of link estimation (e.g., due to noise or common sources) may decrease L and increase C, by simply adding a few false positive connections, leading to the observation of SW even in regular or random networks (Bialonski et al., 2010). Furthermore, in its standard formulation, the SW requires networks to be connected, as d diverges in the presence of disconnected nodes. This issue can be dealt with either by adding links (but, this may introduce spurious ones); by taking into account the connected giant component, (but this alters the network size, complicating network comparisons, van Wijk et al., 2010); or by resorting to an equivalent efficiency measure avoiding divergence for disconnected nodes (Latora and Marchiori, 2001).

Furthermore, SW estimates are sensitive to thresholds adopted to prune non-significant links: for high threshold values, brain activity appears hierarchically organized into modules with large-world self-similar properties, while adding just a few weak links can make the network non-fractal and small-world (Gallos et al., 2012).

• 2. Evaluating SW-ness is non-trivial

Due to the diversity of brain imaging techniques and methodological tools, functional networks may vary in size and link distribution and, as a consequence, in their topological parameters. For this reason, quantifying SW-ness and comparing it across networks requires normalizing L and C.

The metric most commonly used to quantify SW-ness, the SW parameter σ, mainly relies on a normalization using random versions of the original networks (Zanin, 2015). However, how to define an adequate ensemble of random networks is not a straightforward task, as it is unclear what properties of the original network should be conserved. Current methodologies use random rewirings of observed connections, typically conserving the number of nodes and links and the degree distribution, but disregarding the effects of network size on the normalized C and L and the statistical properties of the random ensemble.

The reasons for this standard normalization procedure are to do with the generative model proposed by Watts and Strogatz (WS), which explains the formation of SW as a transition region in a rewiring process from regular to completely random structures (Papo et al., 2014), making the latter a reasonable reference point. However, the WS mechanism does not reflect the formation of neural connections, suggesting that alternative references, possibly incorporating anatomical or functional constraints, may be more appropriate for normalizing brain networks, and other properties, e.g., link distribution, number of modules in the network, correlations in the number of links, may be conserved in the random versions of observed network structures.

A normalization against random networks may also fail to provide information about the statistical relevance or abnormality of results, an issue that may be dealt with by means of a Z-Score (Latora and Marchiori, 2001). For instance, two networks with the same normalized clustering coefficient

2.0 may respectively result from a C = 1.0 and expected C_rand = 0.5, and C = 0.02 and C_rand = 0.01. While the former network has a clearly abnormal clustering (the highest possible clustering is not to be expected in a random network), the latter may be the result of random fluctuations. Both situations can occur in the same network, as the threshold value above which existing couplings are converted or not into links is varied. Increasing the threshold value induces a shift from a highly clustered network with overabundant links, to one where networks are highly sparse. Notice in addition that, when the overall network size is small, L cannot vary much, so that σ values are bound to be strongly correlated with C ones (Zanin, 2015). For functional networks obtained from electro- or magneto-encephalography, L is constrained by the low number of nodes, so that σ is mainly controlled by C.

• 3. The true Aquilles heel of the SW measure lies in interpreting its significance.

Suppose that the results of unbiased network analyses of brain activity obtained with an ideal recording device point to a SW network. Can this result be taken at face value?

The results of Barthélemy and Amaral (1999) suggest that, for any given degree of disorder p, if the system is larger than a crossover size, the network will fall in the SW regime. The percentage p of long-range connections making the network SW scales with the number of nodes N as N~p^−2/3 (Kleinberg, 2000), indicating that only a very small fraction of long-range connections can dramatically decrease L. Functional brain imaging studies, which can in principle consider up to 10⁵ nodes, would then typically lead to observing SW-ness.

More importantly, what functional implications should we attribute to a SW brain network? While the SW represents a topological universality class, its functional significance greatly differs in networks of different nature. In communication systems SW networks optimize information processing or transmission efficiency (Kleinberg, 2000), but this is likely not the case for brain networks. The shortest path is usually optimal in a router communication system, whereas in a system such as the brain, other topological (e.g., path redundancy, communicability, branching, loops) and dynamical variables, e.g., burstiness, may better capture information transfer than SW-ness (Karsai et al., 2011; DeDeo and Krakauer, 2012; Estrada et al., 2012; Estrada and Hatano, 2015).

Finally, functional SW networks may result from a diversity of underlying anatomical networks, including randomly connected ones (Hlinka et al., 2015). Thus, the interplay between functional and anatomical networks further enhances the complexity of the SW construct interpretation.

Concluding remarks: Can the SW be salvaged?

The SW has undeniably been one of the most popular network descriptors in the neuroscience literature. Two main reasons for its lasting popularity are its apparent ease of computation and the intuitions it is thought to provide on how networked systems operate. Over the last few years, some pitfalls of the SW construct and, more generally, of network summary measures, have widely been acknowledged. For instance, analyses using less derivative network measures, such as contrasts of basic edge density have been proposed (Zalesky et al., 2010b). However, stress was put far more on technical than on conceptual limitations. The practical advantages of the SW construct often seem to weigh more than fundamental shortcomings. Given the multiple stumbling blocks the SW measure faces, we conclude with two suggestions. First, network normalization should go beyond comparison with “equivalent random networks” and include other properties that account for fundamental properties of brain networks such as modularity, hierarchical structure or spatial embedding. Second, efforts to quantify functional networks' information transfer efficiency or reliability should strive to capture physiologically plausible mechanisms of information transfer and processing. This may involve acknowledging that the universality of network metrics, originally introduced to describe systems profoundly different from the brain, has its limits, and creating a new neuroscience-inspired network science.

Author contributions

All authors listed, have made substantial, direct and intellectual contribution to the work, and approved it for publication.

Acknowledgments

References