The Louvain Algorithm

One way of finding communities inside complex networks is by finding the division of maximum modularity. However, calculating the modularity for every single possibility of division ends up with a factorial number of options, which is basically impossible to calculate for large networks.

People have developed algorithms that use heuristics to maximize modularity because the best possible solution is so hard to find. One such algorithm is the Louvain method, which uses a greedy heuristic.

In a greedy heuristic, we focus on maximizing the modularity only one step further, even if that step doesn’t guarantee our best modularity overall.

Let’s see what the algorithm looks like.

The Louvain method

The Louvain method is an unsupervised method, which means we don’t need to have the ground-truth communities to find a division. Most of the community detection algorithms will be unsupervised.

The algorithm starts with every node being assigned to one community, such as in the image below, where each color represents a community.