Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space

Abstract

Complex network topologies and hyperbolic geometry seem specularly connected, and one of the most fascinating and challenging problems of recent complex network theory is to map a given network to its hyperbolic space. The Popularity Similarity Optimization (PSO) model represents - at the moment - the climax of this theory. It suggests that the trade-off between node popularity and similarity is a mechanism to explain how complex network topologies emerge - as discrete samples - from the continuous world of hyperbolic geometry. The hyperbolic space seems appropriate to represent real complex networks. In fact, it preserves many of their fundamental topological properties, and can be exploited for real applications such as, among others, link prediction and community detection. Here, we observe for the first time that a topological-based machine learning class of algorithms - for nonlinear unsupervised dimensionality reduction - can directly approximate the network's node angular coordinates of the hyperbolic model into a two-dimensional space, according to a similar topological organization that we named angular coalescence. On the basis of this phenomenon, we propose a new class of algorithms that offers fast and accurate coalescent embedding of networks in the hyperbolic space even for graphs with thousands of nodes.

References in corpus (31)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Power-law distributions in empirical data
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Comparing community structure identification
• Hyperbolic Geometry of Complex Networks
• Community Structure in Jazz
• Popularity versus Similarity in Growing Networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Self-similarity of complex networks and hidden metric spaces
• Direct mass measurements beyond the proton drip-line
• Emergent Hyperbolic Network Geometry
• Network Mapping by Replaying Hyperbolic Growth
• Complex Networks on Hyperbolic Surfaces
• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Interdisciplinary and physics challenges of Network Theory
• Emergent Complex Network Geometry
• Emergence of Soft Communities from Geometric Preferential Attachment
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Network Geometry Inference using Common Neighbors
• Clustering implies geometry in networks
• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• Hyperbolicity Measures "Democracy" in Real-World Networks
• Complex Quantum Network Manifolds in Dimension $d>2$ are Scale-Free
• On the Hyperbolicity of Large-Scale Networks
• Coalescent embedding in the hyperbolic space unsupervisedly discloses the hidden geometry of the brain
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction

Cited by in corpus (57)

• Network Geometry
• Progresses and Challenges in Link Prediction
• Geom-GCN: Geometric Graph Convolutional Networks
• Modular gateway-ness connectivity and structural core organization in maritime network science
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Synchronization in Network Geometries with Finite Spectral Dimension
• Principled approach to the selection of the embedding dimension of networks
• Navigable maps of structural brain networks across species
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Link prediction with hyperbolic geometry
• Detecting the ultra low dimensionality of real networks
• The EntOptLayout Cytoscape plug-in for the efficient visualization of major protein complexes in protein-protein interaction and signalling networks
• Navigability evaluation of complex networks by greedy routing efficiency
• Reconstructing networks
• The inherent community structure of hyperbolic networks
• WGCN: Graph Convolutional Networks with Weighted Structural Features
• Extracting the main trend in a dataset: the Sequencer algorithm
• Network Alignment
• Percolation and the effective structure of complex networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Random hyperbolic graphs in $d+1$ dimensions
• Learning epidemic threshold in complex networks by Convolutional Neural Network
• 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
• Sizing the length of complex networks
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Detecting local perturbations of networks in a latent hyperbolic embedding space
• Zoo Guide to Network Embedding
• Fundamental dynamics of popularity-similarity trajectories in real networks
• Explaining the emergence of complex networks through log-normal fitness in a Euclidean node similarity space
• Random graphs and real networks with weak geometric coupling
• Topological estimation of the latent geometry of a complex network
• Iterative embedding and reweighting of complex networks reveals community structure
• Hyperbolic Mapping of Human Proximity Networks
• Greedy routing optimisation in hyperbolic networks
• Model-free hidden geometry of complex networks
• Hyperbolic embedding of brain networks detects regions disrupted by neurodegeneration in Alzheimer's disease
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Multiscale modeling of brain network organization
• 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
• Deep Learning Super-Diffusion in Multiplex Networks
• Systematic comparison of graph embedding methods in practical tasks
• Nonlinear Markov Clustering by Minimum Curvilinear Sparse Similarity
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Measuring group-separability in geometrical space for evaluation of pattern recognition and embedding algorithms
• Hyperbolic embedding of brain networks as a tool for epileptic seizures forecasting
• Lorentzian Graph Convolutional Networks
• Symmetry-driven embedding of networks in hyperbolic space
• HEAT: Hyperbolic Embedding of Attributed Networks
• Potential energy of complex networks: a novel perspective
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk
• Multi-modal Entity Alignment in Hyperbolic Space
• Hyperbolic embedding of multilayer networks
• Adaptive Latent Space Tuning for Non-Stationary Distributions