Navigation of brain networks

Navigation Performance Measures.

We consider neural communication from the graph-theoretic standpoint of delineating paths (routes) in the connectome between pairs of nodes (gray matter regions). A routing strategy defines a set of rules for identifying a path from a source node to a target node. Path length refers to the number of connections that compose a path (hops) or the sum across the lengths of these connections. To minimize conduction latency, noise introduced by synaptic retransmission, and metabolic costs, neural communication should take place along paths with short path lengths (12, 13).

Navigation is a decentralized communication strategy that is particularly suited to spatially embedded networks (24, 25). Navigating a network involves following a simple rule: Progress to the next directly connected node that is closest in distance to the target node and stop if the target is reached (Fig. 1). To implement navigation, we defined the distance between pairs of nodes as the Euclidean distance between node centroids (27, 28). Importantly, navigation can fail to identify a path. This occurs when a navigation path becomes trapped between nodes without neighbors closer to the destination than themselves (Fig. 1B). The success ratio (SR) measures the proportion of node pairs in a network that can be successfully reached via navigation.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 1.

Illustrative examples of navigation (green) and shortest (red) paths from a source to the target node (circled in orange) in a binary network. Grid indicates spatial embedding of the networks. Efficiency ratios (ER(i,j)) are the ratio of the number of hops in the navigation path to the number of hops in the shortest path. (A) The shortest path between A and H has three hops (A-B-E-H) while navigation leads to a four-hop path (A-D-F-G-H). Navigation routes information from A to H at 75% of optimal efficiency. (B) Navigation fails to find a path from B to F, becoming trapped between E and H. (C) Both strategies lead to three-hop paths, and navigation routes information from G to B at 100% of optimal efficiency. (D) Example of a successful navigation path in the human connectome that achieves 75% efficiency.

Let L ∈RN×N denote a matrix of connection lengths for a network comprising N nodes, where Lij measures the length of the connection from node i to j, and let Λ denote the matrix of navigation path lengths. If node i cannot navigate to node j, Λij=∞. Otherwise, Λij=Liu+...+Lvj, where {u,...,v} is the sequence of nodes visited during navigation. We define navigation efficiency as E=1/(N2−N)∑i ≠ j1/Λij. Analogous to global efficiency (29) [E*=1/(N2−N)∑i ≠ j1/Λij*, where Λij* is the shortest path length from node i to j], both measures characterize the efficiency of information exchange in a parallel system in which all nodes are capable of concurrently exchanging information. In the same way that global efficiency can incorporate network disconnectedness, navigation efficiency incorporates unsuccessful navigation paths (Eij=0 if i cannot reach j under navigation). Therefore, E quantifies both the number of failed paths and the efficiency of successful paths. We defined the efficiency ratioER=1N2−N∑i ≠ jΛij*Λij[1]to compare navigation with shortest path routing. For any network, E*≥E and thus 0≤ER≤1. The closer ER is to 1, the better navigation is at finding paths that are as efficient as shortest paths (Fig. 1).

We focus on binary (ERbin) and weighted (ERwei) navigation efficiency ratios, quantifying how efficient navigation paths are compared with shortest paths computed on binarized and weighted connectomes, respectively. In addition, we compute ERdis to determine how close navigation paths are to routes that minimize the sum of physical (Euclidean) connection distances traversed between nodes.

Navigability of the Human Connectome.

High-resolution diffusion MRI data from 75 healthy participants of the Human Connectome Project (HCP) (30) were used to map structural brain networks at several spatial resolutions (N = 256, 360, 512, 1,024). Whole-brain tractography was performed for each individual and the number of streamlines interconnecting each pair of nodes was enumerated to provide a measure of structural connectivity (SI Appendix, Connectivity Data). A group-level connectome was computed as the average of all individual connectivity matrices (22). Connection weights were remapped into binary, weighted, and distance-based connection lengths to allow for the computation of communication path lengths (SI Appendix, Network Analysis).

