Louvain Clustering

From visone manual
Revision as of 14:42, 2 April 2015 by Nocaj (talk | contribs)
Jump to navigation Jump to search

Louvain Clustering

Method

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:

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


Complexity

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

References