Title: Testing community structure for hypergraphs
Authors: Yang Feng - NYU (United States) [presenting]
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. The aim is to tackle this important problem. Specifically, we systematically study when a hypergraph with community structure can be successfully distinguished from its Erdos-Renyi counterpart, and propose concrete test statistics when the models are distinguishable. The main contribution 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-degree regime, we propose a computationally feasible test based on sub-hypergraph counts and obtain its asymptotic distribution and analyze its power. The results are further extended to non-uniform hypergraphs in which a new test involving both edge and hyperedge information is proposed. The proofs rely on Jansons contiguity theory, a high-moments-driven asymptotic normality result, and a truncation technique for analyzing the likelihood ratio.