Community Detection in Large Hypergraphs

Abstract

Hypergraphs, describing networks where interactions take place among any number of units, are a natural tool to model many real-world social and biological systems. In this work we propose a principled framework to model the organization of higher-order data. Our approach recovers community structure with accuracy exceeding that of currently available state-of-the-art algorithms, as tested in synthetic benchmarks with both hard and overlapping ground-truth partitions. Our model is flexible and allows capturing both assortative and disassortative community structures. Moreover, our method scales orders of magnitude faster than competing algorithms, making it suitable for the analysis of very large hypergraphs, containing millions of nodes and interactions among thousands of nodes. Our work constitutes a practical and general tool for hypergraph analysis, broadening our understanding of the organization of real-world higher-order systems.

References in corpus (10)

• The physics of higher-order interactions in complex systems
• Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
• Random walks on hypergraphs
• Inference of hyperedges and overlapping communities in hypergraphs
• Unveiling the higher-order organization of multivariate time series
• Explosive cooperation in social dilemmas on higher-order networks
• Hypergraphx: a library for higher-order network analysis
• Exact and sampling methods for mining higher-order motifs in large hypergraphs
• A framework to generate hypergraphs with community structure
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons

Cited by in corpus (14)

• The simpliciality of higher-order networks
• Structure and inference in hypergraphs with node attributes
• Hyperlink communities in higher-order networks
• A framework to generate hypergraphs with community structure
• Collective dynamics on higher-order networks
• Multiplex measures for higher-order networks
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Attributed Hypergraph Generation with Realistic Interplay Between Structure and Attributes
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Community detection in hypergraphs through hyperedge percolation
• Finding Influential Cores via Normalized Ricci Flows in Directed and Undirected Hypergraphs with Applications
• Higher-order shortest paths in hypergraphs
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• Sampling nodes and hyperedges via random walks on large hypergraphs