# Navigation of brain networks

^{a}Melbourne Neuropsychiatry Centre, The University of Melbourne and Melbourne Health, Melbourne, VIC 3010, Australia;^{b}Dutch Connectome Lab, Department of Complex Trait Genetics, Center for Neurogenomics and Cognitive Research, Amsterdam Neuroscience, VU University Amsterdam, 1081 HV Amsterdam, The Netherlands;^{c}Department of Clinical Genetics, Amsterdam Neuroscience, VU University Medical Center, 1081 HV Amsterdam, The Netherlands;^{d}Department of Biomedical Engineering, Melbourne School of Engineering, The University of Melbourne, Melbourne, VIC 3010, Australia

See allHide authors and affiliations

Edited by Edward T. Bullmore, University of Cambridge, Cambridge, United Kingdom, and accepted by Editorial Board Member Michael S. Gazzaniga May 7, 2018 (received for review January 24, 2018)

## Significance

We show that the combination of topology and geometry in mammalian cortical networks allows for near-optimal decentralized communication under navigation routing. Following a simple propagation rule based on local knowledge of the distance between cortical regions, we demonstrate that brain networks can be successfully navigated with efficiency that is comparable to shortest paths routing. This finding helps to conciliate the major progress achieved over more than a decade of connectomics research, under the assumption of communication via shortest paths, with recent questions raised by the biologically unrealistic requirements involved in the computation of optimal routes. Our results reiterate the importance of the brain’s spatial embedding, suggesting a three-way relationship between connectome geometry, topology, and communication.

## Abstract

Understanding the mechanisms of neural communication in large-scale brain networks remains a major goal in neuroscience. We investigated whether navigation is a parsimonious routing model for connectomics. Navigating a network involves progressing to the next node that is closest in distance to a desired destination. We developed a measure to quantify navigation efficiency and found that connectomes in a range of mammalian species (human, mouse, and macaque) can be successfully navigated with near-optimal efficiency (>80% of optimal efficiency for typical connection densities). Rewiring network topology or repositioning network nodes resulted in 45–60% reductions in navigation performance. We found that the human connectome cannot be progressively randomized or clusterized to result in topologies with substantially improved navigation performance (>5%), suggesting a topological balance between regularity and randomness that is conducive to efficient navigation. Navigation was also found to (*i*) promote a resource-efficient distribution of the information traffic load, potentially relieving communication bottlenecks, and (*ii*) explain significant variation in functional connectivity. Unlike commonly studied communication strategies in connectomics, navigation does not mandate assumptions about global knowledge of network topology. We conclude that the topology and geometry of brain networks are conducive to efficient decentralized communication.

Nervous systems are networks and one of the key functions of a network is to facilitate communication. Complex topological properties such as small worldness (1, 2), modularity (3), and a core of highly interconnected hubs (4) are universally found across the brain networks of advanced and simple species, including mouse (5, 6), macaque (7, 8), and human connectomes (9). Support for efficient communication between neuronal populations is conjectured to be one of the main adaptive advantages behind the emergence of these complex organizational properties (10, 11).

Understanding how neural information is routed and communicated through complex networks of white matter pathways remains an open challenge for systems neuroscience (12, 13). To date, connectomics has largely focused on network communication based on optimal routing (14, 15), which proposes that information traverses the shortest path between two nodes. However, identifying shortest paths requires individual elements of nervous systems to possess global knowledge of network topology. This requirement for centralized knowledge has been challenged on the basis that nervous systems are decentralized, motivating alternative models of large-scale neural communication, such as spreading dynamics (11), path ensembles (16), communicability (17, 18), and diffusion models (19⇓–21). These studies indicate that brain networks may support efficient communication without the need for centralized knowledge. For instance, random walkers can be biased to travel via efficient routes (22) and shortest paths help facilitate fast spreading of local stimuli (11).

Navigation is a network communication strategy that routes information based on the distance between network nodes (23). Navigating a network is as simple as progressing to the next node that is closest in distance to a desired target. Navigation is not guaranteed to successfully reach a target destination. Moreover, targets might be reached using long, inefficient paths. However, several real-world networks are known to be efficiently navigable, including biological, social, transportation, and technological systems (24⇓–26). Successful navigation depends on certain topological properties such as small worldness (23) and a combination of high clustering and heterogeneous degree distribution (24), all of which are found in the brain networks of several species (9).

Here, we comprehensively investigate the feasibility of navigation routing as a model for large-scale neural communication. We develop a measure of navigation efficiency and apply it to publicly available connectomics data acquired from the macaque, mouse, and human brain. We find that brain networks are highly navigable, with connectome topology well poised between regularity and randomness to facilitate efficient navigation. In addition, we characterize the centrality of nodes and connections under navigability and investigate the relation between navigation path lengths and functional connectivity (FC) inferred from resting-state functional magnetic resonance imaging (MRI). Compared with shortest path routing, we find that navigation uses the brain’s resources more uniformly and yields stronger correlations with FC.

## Results

### 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. 1*B*). The success ratio (

Let

