Network Geometry Inference using Common Neighbors

Abstract

We introduce and explore a new method for inferring hidden geometric coordinates of nodes in complex networks based on the number of common neighbors between the nodes. We compare this approach to the HyperMap method, which is based only on the connections (and disconnections) between the nodes, i.e., on the links that the nodes have (or do not have). We find that for high degree nodes the common-neighbors approach yields a more accurate inference than the link-based method, unless heuristic periodic adjustments (or "correction steps") are used in the latter. The common-neighbors approach is computationally intensive, requiring $O(t^4)$ running time to map a network of $t$ nodes, versus $O(t^3)$ in the link-based method. But we also develop a hybrid method with $O(t^3)$ running time, which combines the common-neighbors and link-based approaches, and explore a heuristic that reduces its running time further to $O(t^2)$, without significant reduction in the mapping accuracy. We apply this method to the Autonomous Systems (AS) Internet, and reveal how soft communities of ASes evolve over time in the similarity space. We further demonstrate the method's predictive power by forecasting future links between ASes. Taken altogether, our results advance our understanding of how to efficiently and accurately map real networks to their latent geometric spaces, which is an important necessary step towards understanding the laws that govern the dynamics of nodes in these spaces, and the fine-grained dynamics of network connections.

References in corpus (5)

• Hyperbolic Geometry of Complex Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• AS Relationships: Inference and Validation
• Emergence of Soft Communities from Geometric Preferential Attachment

Cited by in corpus (37)

• 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
• Multiscale unfolding of real networks by geometric renormalization
• The hidden geometry of weighted complex networks
• Geometric renormalization unravels self-similarity of the multiscale human connectome
• An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN
• Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
• Metric clusters in evolutionary games on scale-free networks
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Link prediction with hyperbolic geometry
• Navigability evaluation of complex networks by greedy routing efficiency
• Latent geometry of bipartite networks
• Reconstructing networks
• HyperKG: Hyperbolic Knowledge Graph Embeddings for Knowledge Base Completion
• Percolation and the effective structure of complex networks
• Structural measures of similarity and complementarity in complex networks
• Random hyperbolic graphs in $d+1$ dimensions
• Collective navigation of complex networks: Participatory greedy routing
• Link persistence and conditional distances in multiplex networks
• k-core structure of real multiplex networks
• Fundamental dynamics of popularity-similarity trajectories in real networks
• Duality between predictability and reconstructability in complex systems
• Random graphs and real networks with weak geometric coupling
• Geometric evolution of complex networks
• Model-free hidden geometry of complex networks
• Hyperbolic Mapping of Human Proximity Networks
• Large-Margin Classification in Hyperbolic Space
• Hyperbolic triangulations and discrete random graphs
• Topology and Geometry of the Third-Party Domains Ecosystem: Measurement and Applications
• Systematic comparison of graph embedding methods in practical tasks
• Dynamics of cold random hyperbolic graphs with link persistence
• Symmetry-driven embedding of networks in hyperbolic space
• Hidden multiscale organization and robustness of real multiplex networks
• Edge sampling using network local information
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk
• Dynamic Distances in Hyperbolic Graphs