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 information. In this work, we study an extension of the Stochastic Block Model (SBM), a widely used statistical framework for community detection, that integrates vectorial edges covariates: the Vectorial Edges Covariates Stochastic Block Model (VEC-SBM). We propose a novel algorithm based on iterative refinement techniques and show that it optimally recovers the latent communities under the VEC-SBM. Furthermore, we rigorously assess the added value of leveraging edge's side information in the community detection process. We complement our theoretical results with numerical experiments on synthetic and semi-synthetic data.
Code (1)
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Perfect 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 EfficiencyCovariate Regularized Community Detection in Sparse Graphs
In this paper, we investigate community detection in networks in the presence of node covariates. In many instances, covariates and networks individually only give a partial view of the cluster structure. One needs to jo…
ClusteringCommunity DetectionEquipping SBMs with RBMs: An Explainable Approach for Analysis of Networks with Covariates
Networks with node covariates offer two advantages to community detection methods, namely, (i) exploit covariates to improve the quality of communities, and more importantly, (ii) explain the discovered communities by id…
Community DetectionLink PredictionPairwise 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 detecti…
ClusteringCommunity Detectionfeature selectionmodel+2Community detection in networks without observing edges
We develop a Bayesian hierarchical model to identify communities in networks for which we do not observe the edges directly, but instead observe a series of interdependent signals for each of the nodes. Fitting the model…
Community Detection