Published on Fri Jun 07 2019

Clustering Degree-Corrected Stochastic Block Model with Outliers

Xin Qian, Yudong Chen, Andreea Minca

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.

0
0
0
Abstract

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.

Tue Dec 15 2015
Machine Learning
Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. We show that it is possible, in the right circumstances (when sizes are spread and the smaller the cluster, the denser), to recover very small clusters.
0
0
0
Wed Apr 23 2014
Machine Learning
Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
Community detection aims to cluster nodes in a given graph into distinct groups based on the observed undirected edges. In this paper, the popular stochastic block model (SBM) is extended to a model that allows for adversarial outlier nodes. Both theoretical and numerical properties of the method are analyzed.
0
0
0
Thu Oct 11 2012
Machine Learning
Improved Graph Clustering
Graph clustering involves the task of dividing nodes into clusters, so that edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model.
0
0
0
Thu Feb 26 2015
Machine Learning
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
The semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The same was shown for the case of a single cluster and outliers.
0
0
0
Mon Dec 28 2015
Machine Learning
Convexified Modularity Maximization for Degree-corrected Stochastic Block Models
The stochastic block model (SBM) is a popular framework for studying community detection in networks. This paper proposes a convexified modularity maximization approach for estimating hidden communities under DCSBM.
0
0
0
Sat Jul 04 2020
Machine Learning
On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariates
In network inference applications, it is often desirable to cluster vertices into groups, or blocks, according to some measure of similarity. We present a comparative analysis of two model-based spectral algorithms for clustering vertices. The first algorithm uses only the adjacency matrix, and directly estimates the induced block assignments.
0
0
0