TY - GEN

T1 - Consistency thresholds for the planted bisection model

AU - Mossel, Elchanan

AU - Neeman, Joe

AU - Sly, Allan

N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2015/6/14

Y1 - 2015/6/14

N2 - The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recover-ability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the sparse case where pn, qn = T(log n/n).

AB - The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recover-ability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the sparse case where pn, qn = T(log n/n).

KW - Graph clustering

KW - Min-bisection

KW - Planted bisection model

KW - Random graph

KW - Stochastic block model

UR - http://www.scopus.com/inward/record.url?scp=84958757854&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958757854&partnerID=8YFLogxK

U2 - 10.1145/2746539.2746603

DO - 10.1145/2746539.2746603

M3 - Conference contribution

AN - SCOPUS:84958757854

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 69

EP - 75

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -