Louvain Clustering: Difference between revisions

From visone manual
Jump to navigation Jump to search
No edit summary
No edit summary
 
(One intermediate revision by the same user not shown)
Line 5: Line 5:


The algorithm is:
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
# 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
#* 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.





Latest revision as of 13:27, 9 April 2015

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