Skip to main content

From Local to Global: Local Search Algorithms Beyond the Worst-Case Analysis

Vincent Cohen-Addad ( Sorbonne Université, CNRS )

A classic problem in data analysis consists in partitioning the vertices of a network in such a way that vertices in the same set are densely 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 detecting communities in social networks, accumulating more than 8600 citations over the past 10 years.  However, explaining the success of these methods remains an open problem: in the worst-case, their performances can be arbitrarily bad.

In this work, we study these local search heuristics and aim at explaining their success and identifying the mechanisms that make them successful through a classic model for social networks, the stochastic block model. We give the first theoretical evidence that Louvain finds the underlying natural partition of the network.

 

 

Share this: