Louvain Clustering: Difference between revisions
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 === | ||
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 === | ||
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:
- (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
Practically, the algorithm seems to scale well for large graphs.
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
- "The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html