Analysis of community detection algorithms in real-world and random graphs

Real-life networks often display community structure. The Louvain algorithm [3] is an influential efficient method for finding communities in networks. This algorithm is a standard part of many software packages such as the widely used graph visualization platform Gephi. Improvements and modifications of the algorithm have been suggested and used e.g. for large-scale analysis of citation networks [12], and for a more general problem of maximizing the likelihood of communities [10].
Remarkably, mathematical properties of Louvain algorithm are still poorly understood. This is due to chal-lenges in both formalization and analysis of the iterative approach, on which Louvain is based. Due to the importance of community detection in large-scale networks, there is a high urgency in addressing this gap.
Research goals. We propose comprehensive mathematical analysis of the Louvain algorithm in its most general form building on recently developed methodologies within NETWORKS. This project aims to:

(i) evaluate the quality of iterative community detection algorithms, such as the Louvain algorithm, by ana-lyzing these algorithms on random graphs with a known community structure;
(ii) provide mathematical evidence that shows for what types of real-world networks the methods work well, and for what they do not, possibly depending on the microscopic-mesocscopic-macroscopic nature of the communities;
(iii) lay theoretical foundations for new well-justified approaches in community detection, by using testbed random graph models, and for example using local weak convergence.