Hypothesis Testing for Automated Community Detection in Networks
Community detection in networks is a key exploratory tool with applications in a diverse set of areas, ranging from finding communities in social and biological networks to identifying link farms in the World Wide Web. The problem of finding communities or clusters in a network has received much attention from statistics, physics and computer science. However, most clustering algorithms assume knowledge of the number of clusters k. In this paper we propose to automatically determine k in a graph generated from a Stochastic Blockmodel. Our main contribution is twofold; first, we theoretically establish the limiting distribution of the principal eigenvalue of the suitably centered and scaled adjacency matrix, and use that distribution for our hypothesis test. Secondly, we use this test to design a recursive bipartitioning algorithm. Using quantifiable classification tasks on real world networks with ground truth, we show that our algorithm outperforms existing probabilistic models for learning overlapping clusters, and on unlabeled networks, we show that we uncover nested community structure.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity DetectionTwo-sample testingSimilar Papers 제목 키워드 기반
Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, comm…
Community DetectionGraphon EstimationTwo-sample testingAutoSciDACT: Automated Scientific Discovery through Contrastive Embedding and Hypothesis Testing
Novelty detection in large scientific datasets faces two key challenges: the noisy and high-dimensional nature of experimental data, and the necessity of making statistically robust statements about any observed outliers…
Dimensionality ReductionData AugmentationAnomaly DetectionBayesian Hypothesis Testing for Block Sparse Signal Recovery
This letter presents a novel Block Bayesian Hypothesis Testing Algorithm (Block-BHTA) for reconstructing block sparse signals with unknown block structures. The Block-BHTA comprises the detection and recovery of the supp…
Two-sample testingIs it easier to count communities than find them?
Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computation…
Hypothesis Testing for Equality of Latent Positions in Random Graphs
We consider the hypothesis testing problem that two vertices $i$ and $j$ of a generalized random dot product graph have the same latent positions, possibly up to scaling. Special cases of this hypothesis test include tes…
Model SelectionStochastic Block Model