The Louvain Algorithm
Learn about the Louvain algorithm and how to use it for community detection.
We'll cover the following...
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.
Now, for every node in the network, we try to put it in one of its neighbor’s communities and measure how much the modularity has grown or decreased when we did it.
After we calculate all the options, we choose to put each node in the community that yields the higher modularity gain at that step. We then repeat this step ...