Maximizing modularity: time VS. quality

> By Jean-Loup Guillaume

Maximizing modularity: time VS. quality

Maximizing modularity: time VS. quality

Community detection in complex networks is a hard problem whose classical formulation is the maximisation of the modularity. Since this problem cannot be solved exactly in a reasonable time, heuristics are used to find the best communities.

The Louvain method is an efficient technique to study this problem and consists in a sequence of passes, each being composed of a sequence of iterations. During one iteration of a given pass, all nodes are considered once and are moved from one community to another so as to maximise the gain of modularity. Rather than doing iterations for a given pass while an improvement can be achieved, we study here the loss of quality if we only perform iterations while the improvement is greater than a given epsilon.

The above plot displays the final modularity (in red) and execution time (in blue) as a function of this epsilon. The greater the epsilon, the less iterations are going to be performed at each pass. This can be seen of the blue curve: with a maximal optimization (left part of the curve), the computation time can take as long a 550s, while with a higher value of epsilon, it can be divided by 10. On the other hand, the red curve displays the final modularity obtained and we can see that even with high value of epsilon, the final quality is still good. It is only above a given value, which is between 0.1 and 0.01 depending on the network, that the quality drops suddenly. Therefore, there is not always a compromise to do between time and quality of the decomposition in communities.

In specific cases the modularity is even better with a high epsilon than with a small one. This can be understood as follows: a strong optimisation of the modularity on the first pass can impose too much constraints on the obtained partition and prevent further optimisation to be achieved on subsequent passes. On the other hand, doing a smaller optimization during the first pass can leave much more space for further optimization.

This entry was posted in Plots and tagged ,