Community detection in hypergraphs through hyperedge percolation

Abstract

Complex networks often exhibit community structure, with communities corresponding to denser subgraphs in which nodes are closely linked. When modelling systems where interactions extend beyond node pairs to arbitrary numbers of nodes, hypergraphs become necessary, creating a need for specialised community detection methods. Here, we adapt the classical $k$-clique percolation method to hypergraphs, constructing communities from hyperedges containing at least $k$ nodes, defining hyperedge adjacency similarly to clique adjacency. Although the analogy between the proposed hyperedge percolation method and the classical clique percolation algorithm is evident, we show that communities obtained directly from the hyperedges can differ from those identified via clique percolation on the pairwise projection of the hypergraph. We also propose an alternative way for merging hyperedges into communities, where instead of imposing a lower bound on hyperedge cardinality, we restrict the maximum size of the considered hyperedges. This alternative algorithm better suits hypergraphs where larger hyperedges realise weaker linkages between the nodes. After comparing the suggested two approaches on simple synthetic hypergraphs designed to highlight their distinctions, we test them on hypergraphs generated by a newly proposed geometric process on the hyperbolic plane, as well as on some real-world examples.

20 pages, 8 figures. Added references and GitHub URL, typos corrected

References in corpus (38)

• Statistical mechanics of complex networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Temporal Networks
• Community detection in networks: A user guide
• Networks beyond pairwise interactions: structure and dynamics
• Hyperbolic Geometry of Complex Networks
• Popularity versus Similarity in Growing Networks
• Clique percolation in random networks
• Simplicial Closure and higher-order link prediction
• What are higher-order networks?
• Network Geometry
• On community structure in complex networks: challenges and opportunities
• Emergent Hyperbolic Network Geometry
• Higher-order motif analysis in hypergraphs
• Simplicial complexes and complex systems
• Element-centric clustering comparison unifies overlaps and hierarchy
• Inference of hyperedges and overlapping communities in hypergraphs
• Emergence of Soft Communities from Geometric Preferential Attachment
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• The hidden geometry of weighted complex networks
• Clustering via Hypergraph Modularity
• Community Detection in Large Hypergraphs
• Mapping flows on hypergraphs
• Network Geometry and Complexity
• Exponential Random Simplicial Complexes
• Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs
• Hypergraphx: a library for higher-order network analysis
• Small worlds and clustering in spatial networks
• Soft communities in similarity space
• The simpliciality of higher-order networks
• Spectral Detection on Sparse Hypergraphs
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• The inherent community structure of hyperbolic networks
• Hyperlink communities in higher-order networks
• Random Simplicial Complexes: Models and Phenomena
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Maximally modular structure of growing hyperbolic networks