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_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_51: Abstract A stochastic model is proposed for social networks in which the actors in a network are partitioned into subgroups called blocks. The model provides a stochastic generalization of the blockmodel. Estimation techniques are developed for the special case of a single relation social network, with blocks specified a priori. An extension of the model allows for tendencies toward reciprocation of ties beyond those explained by the partition. The extended model provides a one degree-of-freedom test of the model. A numerical example from the social network literature is used to illustrate the methods.
  @cite_8: 
summary: The stochastic block model was first introduced within the social science literature in @cite_51 . Around the same time, it was studied within theoretical computer science @cite_8 @cite_29 , under the name of planted partition model. '