# Difference between revisions of "Louvain Clustering"

Jump to navigation
Jump to search

Line 2: | Line 2: | ||

=== Method === | === Method === | ||

− | The Louvain clustering tries to optimize modularity in a greedy fashion. | + | 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: | The algorithm is: | ||

Line 13: | Line 13: | ||

=== 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 |

## Revision as of 14:40, 2 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:

- start with each node being a singleton cluster:
- consider nodes in random order
- repeat as long as cluster membership changes, consider nodes in a random order
- 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).

### 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