Improved graph clustering
Abstract
Graph clustering involves the task of partitioning nodes, so that the edge density is higher within partitions as opposed to across partitions. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this paper we present a new algorithm - a convexified version of Maximum Likelihood - for graph clustering. We show that, in the classic stochastic block model setting, it outperforms all existing methods by polynomial in fact, it is within logarithmic factors of known lower bounds for spectral methods. We then show that this guarantee carries over to a more general semi-random extension of the stochastic block model; our method can handle settings of heterogeneous degree distributions, unequal cluster sizes, outlier nodes, planted k-cliques etc.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2013
- Accession Number
- ADA596381
Entities
People
- Huan Xu
- Sujay Sanghavi
- Yudong Chen
Organizations
- University of Texas at Austin