pubmed.ncbi.nlm.nih.gov

A spectrum of routing strategies for brain networks - PubMed

  • ️Tue Jan 01 2019

A spectrum of routing strategies for brain networks

Andrea Avena-Koenigsberger et al. PLoS Comput Biol. 2019.

Abstract

Communication of signals among nodes in a complex network poses fundamental problems of efficiency and cost. Routing of messages along shortest paths requires global information about the topology, while spreading by diffusion, which operates according to local topological features, is informationally "cheap" but inefficient. We introduce a stochastic model for network communication that combines local and global information about the network topology to generate biased random walks on the network. The model generates a continuous spectrum of dynamics that converge onto shortest-path and random-walk (diffusion) communication processes at the limiting extremes. We implement the model on two cohorts of human connectome networks and investigate the effects of varying the global information bias on the network's communication cost. We identify routing strategies that approach a (highly efficient) shortest-path communication process with a relatively small global information bias on the system's dynamics. Moreover, we show that the cost of routing messages from and to hub nodes varies as a function of the global information bias driving the system's dynamics. Finally, we implement the model to identify individual subject differences from a communication dynamics point of view. The present framework departs from the classical shortest paths vs. diffusion dichotomy, unifying both models under a single family of dynamical processes that differ by the extent to which global information about the network topology influences the routing patterns of neural signals traversing the network.

PubMed Disclaimer

Conflict of interest statement

The authors have declared that no competing interests exist.

Figures

Fig 1
Fig 1. A spectrum of routing strategies.

The parameter λ controls the extent to which routing strategies (transition probabilities) are reshaped by global information. Toy networks in the top row illustrate how transition probabilities, represented by orange arrows, are reshaped as the parameter λ increases. At each node, the orange arrows are proportional to the probability of a walker moving to a neighboring node via that edge. Blue arrows on the toy networks in the bottom row illustrate a possible walk followed by a random walker (signal) going from node 1 to node t, while operating according to the routing strategy represented by the orange arrows. When λ = 0, transition probabilities at each node are proportional to the strength of its connections. Random walkers operating under this routing strategy (the reference navigation strategy, Pref) diffuse through the network until they eventually arrive at the target node. When λ → ∞, transition probabilities at each node route walkers through the shortest path to the target node; a walker starting at node 1 will follow the shortest path to node t, as illustrated by the blue arrows. In the middle of the spectrum, walker’s dynamics are influenced by global information but still driven partially by local topological properties. Notice that only transition probabilities vary with λ while the underlying network structure remains invariant.

Fig 2
Fig 2. A spectrum of communication processes.

(a) Averages of Cλtrans (red) and Cλinfo (blue) across all node pairs, as a function of λ. Solid red and blue lines correspond to the median across all subjects, whereas the shaded red and blue regions denote the 95th percentile. (b) Averages of ‖Cλtrans‖ (red) and ‖Cλinfo‖ (blue) across all node pairs. These curves are computed by normalizing Cλtrans and Cλinfo with respect to the same cost measures computed on ensembles of 500 randomized networks (per subject). Shaded red and blue areas indicate sections of the curves ‖Cλtrans‖ and ‖Cλinfo‖ that are smaller than 1, respectively, indicating the regions in the spectrum where the communication cost of empirical networks (i.e. networks that are derived from empirical data) is smaller than the cost computed on the randomized ensembles. The dashed vertical lines are placed at the minimum and maximum of ‖Cλtrans‖ (λ2 and λ3, respectively), and at two points near the extremes of the spectrum (λ1 and λ4). (c) pairwise values of Cλtrans(i,t) for all node pairs. (d) pairwise values of Cλinfo(i,t) for all node pairs. In all panels, λ1 = e-4.49, λ2 = e-1.64, λ3 = e0.37 and λ4 = e1.79.

Fig 3
Fig 3. Nodal average transmission costs for four increasingly biased routing strategies.

