TESTING COMMUNITY STRUCTURE FOR HYPERGRAPHS

Mingao Yuan, Ruiqi Liu, Yang Feng, Zuofeng Shang

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Many complex networks in the 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 remains unclear. This work aims to tackle this important problem. Specifically, we systematically study when a hypergraph with community structure can be successfully distinguished from its Erdos-Rényi counterpart, and propose concrete test statistics when the models are distinguishable. The main contribution of this paper is threefold. First, we discover a phase transition in the hyperedge probability for distinguishability. Second, in the bounded-degree regime, we derive a sharp signal-to-noise ratio (SNR) threshold for distinguishability in the special two-community 3- uniform hypergraphs, and derive nearly tight SNR thresholds in the general two-community m-uniform hypergraphs. Third, in the dense regime, we propose a computationally feasible test based on sub-hypergraph counts, obtain its asymptotic distribution, and analyze its power. Our results are further extended to nonuniform hypergraphs in which a new test involving both edge and hyperedge information is proposed. The proofs rely on Janson's contiguity theory (Combin. Probab. Comput. 4 (1995) 369-405), a high-moments driven asymptotic normality result by Gao andWormald (Probab. Theory Related Fields 130 (2004) 368-376), and a truncation technique for analyzing the likelihood ratio.

Original languageEnglish (US)
Pages (from-to)147-169
Number of pages23
JournalAnnals of Statistics
Volume50
Issue number1
DOIs
StatePublished - Feb 2022

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Contiguity
  • Hypergraph
  • Hypothesis testing
  • L-cycle
  • Stochastic block model

Fingerprint

Dive into the research topics of 'TESTING COMMUNITY STRUCTURE FOR HYPERGRAPHS'. Together they form a unique fingerprint.

Cite this