Navigability of Complex Networks
By Marián Boguñá, Dmitri V. Krioukov, K. Claffy. 2007
455 citations recorded by the source corpus.
In many real-world processes that can be mapped onto complex networks—from cell signalling to transporting people—communication between distant nodes is surprisingly efficient, considering that no node has a full view of the entire network. A framework sets out to explain why ‘navigability’ is so efficient in these networks.
Subfields: Biomedical Engineering, Molecular Biology, Statistical and Nonlinear Physics, Algorithms & Complexity, Network Science & Complex Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Biomedical Engineering
In Molecular Biology
- Gregorio Alanis-Lobato
- Anthony Randal McIntosh
- Osvaldo Novaes de Oliveira Jr.
- Luciano da Fontoura Costa
- Olaf Sporns
- Luis Enrique Correa Rocha
- Deng Cai
- P. R. Villas Boas
In Statistical and Nonlinear Physics
- Olaf Sporns
- Bratislav Misic
- Gábor Rétvári
- András Gulyás
- Attila Korösi
- József Bíró
- Andrea Avena-Koenigsberger
- Gregorio Alanis-Lobato
In Algorithms & Complexity
- Gregorio Alanis-Lobato
- Cong Fu
- Deborah Estrin
- Osvaldo Novaes de Oliveira Jr.
- Luciano da Fontoura Costa
- Chao Xiang
- Olaf Sporns
- Luis Enrique Correa Rocha
In Network Science & Complex Systems
- Osvaldo Novaes de Oliveira Jr.
- Luciano da Fontoura Costa
- Olaf Sporns
- Luis Enrique Correa Rocha
- P. R. Villas Boas
- Francisco Aparecido Rodrigues
- Matheus Palhares Viana
- Gonzalo Travieso
Citations in the corpus
- Communication Efficiency and Congestion of Signal Traffic in Large-Scale Brain Networks (2014, background): “This has led to the hypothesis that if rich club topology is configured in a way that facilitates cortico-cortical communication via shortest paths, there may exist a set of routing or navigation strategies to take advantage of this feature [16], such as ‘‘greedy’’ routing [31].”
- Navigable networks as Nash equilibria of navigation games (2014, result): “This is fully in line with the edge-locality principle of complex networks [68] [69] [70] which many times accounted for the high clustering coefficient.”
- Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017, background): “Navigable Small-World Networks [9,29] are suitable for the ANNS problem by their nature.”
- Growing Homophilic Networks Are Natural Navigable Small Worlds (2015, unknown): “Our simulations show that, for the scale-free networks (both in GH networks with PA and scale-free networks studied in [16]), the number of distance computations has a power law scaling with the number of network elements, in contrast to GH networks without PA and Kleinberg ’ s networks which have…”
- From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks (2013, background): “…of Guimera et al. - and the need to formalise them in a paradigm such as LCP - appear clearer if interpreted in the light shed by two theories recently posited, one by Bogun˜a´ et al. 37 on the navigability of complex networks, and the other by Liu et al. 38 on the controllability of the same.”
- Communication dynamics in complex brain networks (2017, background): “The amount of information needed to discover a path in a network. that neural signals have access to information or knowledge about the global network topology 50–52 .”
- A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, background): “An improvement direction is put forth by [19, 66] to overcome NSW’s poly-logarithmic search complexity.”
- Analyzing and modeling real-world phenomena with complex networks: a survey of applications (2007, background): “[208] analytically proved: using only local information nodes can work efficiently, especially in networks with powe r-law degree distribution and high clustering coefficient, such as the Internet.”
- Named Data Networking (NDN) Project (2010, background): “Unfortunately, standard greedy routing does not always succeed in reaching the destination [9], sometimes getting stuck at local minima, i.”