text: We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph @math from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit single-letter' characterization of the per-vertex mutual information between the vertex labels and the graph. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and --in particular-- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.
  @cite_35: 
  @cite_36: The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph l-partition problem is to partition the nodes of an undirected graph into l equal-sized groups so as to minimize the total number of edges that cross between groups.
  @cite_41: We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hidden submatrices with elevated means inside a large real-valued random matrix. Of particular interest is the setting where the number of clusters submatrices is allowed to grow unbounded with the problem size. These formulations cover several classical models such as planted clique, planted densest subgraph, planted partition, planted coloring, and stochastic block model, which are widely used for studying community detection and clustering bi-clustering. For both problems, we show that the space of the model parameters (cluster submatrix size, cluster density, and submatrix mean) can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the regime, where all algorithms fail; (2) the regime, where the computationally expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the regime, where the polynomial-time convexified MLE succeeds; (4) the regime, where a simple counting thresholding procedure succeeds. Moreover, we show that each of these algorithms provably fails in the previous harder regimes. Our theorems establish the minimax recovery limit, which are tight up to constants and hold with a growing number of clusters submatrices, and provide a stronger performance guarantee than previously known for polynomial-time algorithms. Our study demonstrates the tradeoffs between statistical and computational considerations, and suggests that the minimax recovery limit may not be achievable by polynomial-time algorithms.
  @cite_29: Abstract The average-case complexity of recognising some NP-complete properties is examined, when the instances are randomly selected from those which have the property. We carry out this analysis for 1. (1) Graph k -colourability. We describe an O ( n 2 ) expected time algorithm for n -vertex graphs, with k constant. 2. (2) Small equitable cut. We describe an O ( n 3 ) expected time algorithm for finding and verifying , the minimum equitable cut in a 2 n -vertex graph G , condition on G having one with at most (1 − ϵ)n 2 2 edges. 3. (3) Partitioning a 2 n vertex graph into two sparse vertex induced subgraphs of a given class. We describe an O ( n 3 ) expected time algorithm for computing such a partition. 4. (4) The number problem 3-PARTITION. We describe an O ( n 2 ) expected time algorithm for problems with 3 n integers.
  @cite_43: The binary symmetric stochastic block model deals with a random graph of @math vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability @math within clusters and @math across clusters. In the asymptotic regime of @math and @math for fixed @math and @math , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe14 . Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to @math .
  @cite_15: 
  @cite_58: 
  @cite_10: We analyze the behavior of hill-climbing algorithms for the minimum bisection problem on instances drawn from the “planted bisection” random graph model, G n,p,q , previously studied in [3, 4, 10, 11, 14, 9, 7]. This is one of the few problem distributions for which various popular heuristic methods, such as simulated annealing, have been proven to succeed. However, it has been open whether these sophisticated methods were necessary, or whether simpler heuristics would also work. Juels [14] made the first progress towards an answer by showing that simple hill-climbing does suffice for very wide separations between p and q. Here we give a more complete answer. A simple, polynomial-time, hill-climbing algorithm for this problem is given and shown to succeed in finding the planted bisection with high probability if p - q = O (n-½ln3n). For dense graphs, this matches the condition for optimality of the planted bisection to within a polylogarithmic factor. Furthermore, we show that a generic randomized hill-climbing algorithm succeeds in finding the planted bisection in polynomial time if p - q = O (n-¼ ln3 n), for any ∈ > 0. This algorithm, studied also by [14], is a degenerate case of both Metropolis and go-with-the-winners, and the range here properly includes those analyzed in [11, 9, 14]. So this result implies, extends, and unifies those from [11, 9, 14]. Thus, to get a provable distinction between simulated annealing and hill-climbing for natural problems will require considerable progress both on new positive results for SA and new negative results for hill-climbing methods.
  @cite_20: The stochastic block model (SBM) with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behaviour. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability @math within clusters and @math across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower-bounds on the scaling of @math to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if @math and @math are constant (with @math ), recovering the communities with high probability is possible if @math and impossible if @math . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst-case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest it may achieve the threshold. An efficient algorithm which succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure.
  @cite_18: We consider the problem of community detection in the Stochastic Block Model with a finite number @math of communities of sizes linearly growing with the network size @math . This model consists in a random graph such that each pair of vertices is connected independently with probability @math within communities and @math across communities. One observes a realization of this random graph, and the objective is to reconstruct the communities from this observation. We show that under spectral algorithms, the number of misclassified vertices does not exceed @math with high probability as @math grows large, whenever @math , @math and where @math and @math denote the (fixed) proportions of vertices in the two smallest communities. In view of recent work by and , this establishes that the proposed spectral algorithms are able to exactly recover communities whenever this is at all possible in the case of networks with two communities with equal sizes. We conjecture that condition (1) is actually necessary to obtain less than @math misclassified vertices asymptotically, which would establish the optimality of spectral method in more general scenarios.
  @cite_8: 
  @cite_48: Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social ne tworks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several empirical networks. Spectral clustering is a popular and computationally feasi ble method to discover these communities. The Stochastic Block Model (, 1983) is a social network model with well defined communities; each node is a member of one community. For a network generated from the Stochastic Block Model, we bound the number of nodes "misclus- tered" by spectral clustering. The asymptotic results in th is paper are the first clustering results that allow the number of clusters in the model to grow with the number of nodes, hence the name high-dimensional. In order to study spectral clustering under the Stochastic Block Model, we first show that under the more general latent space model, the eigenvectors of the normalized graph Laplacian asymptotically converge to the eigenvectors of a "population" normal- ized graph Laplacian. Aside from the implication for spectral clustering, this provides insight into a graph visualization technique. Our method of studying the eigenvectors of random matrices is original. AMS 2000 subject classifications: Primary 62H30, 62H25; secondary 60B20.
  @cite_52: We resolve in the affirmative a question of Boppana and Bui: whether simulated annealing can, with high probability and in polynomial time, find the optimal bisection of a random graph in npr when p − R = Θ(nΔ − 2) for Δ 2. (The random graph model npr specifies a “planted” bisection of density r, separating two n 2-vertex subsets of slightly higher density p.) We show that simulated “annealing” at an appropriate fixed temperature (i.e., the Metropolis algorithm) finds the unique smallest bisection in O(n2 + ) steps with very high probability, provided . (By using a slightly modified neighborhood structure, the number of steps can be reduced to O(n1+).) We leave open the question of whether annealing is effective for Δ in the range , whose lower limit represents the threshold at which the planted bisection becomes lost amongst other random small bisections. It also remains open whether hillclimbing (i.e., annealing at temperature 0) solves the same problem; towards the latter result, Juels has recently extended our analysis and shown that random hillclimbing finds the minimum bisection with constant probability, when p − R = Ω(1) (corresponding to Δ=2).
  @cite_39: A statistical approach to a posteriori blockmodeling for graphs is proposed. The model assumes that the vertices of the graph are partitioned into two unknown blocks and that the probability of an edge between two vertices depends only on the blocks to which they belong. Statistical procedures are derived for estimating the probabilities of edges and for predicting the block structure from observations of the edge pattern only. ML estimators can be computed using the EM algorithm, but this strategy is practical only for small graphs. A Bayesian estimator, based on Gibbs sampling, is proposed. This estimator is practical also for large graphs. When ML estimators are used, the block structure can be predicted based on predictive likelihood. When Gibbs sampling is used, the block structure can be predicted from posterior predictive probabilities. A side result is that when the number of vertices tends to infinity while the probabilities remain constant, the block structure can be recovered correctly with probability tending to 1. (Less)
  @cite_49: New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry. In the general stochastic block model @math , @math vertices are split into @math communities of relative size @math , and vertices in community @math and @math connect independently with probability @math . This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities. The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new divergence function @math , which generalizes the Hellinger and Chernoff divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, in contrast to the conjectures made for detection with more than 4 communities; note that the algorithm is optimal both in terms of achieving the threshold and in having quasi-linear complexity, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio (defined in term of the spectrum of @math ) tends to infinity.
  @cite_17: We develop a new algorithm to cluster sparse unweighted graphs - i.e. partition the nodes into disjoint clusters so that there is higher density within clusters, and low across clusters. By sparsity we mean the setting where both the in-cluster and across cluster edge densities are very small, possibly vanishing in the size of the graph. Sparsity makes the problem noisier, and hence more difficult to solve. Any clustering involves a tradeoff between minimizing two kinds of errors: missing edges within clusters and present edges across clusters. Our insight is that in the sparse case, these must be penalized differently. We analyze our algorithm's performance on the natural, classical and widely studied "planted partition" model (also called the stochastic block model); we show that our algorithm can cluster sparser graphs, and with smaller clusters, than all previous methods. This is seen empirically as well.
  @cite_7: SUMMARY We present asymptotic and finite-sample results on the use of stochastic blockmodels for the analysis of network data. We show that the fraction of misclassified network nodes converges in probability to zero under maximum likelihood fitting when the number of classes is allowed to grow as the root of the network size and the average network degree grows at least polylogarithmically in this size. We also establish finite-sample confidence bounds on maximumlikelihood blockmodel parameter estimates from data comprising independent Bernoulli random variates; these results hold uniformly over class assignment. We provide simulations verifying the conditions sufficient for our results, and conclude by fitting a logit parameterization of a stochasticblockmodelwithcovariatestoanetworkdataexamplecomprisingself-reportedschool friendships, resulting in block estimates that reveal residual structure.
  @cite_6: Graph Bisection is the problem of partitioning the vertices of a graph into two equal-size pieces so as to minimize the number of edges between the two pieces. This paper presents an algorithm that will, for almost all graphs in a certain class, output the minimum-size bisection. Furthermore the algorithm will yield, for almost all such graphs, a proof that the bisection is optimal. The algorithm is based on computing eigenvalues and eigenvectors of matrices associated with the graph.
  @cite_12: Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.
  @cite_14: Problems such as bisection, graph coloring, and clique are generally believed hard in the worst case. However, they can be solved if the input data is drawn randomly from a distribution over graphs containing acceptable solutions. In this paper we show that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. In nearly all cases our approach meets or exceeds previous parameters, while introducing substantial generality. We apply spectral techniques, using foremost the observation that in all of these problems, the expected adjacency matrix is a low rank matrix wherein the structure of the solution is evident.
summary: A large part of the literature has focused on the problem of of the community (cluster) structure. A long series of papers @cite_8 @cite_29 @cite_6 @cite_39 @cite_52 @cite_36 @cite_10 @cite_14 @cite_35 @cite_48 @cite_7 @cite_17 @cite_12 @cite_41 , establishes sufficient conditions on the gap between @math and @math that guarantee exact recovery of the vertex labels with high probability. A sharp threshold for exact recovery was obtained in @cite_20 @cite_15 , showing that for @math , @math , @math , exact recovery is solvable (and efficiently so) if and only if @math . Efficient algorithms for this problem were also developed in @cite_18 @cite_43 @cite_58 . For the SBM with arbitrarily many communities, necessary and sufficient conditions for exact recovery were recently obtained in @cite_49 . The resulting sharp threshold is efficiently achievable and is stated in terms of a CH-divergence.