On the Power of Louvain for Graph Clustering Supplementary Material A The Stochastic Block Model and Definitions

In the following, we use X P to denote that the random variable X follows the law P . See Figure 1a for an illustration of such a graph generated by the Stochastic Block Model. Interestingly, Newman [31] has shown that the modularity objective is the maximum likelihood of a variant of the SBM on two communities, with prescribed degree distribution. However, it leaves the natural question open of whether the Louvain heuristic on the SBM with two communities indeed converges to this solution (the hidden partition). Proving the convergence shows that Louvain's local decisions can indeed be powerful enough to reach the global optimum.