Reconstructing Many Partitions Using Spectral Techniques

Joachim Giesen, Dieter Mitsche

Abstract

Abstract. A partitioning of a set of n items is a grouping of these items into k disjoint, equally sized classes. Any partition can be modeled as a graph. The items become the vertices of the graph and two vertices are connected by an edge if and only if the associated items belong to the same class. In a planted partition model a graph that models a partition is given, which is obscured by random noise, i.e., edges within a class can get removed and edges between classes can get inserted. The task is to reconstruct the planted partition from this graph. In the model that we study the number k of classes controls the difficulty of the task. We design a spectral partitioning algorithm that asymptotically almost surely reconstructs up to k = c √ n partitions, where c is a small constant, in time C k poly(n), where C is another constant. 1
BibTeX
@inproceedings{giesen2005reconstructing,
  author = {Joachim Giesen and Dieter Mitsche},
  title = {{Reconstructing Many Partitions Using Spectral Techniques}},
  booktitle = {FCT},
  year = {2005},
  doi = {10.1007/11537311\_38},
}

Loading related content...

Figure