Small-World Brain Networks Revisited

Abstract

It is nearly 20 years since the concept of a small-world network was first quantitatively defined, by a combination of high clustering and short path length; and about 10 years since this metric of complex network topology began to be widely applied to analysis of neuroimaging and other neuroscience data as part of the rapid growth of the new field of connectomics. Here, we review briefly the foundational concepts of graph theoretical estimation and generation of small-world networks. We take stock of some of the key developments in the field in the past decade and we consider in some detail the implications of recent studies using high-resolution tract-tracing methods to map the anatomical networks of the macaque and the mouse. In doing so, we draw attention to the important methodological distinction between topological analysis of binary or unweighted graphs, which have provided a popular but simple approach to brain network analysis in the past, and the topology of weighted graphs, which retain more biologically relevant information and are more appropriate to the increasingly sophisticated data on brain connectivity emerging from contemporary tract-tracing and other imaging studies. We conclude by highlighting some possible future trends in the further development of weighted small-worldness as part of a deeper and broader understanding of the topology and the functional value of the strong and weak links between areas of mammalian cortex.

Keywords: connectomics; graph theory; network neuroscience; small-world network; small-world propensity.

Figure 1.

An illustration of the shortest path between Omaha and Boston in Milgram’s social network experiment, published in Psychology Today in 1967. Here, the results of multiple experiments are represented as a composite shortest path between the source (a person in Omaha) and the target (a person in Boston). A letter addressed to the target was given to the source, who was asked to send it on (with the same instructions) to the friend or acquaintance that they thought was most likely to know the target, or someone else who might know the target personally. It was found that most letters that eventually reached the correct address in Boston passed through six intermediaries between source and target (denoted 1st remove, 2nd remove, etc.), popularizing the notion that each of us is separated by no more than “six degrees of freedom” from any other individual in a geographically distributed social network. Reproduced with permission from Milgram (1967).

Figure 2.

Diagrams of clustering and path length in binary and weighted networks. (A) In a binary network, all edges have the same weight, and that is a weight equal to unity. In this example of a binary graph, if one wishes to walk along the shortest path from the orange node to the green node, then one would choose to walk along the edges highlighted in red, rather than along the edges highlighted in blue. We also note that the clustering coefficient of the green node is equal to 1 (all neighbors are also connected to each other to form a closed triangular motif), while the clustering coefficient of the orange node is =1 (only three out of five neighbors are also connected to each other). (B) In a weighted graph, edges can have different weights. In this example, edges have weights of $3/3=1$, $2/3=0.66$, and $1/3=0.33$ If one wishes to traverse the graph from the orange node to the green node along the shortest path, one would choose to follow the path along the edges with weight equal to unity (stronger weights are equivalent to shorter topological distance). Note also that because the edges are now weighted, neither the orange nor the green nodes has a clustering coefficient equal to unity.

Figure 3.

