Testing Community Structures for Hypergraphs

Abstract

Many complex networks in real world can be formulated as hypergraphs where community detection has been widely used. However, the fundamental question of whether communities exist or not in an observed hypergraph still remains unresolved. The aim of the present paper is to tackle this important problem. Specifically, we study when a hypergraph with community structure can be successfully distinguished from its Erdös-Renyi counterpart, and propose concrete test statistics based on hypergraph cycles when the models are distinguishable. Our contributions are summarized as follows. For uniform hypergraphs, we show that successful testing is always impossible when average degree tends to zero, might be possible when average degree is bounded, and is possible when average degree is growing. We obtain asymptotic distributions of the proposed test statistics and analyze their power. Our results for growing degree case are further extended to nonuniform hypergraphs in which a new test involving both edge and hyperedge information is proposed. The novel aspect of our new test is that it is provably more powerful than the classic test involving only edge information. Simulation and real data analysis support our theoretical findings. The proofs rely on Janson's contiguity theory (\cite{J95}) and a high-moments driven asymptotic normality result by Gao and Wormald (\cite{GWALD}).

A revised version

References in corpus (11)

• Stochastic blockmodels and community structure in networks
• Random hypergraphs and their applications
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Testing for Global Network Structure Using Small Subgraph Statistics
• Optimal hypothesis testing for stochastic block models with growing degrees
• Non-Reconstructability in the Stochastic Block Model
• Networks of Collaborations: Hypergraph Modeling and Visualisation
• Community Detection in Degree-Corrected Block Models

Cited by in corpus (3)

• Community Detection in General Hypergraph via Graph Embedding
• Heterogeneous Dense Subhypergraph Detection
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition