Louvain Clustering: Difference between revisions

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...")
 
No edit summary
 
(3 intermediate revisions by the same user not shown)
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 by randomly moving nodes from one cluster to another in multiple levels.
 
The algorithm is:
# (level) start with each node being a singleton cluster:
# consider nodes in 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
# aggregate the resulting clustering to a new graph and continue on next level (step 1), as long as modularity improves.
 


=== Complexity ===
=== Complexity ===
The algorithms scales well for large graphs  
Practically, the algorithm seems to scale well for large graphs.


=== References ===
=== References ===
*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
*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
*"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html

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