Louvain Algorithm

At our meeting on 09/18/15, I presented the Louvain Algorithm as outlined in the paper “Fast unfolding of communities in large networks”.

This method centers around optimizing modularity, which measures the density of the links inside of the communities as compared to the links between communities.

This image from the paper provides a good visualization of the Louvain algorithm.

The algorithm begins by assigning each node to its own community. The first phase of this algorithm is labeled “Modularity Optimization” in the image. For each node in this phase, the algorithm looks at how much the modularity changes if the node is removed from its community and added to each of its neighbor’s communities. The node is then placed into the community where the gain in modularity is maximized. This process is repeated for each of the nodes until no further improvement can be achieved. In the second phase, called “Community Aggregation”, the algorithm now builds a new network whose nodes are now the communities found in the first phase.

We can now repeat the two phases on our new network. Going though the two phases is referred to as one “pass” through the algorithm. As we can see in the image, the algorithm goes though another pass of repeating the two phases on this community. The passes are iterated until there are no more changes to be made and a maximum of modularity is achieved.

We are going to begin working with the Louvain algorithm soon by modifying the algorithm to optimize metrics other than modularity.