A testing based extraction algorithm for identifying significant communities in networks
From MaRDI portal
Publication:484064
DOI10.1214/14-AOAS760zbMATH Open1304.05141arXiv1308.0777WikidataQ103589709 ScholiaQ103589709MaRDI QIDQ484064FDOQ484064
Andrew B. Nobel, James D. Wilson, Shankar Bhamidi, Peter J. Mucha, Simi Wang
Publication date: 17 December 2014
Published in: The Annals of Applied Statistics (Search for Journal in Brave)
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 -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.
Full work available at URL: https://arxiv.org/abs/1308.0777
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph algorithms (graph-theoretic aspects) (05C85) Paired and multiple comparisons; multiple testing (62J15) Social networks; opinion dynamics (91D30)
Cites Work
- A decision-theoretic generalization of on-line learning and an application to boosting
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- The elements of statistical learning. Data mining, inference, and prediction
- A nonparametric view of network models and Newman–Girvan and other modularities
- Estimation and Prediction for Stochastic Blockstructures
- Pseudo-likelihood methods for community detection in large sparse networks
- Title not available (Why is that?)
- A Survey of Statistical Network Models
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Consistency of community detection in networks under degree-corrected stochastic block models
- Spectral redemption in clustering sparse networks
- Mixed membership stochastic blockmodels
- Emergence of Scaling in Random Networks
- Community structure in social and biological networks
- Latent Space Approaches to Social Network Analysis
- Title not available (Why is that?)
- A critical point for random graphs with a given degree sequence
- Tabu Search—Part I
- A new approach to the maximum-flow problem
- Overlapping community detection in networks
- The asymptotic number of labeled graphs with given degree sequences
- Information, Physics, and Computation
- Communities in Networks
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Title not available (Why is that?)
- A testing based extraction algorithm for identifying significant communities in networks
- Finding large average submatrices in high dimensional data
Cited In (11)
- Computing exact \(p\)-values for community detection
- Fusing data depth with complex networks: community detection with prior information
- A testing based approach to the discovery of differentially correlated variable sets
- Title not available (Why is that?)
- Validation of community robustness
- Compressive Sensing for Cut Improvement and Local Clustering
- PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
- Title not available (Why is that?)
- A testing based extraction algorithm for identifying significant communities in networks
- A Hypothesis Testing Framework for Modularity Based Network Community Detection
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
Uses Software
This page was built for publication: A testing based extraction algorithm for identifying significant communities in networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484064)
