Remember me

Register  |   Lost password?


arXiv logo for blog page

Clustering Degree-Corrected Stochastic Block Model with Outliers. (arXiv:1906.03305v1 [cs.LG])

Mon, 10 Jun 2019 23:02:02 GMT

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