Hypergraph reconstruction from network data

Abstract

Networks can describe the structure of a wide variety of complex systems by specifying which pairs of entities in the system are connected. While such pairwise representations are flexible, they are not necessarily appropriate when the fundamental interactions involve more than two entities at the same time. Pairwise representations nonetheless remain ubiquitous, because higher-order interactions are often not recorded explicitly in network data. Here, we introduce a Bayesian approach to reconstruct latent higher-order interactions from ordinary pairwise network data. Our method is based on the principle of parsimony and only includes higher-order structures when there is sufficient statistical evidence for them. We demonstrate its applicability to a wide range of datasets, both synthetic and empirical.

arXiv comment13 pages, 7 figures. Code is available at https://graph-tool.skewed.de/

References in corpus (20)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Networks beyond pairwise interactions: structure and dynamics
• Self-similar community structure in organisations
• Identity and Search in Social Networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Properties of highly clustered networks
• Topological strata of weighted complex networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Networks of strong ties
• Construction of and efficient sampling from the simplicial configuration model
• Structure of large random hypergraphs
• Bayesian inference of network structure from unreliable data
• Preferential attachment of communities: the same principle, but a higher level
• Covering Problems and Core Percolations on Hypergraphs
• Trust transitivity in social networks
• Complex networks as an emerging property of hierarchical preferential attachment
• Latent Poisson models for networks with heterogeneous density

Cited by in corpus (29)

• The physics of higher-order interactions in complex systems
• Dynamics on higher-order networks: A review
• Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
• Higher-order motif analysis in hypergraphs
• Inference of hyperedges and overlapping communities in hypergraphs
• Unveiling the higher-order organization of multivariate time series
• The temporal dynamics of group interactions in higher-order social networks
• Community Detection in Large Hypergraphs
• Expectation-Maximizing Network Reconstruction and MostApplicable Network Types Based on Binary Time Series Data
• Disentangling homophily, community structure and triadic closure in networks
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• Hypergraph reconstruction from dynamics
• Contagion dynamics on hypergraphs with nested hyperedges
• Social contagion on higher-order structures
• Hyperlink communities in higher-order networks
• Collective dynamics on higher-order networks
• A framework to generate hypergraphs with community structure
• Multiplex measures for higher-order networks
• Hypergraph reconstruction from noisy pairwise observations
• Persistent Homology of Fractional Gaussian Noise
• Compressing network populations with modal networks reveals structural diversity
• Filtering higher-order datasets
• Mining higher-order triadic interactions
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Higher-order dissimilarity measures for hypergraph comparison
• Higher-order shortest paths in hypergraphs
• Symmetry-driven embedding of networks in hyperbolic space
• Beyond Trivial Edges: A Fractional Approach to Cohesive Subgraph Detection in Hypergraphs
• Reducibility of higher-order to pairwise interactions: Social impact models on hypergraphs