Extraction of Statistically Significant Communities in Undirected Networks

• Activity Number: 254
• Type: Contributed
• Date/Time: Monday, August 5, 2013 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): James Wilson*+ and Simi Wang and Andrew Nobel and Peter Mucha and Shankar Bhamidi
• Companies: UNC Chapel Hill and Department of Mathematics, UNC Chapel Hill and UNC-CH and Department of Mathematics, UNC Chapel Hill and Department of Statistics and Operations Research, UNC Chapel Hill
• Keywords: Networks ; Multiple Hypothesis testing ; False Discovery rate ; Clustering ; Community Extraction ; Community Detection

Abstract

A common problem in network science involves the clustering of vertices in a network into one or more communities. This problem, known as community detection, has lead to the construction of a variety of algorithms aimed at finding the best collection of communities that cover the network. In assuming that every vertex belongs to one or more communities, typical detection methods do not distinguish statistically significant communities from insignificant ones. We propose a simple binomial model to measure the local significance of connection among vertices, providing a natural framework for assessing the significance of detected communities. Based on this parametric model, we develop an iterative procedure that extracts significant communities through the use of the Benjamini Hochberg multiple hypothesis testing procedure. We show that our algorithm - ESSC - outperforms current methods in an extraction setting, and is competetive with popular detection methods in non-overlapping and overlapping benchmark studies. We apply ESSC to several real world networks and show that ESSC reveals characteristics of these data sets beyond the capabilities of detection methods alone.