(a) Scatter plots show the transmission cost associated to each node when it acts as source (C→λtrans) and target (C←λtrans) during communication processes taking place under routing strategies generated with the values λ1, λ2, λ3 and λ4. (b) Scatter plots show the informational cost associated to each node when it acts as source (C→λinfo) and target (C←λinfo) during communication processes taking place under routing strategies generated with the values λ1, λ2, λ3 and λ4. Markers in the scatter plots in (a) and (b), representing each node, are colored according to the node’s membership in the 7 intrinsic connectivity networks (ICN) defined by Yeo et al. (2011) [71]: Visual (VIS), Somatomotor (SM), Dorsal Attention (DA), Ventral Attention (VA), Limbic (LIM), Frontal Parietal (FP), and Default Mode Network (DMN). The size of the markers is proportional to node’s strength. (c) Correlations between node strength and C→λtrans (red), C←λtrans (orange), C→λinfo (green) and C←λinfo (blue) as a function of λ. Solid lines show median correlation across all subjects, shaded areas surrounding the lines show 95th percentile. Shaded colored areas between the vertical dashed lines indicate regions where the correlations were not significant (p > 0.001). (d) Correlation between C→λtrans and C←λtrans (red), and C→λinfo and C←λinfo (blue), as a function of λ. Solid lines show medians across all subjects and shaded areas surrounding solid lines show the 95th percentile. Shaded areas between the vertical dashed lines indicate areas where correlation values were not significant (p > 0.001). In all panels, λ1 = e-4.49, λ2 = e-1.64, λ3 = e0.37 and λ4 = e1.79.

Fig 4
Fig 4. A brain region’s propensity to be a costly source or target.

Cortical surfaces show the difference between a node’s source and target transmission costs. (a) C→λtrans−C←λtrans for routing strategies generated with the values λ1, λ2, λ3 and λ4. (b) C→λinfo−C←λinfo for routing strategies generated with the values λ1, λ2, λ3 and λ4. Red colored areas on the cortical surfaces correspond to nodes whose source transmission/informational cost is higher than their target transmission/informational cost. Blue colored areas correspond to nodes whose target transmission/informational cost is higher than their source transmission/informational cost. In all panels, λ1 = e-4.49, λ2 = e-1.64, λ3 = e0.37 and λ4 = e1.79.

Fig 5
Fig 5. Routing strategies for privileged nodes.

Network average values of Cλtrans (left panel) and Cλinfo (middle panel) as a function of λ (node medians across all subjects) for 22, 55, 110, and 165 privileged nodes (corresponding to 10%, 25%, 50% and 75% of the network’s nodes) that are selected according to betweenness centrality ranking (yellow line), strength ranking (purple line), shortest-path-based closeness centrality (green line), and random-walk-based closeness centrality (blue line). For comparison purposes, we also show cost measures for randomly sampled nodes (red line represents average across 500 samples). The dotted lines show Cλtrans and Cλinfo, respectively, for the case in which all nodes’ routing strategies are biased (i.e. 100% privileged nodes). Right panel shows node stretch distributions for the different sets of privileged nodes and centrality rankings. Black markers indicate the median of the distributions.

Fig 6
Fig 6. Communication cost trade-off within subjects.

(a) Correlations between all subject’s Cλtrans across all values of λ. Positive correlations are colored in red, negative correlations are colored in blue. (b) Eight subject’s Cλtrans and Cλinfo curves after normalization with respect to the max(Cλtrans) and max(Cλinfo), respectively. Notice how some subject’s Cλtrans curves decay faster than others, and how some subject’s Cλinfo curves grow faster than others. (c) Scatter plot of the computed areas under the normalized Cλtrans and Cλinfo curves, sowing a trade-off between the decay of Cλtrans and the growth of Cλinfo (the correlation between A(Cλtrans) and A(Cλinfo) is r = -0.74, p < 0.001).

Similar articles

Cited by

References

    1. Laughlin S.B., & Sejnowski T.J. Communication in neuronal networks. Science 301, 1870–1874 (2003) 10.1126/science.1089662 - DOI - PMC - PubMed
    1. Hu Y., Wang Y., Li D., Havlin S., & Di Z. Possible origin of efficient navigation in small worlds. Physical Review Letters, 106(10), 108701 (2011) 10.1103/PhysRevLett.106.108701 - DOI - PubMed
    1. Kleinberg J. M. Navigation in a small world. Nature, 406(6798), 845–845 (2000) 10.1038/35022643 - DOI - PubMed
    1. Crucitti P., Latora V., Marchiori M., & Rapisarda A. Efficiency of scale-free networks: error and attack tolerance. Physica A: Statistical Mechanics and its Applications, 320, 622–642 (2003)
    1. Kalavri V., Simas T., & Logothetis D. The shortest path is not always a straight line: leveraging semi-metricity in graph analysis. Proceedings of the VLDB Endowment, 9(9), 672–683 (2016)

Publication types

MeSH terms