Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
arXiv:2312.00708 · doi:10.1088/1742-5468/ad343b
Abstract
Hypergraphs are widely adopted tools to examine systems with higher-order interactions. Despite recent advancements in methods for community detection in these systems, we still lack a theoretical analysis of their detectability limits. Here, we derive closed-form bounds for community detection in hypergraphs. Using a Message-Passing formulation, we demonstrate that detectability depends on hypergraphs' structural properties, such as the distribution of hyperedge sizes or their assortativity. Our formulation enables a characterization of the entropy of a hypergraph in relation to that of its clique expansion, showing that community detection is enhanced when hyperedges highly overlap on pairs of nodes. We develop an efficient Message-Passing algorithm to learn communities and model parameters on large systems. Additionally, we devise an exact sampling routine to generate synthetic data from our probabilistic model. With these methods, we numerically investigate the boundaries of community detection in synthetic datasets, and extract communities from real systems. Our results extend the understanding of the limits of community detection in hypergraphs and introduce flexible mathematical tools to study systems with higher-order interactions.
30 pages, 8 figures, 1 table
References in corpus (32)
- Community structure in social and biological networks
- Community detection in graphs
- The structure of scientific collaboration networks
- Weak pairwise correlations imply strongly correlated network states in a neural population
- Networks beyond pairwise interactions: structure and dynamics
- The physics of higher-order interactions in complex systems
- The Bethe lattice spin glass revisited
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
- Clique topology reveals intrinsic geometric structure in neural correlations
- Phase transition in the detection of modules in sparse networks
- Structure and inference in annotated networks
- Network information and connected correlations
- Reconstruction on trees and spin glass transition
- Message passing on networks with loops
- Inference of hyperedges and overlapping communities in hypergraphs
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Hypergraph reconstruction from network data
- Enhanced detectability of community structure in multilayer networks through layer aggregation
- Community Detection in Large Hypergraphs
- Community detection with node attributes in multilayer networks
- Resilience of Networks Formed of Interdependent Modular Networks
- Belief propagation for networks with loops
- On the sufficiency of pairwise interactions in maximum entropy models of biological networks
- The simpliciality of higher-order networks
- Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
- Community detection in the sparse hypergraph stochastic block model
- A framework to generate hypergraphs with community structure
- Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
- Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
- Weak Recovery Threshold for the Hypergraph Stochastic Block Model
- Statistical and computational thresholds for the planted -densest sub-hypergraph problem