Revision as of 14:38, 2 April 2015

Louvain Clustering

The Louvain clustering tries to optimize modularity in a greedy fashion.

The algorithm is:

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
- 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).

The algorithms scales 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 1: / Line 1: @@
 =Louvain Clustering=
 === Method ===
-Starting with a state where each node is a singleton cluster, it greedily merges two clusters if the modularity score gets higher.
+The Louvain clustering tries to optimize modularity in a greedy fashion.
+The algorithm is:
+# 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
+#* 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).
 === Complexity ===