The Watts–Strogatz model and the generation of small-world networks. The canonical model of a small-world network is that described by Duncan Watts and Steve Strogatz in their 1998 article in Nature. The model begins with a regular lattice network in which each node is placed along the circumference of a circle, and is connected to its k nearest neighbors on that circle. Then, with probability p edges are rewired uniformly at random such that (1) at p = 0 the network is a lattice and (2) at p = 1 the network is random. Interestingly, at intermediate values of p the network has so-called “small-world” characteristics with significant local clustering (from the lattice model) and short average path length facilitated by the topological short-cuts created during the random rewiring procedure. Because this architecture can be defined mathematically, small-world graphs have proven fundamental in understanding game theory (Li and Cao 2009) and even testing analytical results in subfields of mathematics (Konishi and Hara 2011). Yet, while this work provided a qualitative model of a small-world graph, it did not give a statistic to measure the degree of small-worldness in a particular data set. As a simple scalar measure of “small-worldness,” Humphries and colleagues defined the small-world index, σ to be the ratio of the clustering coefficient (normalized by that expected in a random graph) to the average shortest path length (also normalized by that expected in a random graph) (Humphries and others 2006). The intuition here is that this index should be large (in particular, σ > 1 when the clustering coefficient is much greater than expected in the random graph, and the average shortest path length is comparable to that expected in a random graph. Since this initial definition, other extensions have been proposed and utilized (Telesford and others 2011; Toppi and others 2012), building on the same general notions.

Figure 4.

High density of the macaque cortical graph excludes sparse small world architecture. (A) Comparison of the average shortest path length and density of the macaque cortical graph from (Markov and others 2013) with the graphs of previous studies (Felleman and Van Essen 1991; Honey and others 2007; Jouve and others 1998; Markov and others 2012; Modha and Singh 2010; Young 1993). Sequential removal of weak connections causes an increase in the path length. Black triangle: macaque cortical graph from Markov and others (2013); gray area: 95% confidence interval following random removal of connections from the macaque cortical graph from Markov and others (2013). Jouve et al., 1998 predicted indicates values of the graph inferred using the published algorithm. (B) Effect of density on Watts and Strogatz’s formalization of a small-world network. Clustering and path length variations generated by edge rewiring with probability range indicated on the x-axis applied to regular lattices of increasingly higher densities. The pie charts show graph density encoded via colors for path length ($L$) and clustering coefficient (C). The y-axis indicates the path length ratio (L_p/L_o) and clustering ratio (C_p/C_o) of the randomly rewired network, where L_o and C_o are the path length and clustering of the regular lattice, respectively. The variables L_p and C_P are the same quantities measured for the network rewired with probability P. Hence, for each density value indicated in the L and C pie charts, the corresponding L_p/L_o and C_p/C_o curves can be identified. Three diagrams below the x-axis indicate the lattice (left), sparsely rewired (middle), and the randomized (right) networks. (C) The small-world coefficient σ (Humphries and others 2006) corresponding to each lattice rewiring. Color code is the same as in panel (B). Dashed lines in (B) and (C) indicate 42% and 48% density levels, respectively. Reproduced with permission from Markov and others (2013).

Figure 5.

Small-world propensity in weighted networks. Here, we illustrate an example of a generative small-world model, and its utility in estimating an empirical network’s small-world propensity. (A) We can extend the concept of a Watts–Strogatz model to weighted graphs by first building a lattice in which the edges are weighted by distance such that edges between spatially neighboring nodes have more strongly weighted than edges between spatially distant nodes. These edge weights can then be rewired with a probability, P, to create a weighted small-world network. (B) Weighted clustering coefficient and weighted path length can be estimated as a function of the rewiring parameter, P, and used to derive the small-world propensity of the graph compared with random and lattice benchmarks (Eq. 11). (C) Weighted small-world propensity calculated for the same network as in panel (B). Error bars represent the standard error of the mean calculated over 50 simulations, and the shaded regions represent the range denoted as small-world. (D) Weighted small-world propensity as a function of network density for a graph of 1000 nodes. Reproduced with permission from Muldoon and others (2016a).

Figure 6.

Binary and weighted small-worldness in mouse and macaque connectomes. For the macaque connectome reported in Markov and others (2013), we show (A) the binary network, a random graph of the same size and density, and the estimated small-world parameters $\mathrm{\Gamma }$ (normalized clustering coefficient), Λ (normalized path length), σ (classical small-world scalar) and φ (small world propensity). In panel (B) we show a weighted network analysis for the same data. For the mouse connectome reported in Rubinov and others (2015), we show (C) the weighted network, a random graph of the same size and density, and the estimated small-world parameters Γ (normalized clustering coefficient), Λ (normalized path length), $\sigma$ (classical small-world scalar) and φ (small world propensity). In panel (D), we show a binary network analysis for the same data. In the boxplots, the gray dotted line shows the threshold value of σ = 1, and the purple area shows the range of values of 0.4 < φ ≤ 1 in which a network is considered small-world.

Figure 7.

Dependence of small-world characteristics on network density. (A) Macaque and (B) mouse connectivity matrices in their natural state (left), as well as after thresholding to retain the 5% strongest (middle) or 25% strongest (right) connections. Weighted small-world metrics including the normalized clustering coefficient (Γ), normalized path length (Λ), small-world index (σ), and small-world propensity (φ) as a function of network density for the (C) macaque and (D) mouse connectivity matrices.

Figure 8.

The existence of weak links and their topology in the mouse connectome. Here, we show the properties of the 5% weakest and 5% strongest edges of the mouse cortical network. (A, B) Axial view of the mouse cortical network, red dots represent brain regions, blue lines represent the connections between them. Drawn are the (A) 5% weakest or (B) 5% strongest edges. Dot size corresponds to degree, the total number of incoming and outgoing edges connected to a node. In (B), the three nodes with highest degree have been labeled as follows: VISp, primary visual area; MOp, primary motor area; SSs, supplemental somatosensory area. The strong connections are spatially organized, mainly connecting spatially adjacent or contralaterally homologous regions. The weak connections span longer distances and are topologically more random than the strongest connections. (C) The distance distributions for (blue) the 5% weakest edges, (red) the 5% strongest edges, and (black) a random graph of the same size and connection density. (D) The degree distributions for the weakest and strongest connections of the mouse connectome, and a comparable random graph, color-coded as in panel (C). Reproduced with permission from Ypma and Bullmore (2016).