On the Power of Louvain in the Stochastic Block Model Vincent Cohen-Addad

A classic problem in machine learning and data analysis is to partition the vertices of a network in such a way that vertices in the same set are densely connected and vertices in different sets are loosely connected. In practice, the most popular approaches rely on local search algorithms; not only for the ease of implementation and the efficiency, but also because of the accuracy of these methods on many real world graphs. For example, the Louvain algorithm - a local search based algorithm - has quickly become the method of choice for clustering in social networks.