Pairwise Covariates-adjusted Block Model for Community Detection

Abstract

One of the most fundamental problems in network study is community detection. The stochastic block model (SBM) is a widely used model, for which various estimation methods have been developed with their community detection consistency results unveiled. However, the SBM is restricted by the strong assumption that all nodes in the same community are stochastically equivalent, which may not be suitable for practical applications. We introduce a pairwise covariates-adjusted stochastic block model (PCABM), a generalization of SBM that incorporates pairwise covariate information. We study the maximum likelihood estimates of the coefficients for the covariates as well as the community assignments. It is shown that both the coefficient estimates of the covariates and the community assignments are consistent under suitable sparsity conditions. Spectral clustering with adjustment (SCWA) is introduced to efficiently solve PCABM. Under certain conditions, we derive the error bound of community detection under SCWA and show that it is community detection consistent. In addition, we investigate model selection in terms of the number of communities and feature selection for the pairwise covariates, and propose two corresponding algorithms. PCABM compares favorably with the SBM or degree-corrected stochastic block model (DCBM) under a wide range of simulated and real networks when covariate information is accessible.

arXiv comment103 pages, 7 figures

References in corpus (20)

• Modularity and community structure in networks
• Community detection in graphs
• Comparing community structure identification
• Stochastic blockmodels and community structure in networks
• Mixture models and exploratory analysis in networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• The ground truth about metadata and community detection in networks
• Structure and inference in annotated networks
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Stochastic blockmodels with growing number of classes
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Modeling homophily and stochastic equivalence in symmetric relational data
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Community extraction for social networks
• A testing based extraction algorithm for identifying significant communities in networks
• Generalized linear models with low rank effects for network data
• Topic-adjusted visibility metric for scientific articles