Difference between revisions of "Louvain Clustering"

From visone manual
Jump to navigation Jump to search
(Created page with "=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. === Comple...")
 
Line 1: Line 1:
 
=Louvain Clustering=
 
=Louvain Clustering=
 
=== Method ===
 
=== 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 ===
 
=== Complexity ===

Revision as of 14:38, 2 April 2015

Louvain Clustering

Method

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

The algorithm is:

  1. start with each node being a singleton cluster:
  2. consider nodes in random order
  3. 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
  4. aggregate the resulting clustering to a new graph and continue with step 1 (as long as modularity improves).


Complexity

The algorithms scales well for large graphs

References