Louvain Clustering

From visone manual
Revision as of 13:27, 9 April 2015 by Nocaj (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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


Complexity

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

References