Clustering Degree-Corrected Stochastic Block Model with Outliers
For the degree corrected stochastic block model in the presence of arbitrary or even adversarial outliers, we develop a convex-optimization-based clustering algorithm that includes a penalization term depending on the positive deviation of a node from the expected number of edges to other inliers. We prove that under mild conditions, this method achieves exact recovery of the underlying clusters. Our synthetic experiments show that our algorithm performs well on heterogeneous networks, and in particular those with Pareto degree distributions, for which outliers have a broad range of possible degrees that may enhance their adversarial power. We also demonstrate that our method allows for recovery with significantly lower error rates compared to existing algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringmodelStochastic Block ModelSimilar Papers 제목 키워드 기반
Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding
Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain…
ClusteringA spectral method for community detection in moderately-sparse degree-corrected stochastic block models
We consider community detection in Degree-Corrected Stochastic Block Models (DC-SBM). We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently r…
ClusteringCommunity DetectionRegularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
Spectral clustering is a fast and popular algorithm for finding clusters in networks. Recently, Chaudhuri et al. (2012) and Amini et al.(2012) proposed inspired variations on the algorithm that artificially inflate the n…
ClusteringConsistency of spectral clustering in stochastic block models
We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the network can consisten…
ClusteringAn improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochas…
ClusteringCommunity DetectionStochastic Block Model