Network Mapping by Replaying Hyperbolic Growth

Abstract

Recent years have shown a promising progress in understanding geometric underpinnings behind the structure, function, and dynamics of many complex networks in nature and society. However these promises cannot be readily fulfilled and lead to important practical applications, without a simple, reliable, and fast network mapping method to infer the latent geometric coordinates of nodes in a real network. Here we present HyperMap, a simple method to map a given real network to its hyperbolic space. The method utilizes a recent geometric theory of complex networks modeled as random geometric graphs in hyperbolic spaces. The method replays the network's geometric growth, estimating at each time step the hyperbolic coordinates of new nodes in a growing network by maximizing the likelihood of the network snapshot in the model. We apply HyperMap to the AS Internet, and find that: 1) the method produces meaningful results, identifying soft communities of ASs belonging to the same geographic region; 2) the method has a remarkable predictive power: using the resulting map, we can predict missing links in the Internet with high precision, outperforming popular existing methods; and 3) the resulting map is highly navigable, meaning that a vast majority of greedy geometric routing paths are successful and low-stretch. Even though the method is not without limitations, and is open for improvement, it occupies a unique attractive position in the space of trade-offs between simplicity, accuracy, and computational complexity.

14 pages, to appear in ToN

References in corpus (8)

• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Hyperbolic Geometry of Complex Networks
• Popularity versus Similarity in Growing Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Self-similarity of complex networks and hidden metric spaces
• AS Relationships: Inference and Validation

Cited by in corpus (53)

• Network Geometry
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Hidden geometric correlations in real multiplex networks
• Progresses and Challenges in Link Prediction
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Network Geometry Inference using Common Neighbors
• An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN
• Navigable Networks as Nash Equilibria of Navigation Games
• Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
• Metric clusters in evolutionary games on scale-free networks
• Hyperbolic Graph Generator
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Link prediction with hyperbolic geometry
• Effective epidemic containment strategy in hypergraphs
• Navigability evaluation of complex networks by greedy routing efficiency
• Latent geometry of bipartite networks
• Geohyperbolic Routing and Addressing Schemes
• The inherent community structure of hyperbolic networks
• HyperKG: Hyperbolic Knowledge Graph Embeddings for Knowledge Base Completion
• Collective navigation of complex networks: Participatory greedy routing
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Random hyperbolic graphs in $d+1$ dimensions
• Link persistence and conditional distances in multiplex networks
• Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Dynamic Hidden-Variable Network Models
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Detecting local perturbations of networks in a latent hyperbolic embedding space
• Maximally modular structure of growing hyperbolic networks
• On the diameter of hyperbolic random graphs
• Fundamental dynamics of popularity-similarity trajectories in real networks
• Random graphs and real networks with weak geometric coupling
• Geometric evolution of complex networks
• Greedy routing optimisation in hyperbolic networks
• Greedy Routing and the Algorithmic Small-World Phenomenom
• Hyperbolic Mapping of Human Proximity Networks
• Hyperbolic embedding of brain networks detects regions disrupted by neurodegeneration in Alzheimer's disease
• Social Centralization and Semantic Collapse: Hyperbolic Embeddings of Networks and Text
• Social Connection Induces Cultural Contraction: Evidence from Hyperbolic Embeddings of Social and Semantic Networks
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Topology and Geometry of the Third-Party Domains Ecosystem: Measurement and Applications
• Geometric representations of brain networks can predict the surgery outcome in temporal lobe epilepsy
• Systematic comparison of graph embedding methods in practical tasks
• HEAT: Hyperbolic Embedding of Attributed Networks
• Dynamics of cold random hyperbolic graphs with link persistence
• Hyperbolic embedding of brain networks as a tool for epileptic seizures forecasting
• Symmetry-driven embedding of networks in hyperbolic space
• Localized geometry detection in scale-free random graphs
• Data Breaches in Healthcare Security Systems
• Hidden multiscale organization and robustness of real multiplex networks
• Hyperbolic embedding of multilayer networks
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk