Pairwise Covariates-adjusted Block Model for Community Detection
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity Detectionfeature selectionmodelModel SelectionStochastic Block ModelMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates
Social networks are often associated with rich side information, such as texts and images. While numerous methods have been developed to identify communities from pairwise interactions, they usually ignore such side info…
Community DetectionStochastic Block ModelOn spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariates
In network inference applications, it is often desirable to detect community structure, namely to cluster vertices into groups, or blocks, according to some measure of similarity. Beyond mere adjacency matrices, many rea…
ClusteringCommunity DetectionBayesian community detection for networks with covariates
The increasing prevalence of network data in a vast variety of fields and the need to extract useful information out of them have spurred fast developments in related models and algorithms. Among the various learning tas…
Community DetectionStochastic Block ModelPerfect Spectral Clustering with Discrete Covariates
Among community detection methods, spectral clustering enjoys two desirable properties: computational efficiency and theoretical guarantees of consistency. Most studies of spectral clustering consider only the edges of a…
ClusteringCommunity DetectionComputational EfficiencyContextual Stochastic Block Models
We provide the first information theoretic tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our wor…