Community Detection in the Multi-View Stochastic Block Model
This paper considers the problem of community detection on multiple potentially correlated graphs from an information-theoretical perspective. We first put forth a random graph model, called the multi-view stochastic block model (MVSBM), designed to generate correlated graphs on the same set of nodes (with cardinality $n$). The $n$ nodes are partitioned into two disjoint communities of equal size. The presence or absence of edges in the graphs for each pair of nodes depends on whether the two nodes belong to the same community or not. The objective for the learner is to recover the hidden communities with observed graphs. Our technical contributions are two-fold: (i) We establish an information-theoretic upper bound (Theorem~1) showing that exact recovery of community is achievable when the model parameters of MVSBM exceed a certain threshold. (ii) Conversely, we derive an information-theoretic lower bound (Theorem~2) showing that when the model parameters of MVSBM fall below the aforementioned threshold, then for any estimator, the expected number of misclassified nodes will always be greater than one. Our results for the MVSBM recover several prior results for community detection in the standard SBM as well as in multiple independent SBMs as special cases.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
Multi-view data arises frequently in modern network analysis e.g. relations of multiple types among individuals in social network analysis, longitudinal measurements of interactions among observational units, annotated n…
Community DetectionStochastic Block ModelA Semidefinite Program for Structured Blockmodels
Semidefinite programs have recently been developed for the problem of community detection, which may be viewed as a special case of the stochastic blockmodel. Here, we develop a semidefinite program that can be tailored …
Community DetectionPairwise 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+2A stochastic block model for community detection in attributed networks
Community detection is an important content in complex network analysis. The existing community detection methods in attributed networks mostly focus on only using network structure, while the methods of integrating node…
ClusteringCommunity DetectionStochastic Block ModelStochastic Block Models with Multiple Continuous Attributes
The stochastic block model (SBM) is a probabilistic model for community structure in networks. Typically, only the adjacency matrix is used to perform SBM parameter inference. In this paper, we consider circumstances in …
AttributeCollaborative FilteringCommunity DetectionLink Prediction+1