CoChat
Sign Up
Cited by 115Complex Network Analysis TechniquesFunctional Brain Connectivity StudiesAdvanced Neuroimaging Techniques and Applications

A spectrum of routing strategies for brain networks

Open access
Avena-Koenigsberger, Andrea, Yan, Xiaoran, Kolchinsky, Artemy, van den Heuvel, Martijn P., Hagmann, Patric, Sporns, Olaf·2019·PLOS Computational Biology
DOI 10.1371/journal.pcbi.1006833PMC PMC6426276
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1371/journal.pcbi.1006833

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Identification of shortest paths demands individual regions to possess global knowledge of structural connectivity, which is unlikely in decentralized systems such as the brain.

    “However, algorithmically, the identification of shortest paths demands individual regions to possess global knowledge of structural connectivity, a requirement unlikely to be met in decentralized systems such as the brain (Avena-Koenigsberger et al., 2019; Goñi et al., 2014; Seguin et al., 2018).”

    From Quantitative mapping of the brain’s structural connectivity using diffusion MRI tractography: A review (2022) · cites this paper as Avena-Koenigsberger et al., 2019

    The Introduction says that routing along shortest paths relies on all elements having information about the network’s global topology. The Discussion, however, calls it an open question how a brain system gains that information and raises the possibility that it learns about its topology through feedback; it does not establish that the requirement is unlikely to be met. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 62

  1. [1]Laughlin S.B., & Sejnowski T.J. Communication in neuronal networks. Science 301, 1870– 1874 (2003) 10.1126/science.1089662 14512617 PMC2930149 · DOI · Paper page
  2. [2]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 21469842 · DOI
  3. [3]Kleinberg J. M. Navigation in a small world. Nature, 406(6798), 845– 845 (2000) 10.1038/35022643 10972276 · DOI
  4. [5]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)
  5. [6]Avena-Koenigsberger A., Mišić B., Hawkins R. X., Griffa A., Hagmann P., Goñi J., & Sporns O. Path ensembles and a tradeoff between communication efficiency and resilience in the human connectome. Brain Structure and Function, 222(1), 603– 618 (2017) 10.1007/s00429-016-1238-5 27334341 · DOI
  6. [7]Yan G., Zhou T., Hu B., Fu Z. Q., & Wang B. H. Efficient routing on complex networks. Physical Review E, 73(4), 046108 (2006) 16711879
  7. [8]Yu H., Kim P. M., Sprecher E., Trifonov V., & Gerstein M. The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics. PLoS Comput Biol, 3(4), e59 (2007) 10.1371/journal.pcbi.0030059 17447836 PMC1853125 · DOI
  8. [9]Tombu M.N., Asplund C.L., Dux P.E., Godwin D., Martin J.W., & Marois R. A unified attentional bottleneck in the human brain. Proceedings of the National Academy of Sciences, 108(33), 13426– 13431 (2011) PMC3158154 21825137
  9. [10]Dodds P. S., Watts D. J., & Sabel C. F. Information exchange and the robustness of organizational networks. c, 100(21), 12516– 12521 (2003) PMC218789 14528009
  10. [11]Boccaletti S., Latora V., Moreno Y., Chavez M., & Hwang D. U. Complex networks: Structure and dynamics. Physics reports, 424(4), 175– 308 (2006)
  11. [13]Chen B. L., Hall D. H., & Chklovskii D. B. Wiring optimization can relate neuronal structure and function. Proceedings of the National Academy of Sciences of the United States of America, 103(12), 4723– 4728 (2006) 10.1073/pnas.0506806103 16537428 PMC1550972 · DOI · Paper page
  12. [14]Barthélemy M. Spatial networks. Physics Reports, 499(1), 1– 101 (2011)
  13. [15]Bullmore E., & Sporns O. The economy of brain network organization. Nature Reviews Neuroscience, 13(5), 336– 349 (2012) 10.1038/nrn3214 22498897 · DOI · Paper page
  14. [16]Clune J., Mouret J.B. & Lipson H. The evolutionary origins of modularity. Proc. R. Soc. B, 280(1755), p. 20122863 (2013) 10.1098/rspb.2012.2863 23363632 PMC3574393 · DOI
  15. [17]Betzel R.F., et al Generative models of the human connectome. Neuroimage, 124, pp. 1054– 1064 (2016) 10.1016/j.neuroimage.2015.09.041 26427642 PMC4655950 · DOI · Paper page
  16. [18]Noh J. D., & Rieger H. Random walks on complex networks. Physical review letters, 92(11), 118701 (2004) 10.1103/PhysRevLett.92.118701 15089179 · DOI · Paper page
  17. [19]Yang S. J. Exploring complex networks by walking on them. Physical Review E, 71(1), 016107 (2005) 15697658
  18. [20]Tejedor V., Bénichou O., & Voituriez R. Global mean first-passage times of random walks on complex networks. Physical Review E, 80(6), 065104 (2009) 20365216
  19. [22]Adamic L. A., Lukose R. M., Puniyani A. R., & Huberman B. A. Search in power-law networks. Physical review E, 64(4), 046135 (2001) 11690118
  20. [23]Yin C. Y., Wang B. H., Wang W. X., Zhou T., & Yang H. J. Efficient routing on scale-free networks based on local information. Physics letters A, 351(4), 220– 224 (2006)
  21. [24]van den Heuvel M. P., Kahn R. S., Goñi J., & Sporns O. High-cost, high-capacity backbone for global brain communication. Proceedings of the National Academy of Sciences, 109(28), 11372– 11377 (2012) PMC3396547 22711833
  22. [25]Csoma A., et al Routes Obey Hierarchy in Complex Networks. Scientific reports, 7(1), p. 7243 (2017) 10.1038/s41598-017-07412-4 28775278 PMC5543142 · DOI
  23. [26]Fronczak A., & Fronczak P. Biased random walks in complex networks: The role of local navigation rules. Physical Review E, 80(1), 016107 (2009) 19658774
  24. [27]Lambiotte R., Sinatra R., Delvenne J. C., Evans T. S., Barahona M., & Latora V. Flow graphs: Interweaving dynamics and structure. Physical Review E, 84(1), 017102 (2011) 21867345
  25. [28]Zlatić V., Gabrielli A., & Caldarelli G. Topologically biased random walk and community finding in networks. Physical Review E, 82(6), 066109 (2010) 21230707
  26. [30]Simsek O., Jensen D. Navigating networks by using homophily and degree. Proceedings of the National Academy of Sciences USA 105(35) 12758– 12762 (2008) PMC2522263 18725637
  27. [32]Simas T., Chavez M., Rodriguez P.R. and Diaz-Guilera A. An algebraic topological method for multimodal brain networks comparisons. Frontiers in psychology, 6, p. 904 (2015) 10.3389/fpsyg.2015.00904 26217258 PMC4491601 · DOI
  28. [33]Simas T., & Rocha L.M. Distance closures on complex networks. Network Science, 3(02), 227– 268 (2015)
  29. [34]Todorov E. Efficient computation of optimal actions. Proceedings of the national academy of sciences, 106(28), 11478– 11483 (2009) PMC2705278 19574462
  30. [35]Van Essen D.C., et al The WU-Minn Human Connectome Project: an overview. Neuroimage 80: 6279 (2013) PMC3724347 23684880
  31. [36]Glasser M.F., et al The minimal preprocessing pipelines for the human connectome project NeuroImage, 80, 105– 124 (2013) 10.1016/j.neuroimage.2013.04.127 23668970 PMC3720813 · DOI · Paper page
  32. [37]Avena-Koenigsberger A., et al Using Pareto optimality to explore the topology and dynamics of the human connectome. Phil. Trans. R. Soc. B, 369(1653), 20130530 (2014) PMC4150305 25180308
  33. [39]Estrada E. and Hatano N. Communicability in complex networks. Physical Review E, 77(3), p. 036111 (2008) 18517465
  34. [40]Avena-Koenigsberger A., Mišić B., & Sporns O. Communication Dynamics. Nature Review Neuroscience 19, 17– 33 (2018) 29238085
  35. [41]Roland P.E., Hilgetag C.C., & Deco G. Cortico-cortical communication dynamics. Frontiers in systems neuroscience, 8 (2014) PMC4017159 24847217
  36. [42]Fries P. Rhythms for cognition: communication through coherence. Neuron, 88(1), 220– 235 (2015) 10.1016/j.neuron.2015.09.034 26447583 PMC4605134 · DOI · Paper page
  37. [43]Palmigiano A., Geisel T., Wolf F., & Battaglia D. Flexible information routing by transient synchrony. Nature Neuroscience 20(7), 1014 (2017) 10.1038/nn.4569 28530664 · DOI
  38. [44]Latora V., & Marchiori M. Efficient behavior of small-world networks. Physical Review Letters, 87(19), 198701 (2001) 10.1103/PhysRevLett.87.198701 11690461 · DOI · Paper page
  39. [45]Humphries M. D., & Gurney K. Network ‘small-world-ness’: a quantitative method for determining canonical network equivalence. PloS one, 3(4), e0002051 (2008) 10.1371/journal.pone.0002051 18446219 PMC2323569 · DOI · Paper page
  40. [46]Van Wijk B.C., Stam C.J., & Daffertshofer A. Comparing brain networks of different size and connectivity density using graph theory. PloS one, 5(10), e13701 (2010) 10.1371/journal.pone.0013701 21060892 PMC2965659 · DOI · Paper page
  41. [47]Goñi J., et al Resting-brain functional connectivity predicted by analytic measures of network communication. Proceedings of the National Academy of Sciences, 111(2), 833– 838 (2014) PMC3896172 24379387
  42. [48]Stam C. J., & van Straaten E. C. Go with the flow: use of a directed phase lag index (dPLI) to characterize patterns of phase relations in a large-scale model of brain dynamics. Neuroimage, 62(3), 1415– 1428 (2012) 10.1016/j.neuroimage.2012.05.050 22634858 · DOI
  43. [49]Moon J. Y., Lee U., Blain-Moraes S., & Mashour G. A. General relationship of global topology, local dynamics, and directionality in large-scale brain networks. PLoS computational biology, 11(4), e1004225 (2015) 10.1371/journal.pcbi.1004225 25874700 PMC4397097 · DOI · Paper page
  44. [50]Delvenne J.C., Schaub M.T., Yaliraki S.N., & Barahona M. The stability of a graph partition: A dynamics-based framework for community detection. In Dynamics On and Of Complex Networks, Volume 2 (pp. 221– 242). Springer New York (2013)
  45. [51]Bertolero M.A., Yeo B.T., & D'Esposito M. The Diverse Club: The Integrative Core of Complex Networks. Nature Communications 8; 1277 (2017) 10.1038/s41467-017-01189-w 29097714 PMC5668346 · DOI
  46. [52]Bertolero M.A., Yeo B.T., & D’Esposito M. The modular and integrative functional architecture of the human brain. Proceedings of the National Academy of Sciences, 112(49), E6798– E6807. (2015) PMC4679040 26598686
  47. [54]Guimerà R., Díaz-Guilera A., Vega-Redondo F., Cabrales A. and Arenas A., Optimal network topologies for local search with congestion. Physical review letters, 89(24), p. 248701 (2002). 10.1103/PhysRevLett.89.248701 12484988 · DOI
  48. [55]Françoisse K., Kivimäki I., Mantrach A., Rossi F. and Saerens M. A bag-of-paths framework for network data analysis. Neural Networks, 90, pp. 90– 111 (2017) 10.1016/j.neunet.2017.03.010 28458082 · DOI
  49. [56]Mišić B., Sporns O., & McIntosh A.R. Communication Efficiency and Congestion of Signal Traffic in Large-Scale Brain Networks. PLoS Comput Biol 10(1): e1003427 (2014) 10.1371/journal.pcbi.1003427 24415931 PMC3886893 · DOI
  50. [57]Betzel R.F., & Bassett D.S. Multi-scale brain networks. Neuroimage 160, 73– 83(2016) 10.1016/j.neuroimage.2016.11.006 27845257 PMC5695236 · DOI · Paper page
  51. [58]Messé A., Rudrauf D., Giron A. and Marrelec G. Predicting functional connectivity from structural connectivity via computational models using MRI: an extensive comparison study. NeuroImage 111, pp. 65– 75 (2015) 10.1016/j.neuroimage.2015.02.001 25682944 · DOI
  52. [59]Daducci A., et al The connectome mapper: an open-source processing pipeline to map connectomes with MRI. PloS one, 7(12), e48121 (2012) 10.1371/journal.pone.0048121 23272041 PMC3525592 · DOI
  53. [60]Cammoun L., et al Mapping the human connectome at multiple scales with diffusion spectrum MRI. Journal of neuroscience methods, 203(2), 386– 397 (2012) 10.1016/j.jneumeth.2011.09.031 22001222 · DOI
  54. [61]Wedeen V.J., et al Diffusion spectrum magnetic resonance imaging (DSI) tractography of crossing fibers. Neuroimage, 41(4), 1267– 1277 (2008) 10.1016/j.neuroimage.2008.03.036 18495497 · DOI
  55. [63]de Reus M.A., van den Heuvel M.P. Simulated rich club lesioning in brain networks: a scaffold for communication and integration? Front Hum Neurosci 8: 647, 10.3389/fnhum.2014.00647 (2014) 25191259 PMC4139657 · DOI
  56. [64]Fischl B., et al Automatically parcellating the human cerebral cortex. Cereb Cortex 14: 11– 22, 10.1093/cercor/bhg087 (2004) 14654453 · DOI
  57. [65]Buzsaki G., & Mizuseki K. The log-dynamic brain: how skewed distributions affect network operations. Nat Rev Neurosci 15(4): 264– 278 (2014) 10.1038/nrn3687 24569488 PMC4051294 · DOI
  58. [66]Markov N.T., et al A weighted and directed interareal connectivity matrix for macaque cerebral cortex. Cereb Cortex. 270 (2012) PMC3862262 23010748
  59. [69]Opsahl T., Colizza V., Panzarasa P., & Ramasco J.J. Prominence and control: the weighted rich-club effect. Physical review letters, 101(16), 168702 (2008) 10.1103/PhysRevLett.101.168702 18999722 · DOI
  60. [70]Zlatic, et al On the rich-club effect in dense and weighted networks. The European Physical Journal B, 67(3), 271– 275 (2009)
  61. [71]Maslov S., & Sneppen K. Specificity and stability in topology of protein networks. Science, 296(5569), 910– 913 (2002) 10.1126/science.1065103 11988575 · DOI · Paper page
  62. [72]Yeo B.T., et al The organization of the human cerebral cortex estimated by intrinsic functional connectivity. J Neurophysiol 106(3): 1125– 1165 (2011) 10.1152/jn.00338.2011 21653723 PMC3174820 · DOI · Paper page