We focus on binary (

### 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 (*A*). Remarkably, navigation was only marginally less efficient than shortest paths (e.g., *B*–*D*), with navigation performance improving as connection density increased. Note that navigation does not use connection weights, and thus *SI Appendix*, Fig. S1), with moderate decreases in success and efficiency ratios as the number of nodes increased (*N* = 256, 512, and 1,024, respectively, at 15% connection density; Fig. 2*E*). When stratified by hop count, navigation performance remained high for long, multihop paths (61% median *F* 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.

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 *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 (*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 *E*). As with the human connectome, navigation performance was significantly increased compared with the topologically rewired and spatial null networks (all *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. 3*A*). Specifically, peak *N* = 256, 360, 512, respectively. Further randomization beyond these peaks resulted in deterioration of navigation efficiency. Similar results were found for *SI Appendix*, Fig. S10).

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 *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, *A* and *B*). However, NC was more uniformly distributed across nodes compared with BC, suggesting that navigation uses network resources more homogeneously (Fig. 4*C*). High values of BC were found only in a small group of high-degree nodes (*D*). In contrast, although high-degree nodes showed high NC (*SI Appendix*, Fig. S12) and for edge-centric definitions of BCs and NCs (*SI Appendix*, Fig. S13). All correlation coefficients (r) were significant (

### 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

## Discussion

This study investigated navigation as a model for large-scale neural communication. Using a measure of navigation efficiency, we evaluated the navigability of a range of mammalian connectomes. We found multiple lines of evidence suggesting that the topology (wiring) and spatial embedding (geometry) of nervous systems is conducive to efficient navigation. Our measure of navigation centrality indicated that navigation uses network resources more uniformly compared with shortest paths. We conclude that navigation is a viable neural communication strategy that does not mandate the centralized knowledge assumptions inherent to shortest paths, nevertheless achieving near-optimal routing efficiency.

Navigation performance was assessed for binary, weighted, and distance-based connectomes, each emphasizing a distinct attribute of network communication. While binary and weighted brain networks are commonly used in connectomics (12), distance-based connectomes were introduced to provide a geometric benchmark for navigation efficiency. Interestingly, navigation paths were simultaneously efficient in all three regimes, suggesting that neural signaling may favor communication routes that combine few synaptic crossings (binary), high axonal strength and reliability (weighted), and short propagation distances (distance based).

The topology of the human connectome was found to be well poised between regularity and randomness to promote efficient decentralized communication. While our focus on this order spectrum was motivated by canonical work on brain and real-world networks (1, 10), other dimensions of connectome topology such as degree diversity or hierarchical structure could be investigated (35). In fact, progressive rewiring explicitly seeking to optimize navigation indicates that connectome topology has a 5–22% margin for improvement in navigability. These findings support the notion that communication efficiency was likely only one of several evolutionary pressures that shaped connectome architecture (10, 13) (*SI Appendix, Supplementary Analyses*).

The significant association between navigation and FC is further evidence that neural communication is not necessarily constrained to optimal routes (22). This association could not be entirely attributed to navigation path lengths approximating interregional distances. Therefore, our findings build on previous work on the relationship between Euclidean distance and FC (27, 36), indicating that the combination of topological and geometric distances may contribute to the relationship between brain structure and function. Alternative formulations of interregional distances taking into account fiber-tract length or tract myelination could improve the biological relevancy of node distances, potentially improving the association between navigation path lengths and FC.

### Connectome Geometry, Topology, and Communication.

Several recent studies have drawn attention to the link between geometry and topology in neural and other real-world networks (24, 27, 28). Our findings indicate that the interplay between connectome geometry and topology may be relevant for neural communication: The association between network geometry and topology (28, 37) contributes to the appearance of topological attributes conducive to navigation (24, 26), while the spatial positioning of nodes guides navigation of the topology, facilitating efficient decentralized communication. This notion is supported by our analyses of the navigation performance of different null models. Randomization of either connectome topology or geometry was sufficient to render connectomes less navigable, while topological randomizations that preserved characteristics of connectome geometry led to marked improvements in the navigability of null networks (see *SI Appendix, Supplementary Analyses* for further discussion).

Successful navigation has been linked to small-world topologies that combine spatially separated hubs and high-clustering coefficients (23, 24). Hub-to-hub long-range connections facilitate rapid information transfer across distant regions of the brain (although see ref. 38 for a counterpoint), while high clustering enables navigation to home in on specific destinations (4, 24) (*SI Appendix*, Fig. S15). This mechanism for information transfer is consistent with observations suggesting that nervous systems are small-world networks, balancing integration supported by long-range connections and segregation due to locally clustered modules (10).

### Biological Plausibility and Communication Efficiency.

To date, the study of brain network organization has been anchored to the assumption of communication under shortest path routing (12, 15). Two examples are the characterization of the brain as a small-world network (1, 2) and the use of global efficiency as a measure of network integration (10, 14). These topological properties are derived from the shortest paths between all pairs of nodes. Building on previous work suggesting that efficient neural communication may take place in a decentralized manner (11, 22), we found that navigation can approximate the overall efficiency of shortest paths without requiring centralized knowledge of global network topology. Thus, we provide reassurance that previous findings obtained under the shortest paths assumption remain pertinent, despite the biologically implausible requirements for the computation of optimal routes, and reaffirm the importance of the brain’s small-world architecture in the light of decentralized routing schemes.

Navigation depends on network nodes possessing information about the relative spatial positioning between their direct neighbors and a target node. While the biological mechanisms that might endow nodes with this spatial information remain unclear, it is important to remark that navigation demands less information about network topology than shortest path routing and thus requires fewer assumptions to support its biological plausibility. Hence, in terms of biological plausibility, navigation occupies a middle ground between shortest paths and other decentralized models such as communicability (17, 18) and diffusion processes (19⇓–21), which mandate fewer assumptions. However, navigation is near-optimally efficient and metabolically parsimonious (information is routed through a single path), thus overcoming important shortcomings of diffusion (39) and communicability (13) models, respectively.

Future research on large-scale neural communication models is necessary to explore alternative decentralized, efficient, and parsimonious network communication strategies. Exploring alternative spatial embeddings of brain networks (e.g., in hyperbolic space) may provide further insight into the navigability of nervous systems across species (40). In parallel, brain stimulation techniques could be used to evaluate evidence for competing communication strategies by means of electrophysiological tracking of local perturbations (41, 42).

## Materials and Methods

Details on the acquisition and preprocessing of network datasets are described in *SI Appendix, Connectivity Data*. *SI Appendix, Network Analysis* provides details on network modeling. Supporting and replication analyses are presented in *SI Appendix, Supplementary Analyses*.

### Navigation Implementation.

For a network with N nodes, navigation routing from node i to j was implemented as follows. Determine which of i’s neighbors is closest (shortest Euclidean distance) to j and progress to it. Repeat this process for each new node until j is reached—constituting a successful navigation path—or a node is revisited—constituting a failed navigation path.

Navigation paths are identified based on network topology and the spatial positioning of nodes and thus independent from how connection lengths are defined. Navigation path lengths, however, are the sum of connection lengths composed in navigation paths and will vary depending on the definition of L. The matrix of navigation path lengths Λ was computed by navigating every node pair. Note that Λ is asymmetric, requiring **1**.

### Data Sharing.

Human, macaque, and mouse datasets are publicly available. Our implementation of navigation routing is available at https://github.com/caioseguin/connectomics/.

## Acknowledgments

We thank Mikail Rubinov for providing connectivity data for the mouse. Human data were provided by the Human Connectome Project, WU–Minn Consortium (1U54MH091657; Principal Investigators David Van Essen and Kamil Ugurbil) funded by the 16 National Institutes of Health (NIH) institutes and centers that support the NIH Blueprint for Neuroscience Research, and by the McDonnell Center for Systems Neuroscience at Washington University. C.S. is funded by a Melbourne Research Scholarship. M.P.v.d.H. was funded by an ALW (Earth and Life Sciences) open (ALWOP.179) and VIDI (452-16-015) grant from the Netherlands Organization for Scientific Research (NWO) and a Fellowship of MQ. A.Z. is supported by the Australian National Health and Medical Research Council (NHMRC) Senior Research Fellowship B (1136649).

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. Email: caioseguin{at}gmail.com.

Author contributions: C.S. and A.Z. designed the research; C.S. and A.Z. performed research; C.S. and A.Z. contributed new reagents/analytic tools; C.S. and A.Z. analyzed data; and C.S., M.P.v.d.H., and A.Z. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission. E.T.B. is a guest editor invited by the Editorial Board.

Data deposition: All data analyzed in this work are publicly available. Human data are from the Human Connectome Project (https://db.humanconnectome.org/); macaque data can be found at core-nets.org/; and mouse data were gathered from the following publicly available resources: connectivity.brain-map.org; developingmouse.brain-map.org/; and mouse.brain-map.org/.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1801351115/-/DCSupplemental.

- Copyright © 2018 the Author(s). Published by PNAS.

This open access article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND).

## References

- ↵
- ↵
- ↵
- ↵
- van den Heuvel MP,
- Kahn RS,
- Goñi J,
- Sporns O

- ↵
- ↵
- Rubinov M,
- Ypma RJF,
- Watson C,
- Bullmore ET

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Fornito A,
- Zalesky A,
- Bullmore ET

- ↵
- ↵
- ↵
- ↵
- Avena-Koenigsberger A, et al.

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Goñi J, et al.

- ↵
- ↵
- ↵
- ↵
- Allard A,
- Serrano MÁ,
- Gárcia-Pérez G,
- Boguña M

- ↵
- Vértes PE, et al.

- ↵
- ↵
- ↵
- ↵
- Maslov S,
- Sneppen K

- ↵
- ↵
- ↵
- Honey CJ, et al.

- ↵
- ↵
- ↵
- Roberts JA, et al.

- ↵
- Betzel RF,
- Bassett DS

- ↵
- ↵
- Allard A,
- Serrano M

- ↵
- Gollo LL,
- Roberts JA,
- Cocchi L

- ↵
- Khambhati AN, et al.

## Citation Manager Formats

## Article Classifications

- Biological Sciences
- Neuroscience

### This article has a Letter. Please see:

- Relationship between Research Article and Letter - January 10, 2019