Consistent with previous reports (24, 25), we found that navigation can successfully identify paths for the majority of nodes pairs composing the human connectome (SR= 89%, 94%, and 96% for 10%, 15%, and 20% connection density, respectively, N=360; Fig. 2A). Remarkably, navigation was only marginally less efficient than shortest paths (e.g., ERwei= 72%, ERbin= 83%, and ERdis= 83%, for N=360 at 15% connection density; Fig. 2 B–D), with navigation performance improving as connection density increased. Note that navigation does not use connection weights, and thus ERwei quantifies the extent to which navigation can blindly identify weighted shortest paths. Navigation remained efficient and successfully identified paths for the majority of node pairs across various parcellation resolutions (SI Appendix, Fig. S1), with moderate decreases in success and efficiency ratios as the number of nodes increased (SR= 95%, 91%, and 90% and ERbin= 84%, 80%, and 81% for N = 256, 512, and 1,024, respectively, at 15% connection density; Fig. 2E). When stratified by hop count, navigation performance remained high for long, multihop paths (61% median ERwei and 79% median ERdis benchmarked against five-hop shortest paths; Fig. 2F and SI Appendix, Fig. S2), suggesting that navigation efficiency is not due to directly connected node pairs or node pairs that can be navigated in only a few hops.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 2.

Navigability of mammalian connectomes. (A–D) Success ratio (SR), binary efficiency ratio (ERbin), weighted efficiency ratio (ERwei), and distance efficiency ratio (ERdis) for human connectomes (N=360) at several connection density thresholds. Empirical measures (red) for group-averaged connectomes were compared with 1,000 rewired (green) and spatially repositioned (blue) null networks. Shading indicates 95% confidence intervals. (E) The same performance metrics shown across different parcellation resolutions of mammalian structural networks (SR shown in blue, ERwei in orange, ERbin in yellow, and ERdis in purple). Triangles denote nonhuman species while circles denote human data. Dashed lines denote the same connection density (15%) across all human networks. (F) Navigability stratified by hop count (N=360 at 15% connection density). Blue box plots indicate the quartiles of ERwei navigation paths benchmarked against shortest paths with matching hop count. Bar plots show the number of shortest paths for a given hop count, with colors indicating the proportion of successful (green) and failed (red) navigation paths. Brain diagrams reproduced from ref. 9, with permission from Elsevier.

Having established that the human connectome can be successfully and efficiently navigated, we next sought to determine whether efficient navigation is facilitated by the connectome’s topology or its spatial embedding. Navigation performance was benchmarked against ensembles of random null networks in which (i) the spatial position of nodes was shuffled; (ii) connectome topology was randomized (31); or (iii) connectome topology was randomized while preserving total network cost, defined as the sum of Euclidean distances between structurally connected nodes (10, 28) (SI Appendix, Network Analysis). Navigability of both the spatial and topological null networks was markedly reduced in comparison with the empirical networks (46% and 60% decrease in ERbin and 48% and 60% decrease in ERwei, for topological and spatial randomization, respectively, at 15% connection density; Fig. 2 A–D, blue and green curves). In contrast, cost-preserving topological randomization resulted in null networks that, although significantly less navigable than the human connectome (P<10−4; 13% and 11% decrease in ERbin and ERwei, respectively, at 15% connection density; SI Appendix, Fig. S3), showed greater navigation performance than the less constrained null models. Taken together, these results suggest that navigation is jointly facilitated by both the connectome’s topology and its geometry. Randomization of either of these attributes markedly impeded navigation, while restricting topological randomization to realistic spatial embeddings accounted for a large extent of empirical navigation performance.

These findings were robust to variations in node distance measures and streamline count normalizations (SI Appendix, Supplementary Analyses and Figs. S4 and S5). Navigation performance of individual connectomes was comparable to the performance determined for the group-averaged connectome (SI Appendix, Fig. S6). Furthermore, navigation performance significantly deteriorated with age (SI Appendix, Fig. S7 and Table S1), but did not differ between males and females (SI Appendix, Fig. S8).

Navigability of Nonhuman Mammalian Connectomes.

