Consistency Thresholds for Binary Symmetric Block Models.

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