A testing based extraction algorithm for identifying significant communities in networks

Abstract

A common and important problem arising in the study of networks is how to divide the vertices of a given network into one or more groups, called communities, in such a way that vertices of the same community are more interconnected than vertices belonging to different ones. We propose and investigate a testing based community detection procedure called Extraction of Statistically Significant Communities (ESSC). The ESSC procedure is based on $p$-values for the strength of connection between a single vertex and a set of vertices under a reference distribution derived from a conditional configuration network model. The procedure automatically selects both the number of communities in the network and their size. Moreover, ESSC can handle overlapping communities and, unlike the majority of existing methods, identifies "background" vertices that do not belong to a well-defined community. The method has only one parameter, which controls the stringency of the hypothesis tests. We investigate the performance and potential use of ESSC and compare it with a number of existing methods, through a validation study using four real network data sets. In addition, we carry out a simulation study to assess the effectiveness of ESSC in networks with various types of community structure, including networks with overlapping communities and those with background vertices. These results suggest that ESSC is an effective exploratory tool for the discovery of relevant community structure in complex network systems. Data and software are available at \urlhttp://www.unc.edu/~jameswd/research.html.

Published in at http://dx.doi.org/10.1214/14-AOAS760 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (34)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Maps of random walks on complex networks reveal community structure
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Dynamic reconfiguration of human brain networks during learning
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The map equation
• Mixed membership stochastic blockmodels
• Social Structure of Facebook Networks
• Spectral redemption: clustering sparse networks
• Mapping change in large networks
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Geographic constraints on social network groups
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• The dynamical strength of social ties in information spreading
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Assessing the relevance of node features for network structure
• Community extraction for social networks
• Finding large average submatrices in high dimensional data
• Network histograms and universality of blockmodel approximation
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• Empirical Comparison of Algorithms for Network Community Detection
• Benchmarking community detection methods on social media data

Cited by in corpus (13)

• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Social significance of community structure: Statistical view
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• Pairwise Covariates-adjusted Block Model for Community Detection
• Detecting Statistically Significant Communities
• Intertemporal Community Detection in Human Mobility Networks
• Network inference and community detection, based on covariance matrices, correlations and test statistics from arbitrary distributions
• Community Detection in Weighted Multilayer Networks with Ambient Noise
• Compressive Sensing for cut improvement and local clustering
• Latent Association Mining in Binary Data
• Correlation-Based Community Detection
• Binomial Tails for Community Analysis