Graph 01 : Louvain Algorithm
( Easy understanding from Jure Leskovec, Stanford CS224W : Machine Learning with Graph)
What is Louvain Algorithm??
Louvain algorithm is the community detection algorithm (The algorithm for finding graph clustering). The algorithm calculates which nodes should be in the same community based on edges’ characteristics.
Louvain algorithm calculates how good the graph separated into communities by using modularity concept. The algorithm will find greedily maximizes modularity value. Based on the concept of finding internal edges in sub-community compared with expected edges that the sub-community can have.
The high value of modularity meaning that it is the good community. Louvain will find the maximum summation of all modularity that the main graph can have.
Louvain will compare sub-communities’s modularity in all combinations that can occur and select the largest summation of modularity the main graph can have.
There are many metric for calculate how good of graph community. The most well known metric is Modularity. Louvain calculates from the concept of this metric.
The metric for community detection. Calculated from the concept that the modularity value will High if Number of High edges within group is larger than expected number of edges within group can have (Calculate expected edge from the random graph with identical number of nodes with the real graph)
Modularity Q Concept
HIGH Modularity Q meaning that the edges within the same sub-community is denser than expected edges. Thus we will calculate modularity Q from the difference between internal edge (real edges in the same sub-community) and expected edges from random graph with the same number of nodes.
Modularity Q Formula
We use greedy algorithm on modularity gain to compare which community node i should belong to and finding the maximum modularity the main graph can have.
Modularity gain is the difference between modularity Q value before adding individual node to community and modularity Q value after adding individual node to community to decide which community should assign node i to.
Louvain has 2 steps calculation.
Phase 1: Finding maximum modularity bases on node granularity memberships.
— — — Pseudocode
Phase 2: Aggregate communities from phase 1 to super-nodes and calculate maximum modularity based on super-nodes granularity memberships.
Louvain Main Formula (derived)
We will compute modularity gain to each combination that node i can be in communities and selecting the maximum modularity gain to decide which sub-community node i should belong to.
Derived Modularity Q for easily use
Actionable use of modularity gain formula
How to use modularity Gain formula in real graph
Compare and select the maximum modularity gain until all nodes stable (not change the belonging community)
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —