Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
arXiv:2207.07633 · doi:10.1038/s42005-023-01143-x
Abstract
The arrangement of network nodes in hyperbolic spaces has become a widely studied problem, motivated by numerous results suggesting the existence of hidden metric spaces behind the structure of complex networks. Although several methods have already been developed for the hyperbolic embedding of undirected networks, approaches able to deal with directed networks are still in their infancy. Here, we propose a framework based on the dimension reduction of proximity matrices reflecting the network topology, coupled with a general conversion method transforming Euclidean node coordinates into hyperbolic ones even for directed networks. While proposing a new measure of proximity, we also incorporate an earlier Euclidean embedding method in our pipeline, demonstrating the widespread applicability of our Euclidean-hyperbolic conversion. Besides, we introduce a dimension reduction technique that maps the nodes directly into the hyperbolic space with the aim of reproducing a distance matrix measured on the given (un)directed network. According to mapping accuracy, graph reconstruction performance and greedy routing score, our methods are capable of producing high-quality embeddings for several real networks.
References in corpus (34)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Community detection in graphs
- Hierarchical structure and the prediction of missing links in networks
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Community detection in networks: A user guide
- Predicting Missing Links via Local Information
- 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
- Evaluating Link Prediction Methods
- Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
- On community structure in complex networks: challenges and opportunities
- Network Mapping by Replaying Hyperbolic Growth
- Directed network modules
- Interdisciplinary and physics challenges of Network Theory
- Emergence of Soft Communities from Geometric Preferential Attachment
- A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
- Clustering implies geometry in networks
- Navigable Networks as Nash Equilibria of Navigation Games
- Euclidean versus hyperbolic congestion in idealized versus experimental networks
- Link prediction with hyperbolic geometry
- Soft communities in similarity space
- Navigability evaluation of complex networks by greedy routing efficiency
- The Evolution of Wikipedia's Norm Network
- The inherent community structure of hyperbolic networks
- Hierarchical networks of scientific journals
- Detecting hyperbolic geometry in networks: why triangles are not enough
- Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
- Optimisation of the coalescent hyperbolic embedding of complex networks
- Systematic comparison of graph embedding methods in practical tasks
- Geometrical congruence and efficient greedy navigability of complex networks