Latest revision as of 13:27, 9 April 2015

Louvain Clustering

The Louvain clustering tries to optimize modularity in a greedy fashion by randomly moving nodes from one cluster to another in multiple levels.

The algorithm is:

(level) start with each node being a singleton cluster:
consider nodes in random order
iterate as long as cluster membership changes
- for each node : remove it from its current cluster and add it to the cluster with the highest modularity gain
aggregate the resulting clustering to a new graph and continue on next level (step 1), as long as modularity improves.

Practically, the algorithm seems to scale well for large graphs.

Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp) doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476
"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html

@@ Line 5: / Line 5: @@
 The algorithm is:
-# start with each node being a singleton cluster:
+# (level) start with each node being a singleton cluster:
 # consider nodes in random order
-# repeat as long as cluster membership changes, consider nodes in a random order
+# iterate as long as cluster membership changes
 #* for each node : remove it from its current cluster and add it to the cluster with the highest modularity gain
-# aggregate the resulting clustering to a new graph and continue with step 1 (as long as modularity improves).
+# aggregate the resulting clustering to a new graph and continue on next level (step 1), as long as modularity improves.