Invasive tract-tracing studies provide high-quality connectomes for a number of nonhuman species (9). We aimed to determine whether a 112-region mouse connectome (52% connection density) (5, 6) and a 29-region macaque connectome (66% connection density) (8) were navigable. Navigation performed with SR= 100% and near-optimal communication efficiency for both species (ERbin= 99%, 97%; ERdis= 97%, 94%; and ERwei= 87%, 84%, for the macaque and mouse, respectively; Fig. 2E). As with the human connectome, navigation performance was significantly increased compared with the topologically rewired and spatial null networks (all P<10−4, with the exception of P=0.012 and P=0.002 for the macaque SR of topological and spatial null networks, respectively). However, the null hypothesis of equality in navigation performance between the connectomes of both species and the cost-preserving null networks could not be rejected (SI Appendix, Fig. S9).

The efficient navigation of connectomes across a variety of species, scales, and mapping modalities suggests that the topology and spatial embedding of nervous systems is conducive to efficient decentralized communication.

Connectome Topology and Navigation Performance.

We sought to explore the impact of progressive topological alterations on the navigability of the human connectome. First, we tested whether navigation efficiency can be improved by progressively altering the topology of the human connectome to either increase its regularity (clusterize) or increase its randomness and wiring cost. Randomization was performed by progressively swapping connections between randomly chosen node pairs, while preserving connection density and degree distribution (31). With sufficient iterations, this yielded the topologically randomized null networks shown in Fig. 2 A–D (green curves). To clusterize topology, the same procedure was used with the additional constraint that each connection swap must lead to an increase in the overall clustering coefficient. Applying these procedures generated two sets of networks that progressively tended toward different ends of an order spectrum, ranging from orderly and regular networks with a high clustering coefficient to disordered and costly random networks (SI Appendix, Network Analysis). Clusterization was found to progressively decrease navigation efficiency, whereas slight randomization of connectome topology yielded networks with marginal increases in navigation performance (Fig. 3A). Specifically, peak ERwei was, on average, 0.8%, 1.4%, and 4.7% more efficient than the connectome after 4.0%, 3.3%, and 4.8% of connections were randomly swapped, for N = 256, 360, 512, respectively. Further randomization beyond these peaks resulted in deterioration of navigation efficiency. Similar results were found for ERbin (SI Appendix, Fig. S10).

• Download figure
• Open in new tab
• Download powerpoint

Fig. 3.

Navigation performance (ERwei) of progressively rewired connectome topologies (at 15% connection density). The ERwei of rewired topologies was normalized by the empirical value found for the human connectome. Curves indicate the mean values (inner line) and 95% confidence intervals (outer shadow) obtained from several runs of the rewiring routines. (A) Normalized ERwei of clusterized and randomized networks for 100 runs of the randomization–clusterizing procedure and different parcellation resolutions. Dashed lines show performance peaks (vertical axis) and number of connection swaps (horizontal axis), with red indicating the values obtained for the empirical brain. (B) Normalized ERwei obtained from direct optimization of the connectome’s empirical ERwei, as a function of connection swap attempts, for 50 (N=256), 50 (N=360), and 30 (N=512) independent rewiring runs.

Next, we investigated the effects of connectome rewiring aimed to explicitly increase navigability. To this end, we progressively performed connection swaps between randomly chosen node pairs that (i) preserved connection density and degree distribution, (ii) led to an increase of a measure of navigation performance, and (iii) preserved total network cost. We performed a total of 2×106 connection swap attempts, with rejection of swaps that did not simultaneously meet all three conditions. Direct optimization of network navigability led to an 18–20% increase in ERwei, with 16–18% of the improvement taking place in the first 106 swap attempts. Therefore, increasing connectome navigability rapidly became more difficult as a function of swap attempts, suggesting that the observed improvements converge to an asymptote. Comparable improvements between 5% and 22% were found for other measures of navigation performance (SI Appendix, Fig. S11). Collectively, these results indicate that the human connectome is well poised between randomness and regularity to facilitate efficient navigation, while explicit optimization by connectome rewiring converges to 5–22% improvements in navigability.

Navigation Centrality.

The number of shortest paths that traverse a node defines its betweenness centrality (BC), a measure that finds utility in identifying connectome hub nodes (12) and nodes mediating the bulk of neural communication (7). We defined a new path-based centrality measure called navigation centrality (NC), which quantifies the number of successful navigation paths that traverse each node (SI Appendix, Network Analysis).

We computed NC and BC for the human connectome (group average, N=360, at 15% connection density), with BC based on weighted shortest paths. We found that both NC and BC spanned four orders of magnitude and were positively correlated (Pearson correlation coefficient r=0.54). Several regions were central to both shortest paths (BC) and navigation (NC), including portions of the left and right superior frontal gyrus, insula, central gyri, and precuneus (Fig. 4 A and B). However, NC was more uniformly distributed across nodes compared with BC, suggesting that navigation uses network resources more homogeneously (Fig. 4C). High values of BC were found only in a small group of high-degree nodes (r=0.86 between logarithm of BC and degree), which mediated most of the network’s communication routes. For instance, 99.3% of all shortest paths traveled exclusively through the top 50% most connected nodes (Fig. 4D). In contrast, although high-degree nodes showed high NC (r=0.61 between logarithm of NC and degree), medium- and low-degree regions were responsible for mediating a share of navigation paths, with the 50% least-connected nodes responsible for 26% of navigation paths. Greater diversity in paths may lead to fewer communication bottlenecks and less signal congestion (32), as well as stronger resilience against failure of network elements (16, 33). Similar results were obtained for BC computed in binarized connectomes (SI Appendix, Fig. S12) and for edge-centric definitions of BCs and NCs (SI Appendix, Fig. S13). All correlation coefficients (r) were significant (P<10−8).

• Download figure
• Open in new tab
• Download powerpoint

Fig. 4.

Comparison between navigation (NC) and weighted betweenness (BC) node centralities for N=360 at 15% connection density. Centrality values are logarithmically scaled. (A and B) NC (A) and BC (B) projected onto the cortical surface. (C) NC (Left) and BC (Right) sorted from highest to lowest values. (D) Relationship between the cumulative sum of centrality measures and degree. The horizontal axis is a percentage ranking of nodes from highest to lowest degree (e.g., for N=360, the 10% most connected nodes are the 36 nodes with highest degree). Solid curves (left-hand vertical axis) represent the cumulative sum of BC (red) and NC (green) over all nodes ordered from most to least connected, divided by the total number of communication paths in the network, indicating the fraction of communication paths mediated by nodes. Blue dots (right-hand vertical axis) show the original degree associated with each percentage of most-connected nodes.

Navigation and Functional Connectivity.

Finally, we tested whether navigation path lengths can explain variation in functional connectivity across nodes pairs of the human connectome. The strength of functional connectivity between node pairs that are not directly connected can be attributed to signal propagation along multisynaptic (multihop) paths (22, 34). Therefore, if multihop neural communication is indeed facilitated by navigation, we hypothesized that navigation path lengths should be inversely correlated with functional connectivity strength. Resting-state functional MRI data from the same 75 participants of the HCP were used to map functional brain networks. A group-averaged functional network was obtained by averaging FC across all participants (SI Appendix, Connectivity Data).

Given the geometric nature of navigation, an intuitive definition of navigation path length is the total distance traveled from one node to another along the navigation path (SI Appendix, Network Analysis). Navigation path lengths and FC were significantly associated across node pairs (SI Appendix, Fig. S14), with Pearson correlation coefficient r=−0.32 and r=−0.43, for the whole brain and right hemisphere, respectively, for N=360 at 15% connection density. This relationship was consistent across density thresholds, with navigation path lengths yielding stronger correlations with FC than shortest path lengths (r=−0.35, right hemisphere) and the direct Euclidean distance between node pairs (r=−0.40, right hemisphere). Correlations with navigation path lengths remained significant when stratified by structurally connected (r=−0.51, right hemisphere) and unconnected (r=−0.28, right hemisphere) node pairs. All correlations remained significant when interregional Euclidean distances were regressed from navigation path lengths and the resulting residuals correlated with FC (P<10−5).