Symmetry-driven embedding of networks in hyperbolic space

Abstract

Hyperbolic models are known to produce networks with properties observed empirically in most network datasets, including heavy-tailed degree distribution, high clustering, and hierarchical structures. As a result, several embeddings algorithms have been proposed to invert these models and assign hyperbolic coordinates to network data. Current algorithms for finding these coordinates, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model. We show that the samples are consistent with current algorithms while providing added credible intervals for the coordinates and all network properties. We also show that some networks admit two or more plausible embeddings, a feature that an optimization algorithm can easily overlook.

References in corpus (35)

• Cooperative Game Theory Approaches for Network Partitioning
• Variational Inference: A Review for Statisticians
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Rank-normalization, folding, and localization: An improved $\hat{R}$ for assessing convergence of MCMC
• Self-similarity of complex networks
• Hyperbolic Geometry of Complex Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Self-similarity of complex networks and hidden metric spaces
• Network structure from rich but noisy data
• Network Geometry
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• Network Mapping by Replaying Hyperbolic Growth
• Bayesian stochastic blockmodeling
• Multiscale unfolding of real networks by geometric renormalization
• Hypergraph reconstruction from network data
• Emergence of Soft Communities from Geometric Preferential Attachment
• The hidden geometry of weighted complex networks
• Geometric renormalization unravels self-similarity of the multiscale human connectome
• Network Geometry Inference using Common Neighbors
• Clustering implies geometry in networks
• Bayesian inference of network structure from unreliable data
• Clustering Drives Assortativity and Community Structure in Ensembles of Networks
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Link prediction with hyperbolic geometry
• Small worlds and clustering in spatial networks
• Soft communities in similarity space
• Embedding Graphs in Lorentzian Spacetime
• The inherent community structure of hyperbolic networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Hypergraph reconstruction from noisy pairwise observations
• Maximally modular structure of growing hyperbolic networks
• Zoo Guide to Network Embedding
• Exact and rapid linear clustering of networks with dynamic programming