Navigability of Complex Networks

Abstract

Routing information through networks is a universal phenomenon in both natural and manmade complex systems. When each node has full knowledge of the global network connectivity, finding short communication paths is merely a matter of distributed computation. However, in many real networks nodes communicate efficiently even without such global intelligence. Here we show that the peculiar structural characteristics of many complex networks support efficient communication without global knowledge. We also describe a general mechanism that explains this connection between network structure and function. This mechanism relies on the presence of a metric space hidden behind an observable network. Our findings suggest that real networks in nature have underlying metric spaces that remain undiscovered. Their discovery would have practical applications ranging from routing in the Internet and searching social networks, to studying information flows in neural, gene regulatory networks, or signaling pathways.

References in corpus (14)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• The architecture of complex weighted networks
• The large-scale organization of metabolic networks
• Classes of behavior of small-world networks
• Hierarchical structure and the prediction of missing links in networks
• Identity and Search in Social Networks
• Vertex similarity in networks
• Class of correlated random networks with hidden variables
• Self-similarity of complex networks and hidden metric spaces
• The Internet AS-Level Topology: Three Data Sources and One Definitive Metric
• On Compact Routing for the Internet
• Network Structure of Protein Folding Pathways

Cited by in corpus (139)

• Spatial Networks
• Hyperbolic Geometry of Complex Networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Sustaining the Internet with Hyperbolic Mapping
• Networks in Cognitive Science
• Spreading dynamics in complex networks
• Network Geometry
• Assessing the relevance of node features for network structure
• Navigation of brain networks
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
• Scale-free Networks Well Done
• Spectral entropies as information-theoretic tools for complex network comparison
• Emergent Hyperbolic Network Geometry
• Network Mapping by Replaying Hyperbolic Growth
• Network geometry with flavor: from complexity to quantum geometry
• Hidden geometric correlations in real multiplex networks
• Resilience and rewiring of the passenger airline networks in the United States
• Complex Networks from Classical to Quantum
• Curvature and temperature of complex networks
• Network Cosmology
• Interdisciplinary and physics challenges of Network Theory
• Long-Range Navigation on Complex Networks using Lévy Random Walks
• Ordinary Percolation with Discontinuous Transitions
• Emergent Complex Network Geometry
• The hidden geometry of weighted complex networks
• Network Geometry Inference using Common Neighbors
• Quantum Google in a Complex Network
• Navigable Networks as Nash Equilibria of Navigation Games
• Navigating the massive world of reddit: Using backbone networks to map user interests in social media
• Deciphering the global organization of clustering in real complex networks
• Extended navigability of small world networks: exact results and new insights
• Navigable maps of structural brain networks across species
• Complex Quantum Network Geometries: Evolution and Phase Transitions
• Asymptotic behavior of the Kleinberg model
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Superlinear and sublinear urban scaling in geographical network model of the city
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Network Geometry and Complexity
• Scaling of human behavior during portal browsing
• Community Detection in Complex Networks Using Density-based Clustering Algorithm
• Modeling Structure and Resilience of the Dark Network
• Matching-centrality decomposition and the forecasting of new links in networks
• Does the brain behave like a (complex) network? I. Dynamics
• Exploring Maps with Greedy Navigators
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Multilayer Network Science: from Cells to Societies
• Navigability evaluation of complex networks by greedy routing efficiency
• Mapping from Architecture to Dynamics: A Unified View of Dynamical Processes on Networks
• Complex Quantum Network Manifolds in Dimension $d>2$ are Scale-Free
• Enhancing transport properties in interconnected systems without altering their structure
• Geohyperbolic Routing and Addressing Schemes
• Supersymmetric multiplex networks described by coupled Bose and Fermi statistics
• Navigating ultrasmall worlds in ultrashort time
• The inherent community structure of hyperbolic networks
• On the Hyperbolicity of Large-Scale Networks
• Hidden Variables in Bipartite Networks
• Suppressing traffic-driven epidemic spreading by adaptive routing strategy
• Suppressing traffic-driven epidemic spreading by use of the efficient routing protocol
• Bridging the gap between graphs and networks
• Diffusion geometry of multiplex and interdependent systems
• Competition between global and local online social networks
• The shape of shortest paths in random spatial networks
• Geometric explanation of the rich-club phenomenon in complex networks
• Scale-free networks embedded in fractal space
• Similarity forces and recurrent components in human face-to-face interaction networks
• New Phenomena in Large-Scale Internet Traffic
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• The Dynamics of Knowledge Acquisition via Self-Learning in Complex Networks
• Random hyperbolic graphs in $d+1$ dimensions
• Collective navigation of complex networks: Participatory greedy routing
• Estimating Tipping Points in Feedback-Driven Financial Networks
• An integrative dynamical perspective for graph theory and the study of complex networks
• k-core structure of real multiplex networks
• The specificity and robustness of long-distance connections in weighted, interareal connectomes
• A greedy-navigator approach to navigable city plans
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Routes Obey Hierarchy in Complex Networks
• Sizing the length of complex networks
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Optimal transport on supply-demand networks
• Multi-Temporal Analysis and Scaling Relations of 100,000,000,000 Network Packets
• Complex networks as an emerging property of hierarchical preferential attachment
• On the Hyperbolicity of Small-World and Tree-Like Random Graphs
• Principled Multilayer Network Embedding
• Impact of noise and damage on collective dynamics of scale-free neuronal networks
• Self-organized Emergence of Navigability on Small-World Networks
• Detecting local perturbations of networks in a latent hyperbolic embedding space
• Random Walk with Memory on Complex Networks
• MeMemo: On-device Retrieval Augmentation for Private and Personalized Text Generation
• Zoo Guide to Network Embedding
• Cosmological networks
• Growing homophilic networks are natural navigable small worlds
• A Latent Parameter Node-Centric Model for Spatial Networks
• Protein residue networks from a local search perspective
• Random graphs and real networks with weak geometric coupling
• Discovering universal statistical laws of complex networks
• Comparing local search paths with global search paths on protein residue networks: allosteric communication
• Geometric evolution of complex networks
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• Metric tree-like structures in real-life networks: an empirical study
• Greedy Routing and the Algorithmic Small-World Phenomenom
• Greedy Connectivity of Geographically Embedded Graphs
• Model-free hidden geometry of complex networks
• Greedy routing optimisation in hyperbolic networks
• Strange Attractors in Complex Networks
• Pathlength scaling in graphs with incomplete navigational information
• On the decentralized navigation of multiple packages on transportation networks
• Quantifying navigation complexity in transportation networks
• Geometric randomization of real networks with prescribed degree sequence
• Organic Design of Massively Distributed Systems: A Complex Networks Perspective
• Geometric properties of graph layouts optimized for greedy navigation
• Generalised thresholding of hidden variable network models with scale-free property
• Rapid Bayesian Inference of Global Network Statistics Using Random Walks
• Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach
• Decentralized Routing on Spatial Networks with Stochastic Edge Weights
• Geometric representations of brain networks can predict the surgery outcome in temporal lobe epilepsy
• Expansion and Search in Networks
• Community Detection in the Hyperbolic Space
• Degree and connectivity of the Internet's scale-free topology
• Topology and Geometry of the Third-Party Domains Ecosystem: Measurement and Applications
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Systematic comparison of graph embedding methods in practical tasks
• The Network of Mexican Cities
• Searchability of central nodes in networks
• A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity
• High Performance Algorithms for Quantum Gravity and Cosmology
• Deductive Way of Reasoning about the Internet AS Level Topology
• Symmetry-driven embedding of networks in hyperbolic space
• High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility
• A stylised view on structural and functional connectivity in dynamical processes in networks
• On the hyperbolicity of random graphs
• Hidden space reconstruction inspires link prediction in complex networks
• Siamese networks for Poincaré embeddings and the reconstruction of evolutionary trees
• Latent geometry emerging from network-driven processes
• Mapping bipartite networks into multidimensional hyperbolic spaces
• Hyperbolic embedding of multilayer networks
• Multiplexity amplifies geometry in networks