Cited by

Sorted by citations

Authors
Avena-Koenigsberger, A., Yan, X., Kolchinsky, A., van den Heuvel, M. P., Hagmann, P., & Sporns, O.
Affiliations
  • Indiana University Bloomington (US)
  • Santa Fe Institute (US)
  • Centre Hospitalier Universitaire Vaudois (CH)
ORCID
Venue
PLOS Computational Biology
Publisher
Public Library of Science (PLoS)
Published
2019-03-08
Volume
15
Issue
3
Pages
e1006833
ISSN
  • 1553-734X (ISSN-L)
  • 1553-7358
DOI
10.1371/journal.pcbi.1006833
PMC
PMC6426276
OpenAlex
W2795327628
Cited by
115
References
4
Citations by year
2026: 1 · 2025: 14 · 2024: 17 · 2023: 17 · 2022: 11 · 2021: 24 · 2020: 28 · 2019: 3
FWCI
7.64
Type
journal article
Language
en
Update notices
new_version (2019-03-20)
Open access
Licence
Locations
  • PLoS Computational Biology (publishedVersion, cc-by)
  • Europe PMC (PubMed Central) (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • VU Research Portal (publishedVersion, other-oa)
  • PubMed (publishedVersion)
  • SERVAL (Université de Lausanne) (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • IRIS (submittedVersion, cc-by)
  • RePEc: Research Papers in Economics (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Figshare (submittedVersion, cc-by)
  • IUScholarWorks Open (Indiana University) (submittedVersion)
  • Amsterdam UMC (VU Amsterdam) - Institutional Repository (submittedVersion, other-oa)
  • Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
  • arXiv (Cornell University)
Funders
  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek (452-16-015, 1U54MH091657)
  • Fondation Leenaards
  • National Institutes of Health (1U54‐MH‐091657)
  • McDonnell Center for Systems Neuroscience (1U54MH091657)
  • NIH Blueprint for Neuroscience Research (1U54-MH-091657)
  • National Center for Complementary and Integrative Health (R01AT009036)
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Life Sciences › Neuroscience › Cognitive Neuroscience › Functional Brain Connectivity Studies
  • Health Sciences › Medicine › Radiology, Nuclear Medicine and Imaging › Advanced Neuroimaging Techniques and Applications
Keywords
brain networks, network routing, biased random walk, shortest path, diffusion, communication overhead, human connectome, network hubs, individual differences, network topology
MeSH terms
Brain Mapping, Communication, Humans, Models, Neurological, Stochastic Processes, Cohort Studies, Connectome

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review