Abstract. The stochastic block model is a natural model for studying community detection in random networks. Its clustering properties have been extensively studied in the statistics, physics and computer science literature. Recently this area has experienced major mathematical breakthroughs, particularly for the binary (two-community) version, see [26, 27, 21] . In this paper, we introduce a variant of the binary model which we call the regular stochastic block model (RSBM). We prove rigidity by showing that with high probability an exact recovery of the community structure is possible. Spectral methods exhibit a regime where this can be done efficiently. Moreover we also prove that, in this setting, any suitably good partial recovery can be bootstrapped to obtain a full recovery of the communities. The stochastic block model (SBM) is a classical cluster-exhibiting random graph model that has been extensively studied, both empirically and rigorously, across numerous fields. In its simplest form, the SBM is a model of random graphs on 2n nodes with two equal-sized clusters A and B such that |A| = |B| = n and A ∩ B = ∅. Edges between various pairs of vertices appear independently with probability p = p n if the two vertices belong to the same cluster and with probability q = q n otherwise. Thus, for any vertex, the expected number of same-class neighbors is a := a n := p(n − 1) ∼ pn, and the expected number of across-class neighbors is b := b n := qn. Given a realization of the graph, the broad goal is to determine whether it is possible (with high probability) to find the partition A, B; and if the answer is yes, whether it is possible to do so using an efficient algorithm. Otherwise, the best one can hope for is the existence of an algorithm that will output a partition which is highly (or at least positively) correlated with the underlying cluster. To this end, consider the space M of all algorithms which take as input a finite graph on 2n vertices and output a partition of the vertex set into two sets. Informally, we say that an algorithm in M allows for weak recovery if, with probability going to 1 as n goes to infinity, it outputs a partition (A , B ) such that |A∆A | + |B∆B | = o(n) (here ∆ denotes the symmetric difference). We say that an algorithm allows for strong recovery if, with probability going to 1 as n goes to infinity, it outputs the partition (A, B) . Finally, an algorithm in M will be called efficient if its run time is polynomial in n. The problem of community detection described above is closely related to the min-bisection problem, where one looks for a partition of the vertex set of a given graph into two subsets of equal size such that the number of edges across the subsets is minimal. In general, this problem is known to be NP-hard [12] ; however, if the min-bisection is smaller than most of the other bisections, the problem is known to be simpler. This fact was noticed a few decades ago, with the advent of the study of min-bisection in the context of the SBM. In particular, Dyer and Frieze [9] produced one of the earliest results when they showed that if p > q are fixed as n → ∞ then the min-bisection is the one that separates the two classes, and it can be found in expected O(n 3 ) time. Their results were improved by Jerrum and Sorkin [16] and Condon and Karp [7] . Each of these papers were 1 arXiv:1507.00930v3 [math.PR]
In particular Brito et al. REF show that strong reconstruction is possible in polynomial-time
Recovery and Rigidity in a Regular Stochastic Block Model
SODA 2016
arXiv: Probability
Computer Science Mathematics