Louvain method

Short description: Clustering and community detection algorithm

This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (April 2025) (Learn how and when to remove this template message)

|

Network science

* Theory

* Graph
* Complex network
* Contagion
* Small-world
* Scale-free
* Community structure
* Percolation
* Evolution
* Controllability
* Graph drawing
* Social capital
* Link analysis
* Optimization
* Reciprocity
* Closure
* Homophily
* Transitivity
* Preferential attachment
* Balance theory
* Network effect
* Social influence

Network types

* Informational (computing)
* Telecommunication
* Transport
* Social
* Scientific collaboration
* Biological
* Artificial neural
* Interdependent
* Semantic
* Spatial
* Dependency
* Flow
* on-Chip

Graphs
|  Features

* Clique
* Component
* Cut
* Cycle
* Data structure
* Edge
* Loop
* Neighborhood
* Path
* Vertex
* Adjacency list / matrix
* Incidence list / matrix

Types

* Bipartite
* Complete
* Directed
* Hyper
* Multi
* Random
* Weighted

* Metrics
* Algorithms

* Centrality
* Degree
* Betweenness
* Closeness
* PageRank
* Motif
* Clustering
* Degree distribution
* Assortativity
* Distance
* Modularity
* Efficiency

Models
|  Topology

* Random graph
* Erdős–Rényi
* Barabási–Albert
* Fitness model
* Watts–Strogatz
* Exponential random (ERGM)
* Random geometric (RGG)
* Hyperbolic (HGN)
* Hierarchical
* Stochastic block
* Maximum entropy
* Soft configuration
* LFR Benchmark

Dynamics

* Boolean network
* agent based
* Epidemic/SIR

* Lists
* Categories

* Topics
* Software
* Network scientists

* Category:Network theory
* Category:Graph theory

* v
* t
* e

The Louvain method for community detection is a greedy optimization method intended to extract non-overlapping communities from large networks created by Blondel et al.[1] from the University of Louvain (the source of this method's name).

## Contents

* 1 Modularity optimization
* 2 Algorithm description
* 2.1 Modularity
* 2.2 The Louvain method algorithm
* 2.2.1 Phase 1
* 2.2.1.1 Each node in the network is assigned to its own community.
* 2.2.1.2 Nodes are grouped into communities
* 2.2.2 Phase 2
* 2.2.2.1 Communities are reduced to a single node
* 2.3 Time complexity
* 3 Previous uses
* 4 Disadvantages
* 5 Comparison to other methods of non-overlapping community detection
* 6 See also
* 7 References

## Modularity optimization

The inspiration for this method of community detection is the optimization of modularity as the algorithm progresses. Modularity is a scale value between −1 (non-modular clustering) and 1 (fully modular clustering) that measures the relative density of edges inside communities with respect to edges outside communities. Optimizing this value theoretically results in the best possible grouping of the nodes of a given network. But because going through all possible configurations of the nodes into groups is impractical, heuristic algorithms are used.

In the Louvain Method of community detection, first small communities are found by optimizing modularity locally on all nodes, then each small community is grouped into one node and the first step is repeated. The method is similar to the earlier method by Clauset, Newman and Moore[2] that connects communities whose amalgamation produces the largest increase in modularity. The Louvain algorithm was shown to correctly identify the community structure when it exists, in particular in the stochastic block model.[3]

## Algorithm description

### Modularity

The value to be optimized is modularity, defined as a value in the range [−1,1] that measures the density of links inside communities compared to links between communities.[1] For a weighted graph, modularity is defined as:

Q=12m∑i=1N∑j=1N[Aij−kikj2m]δ(ci,cj),

where:

* Aij represents the edge weight between nodes i and j; see Adjacency matrix;
* ki and kj are the sum of the weights of the edges attached to nodes i and j, respectively;
* m is the sum of all of the edge weights in the graph;
* N is the total number of nodes in the graph;
* ci and cj are the communities to which the nodes i and j belong; and
* δ is Kronecker delta function:

δ(ci,cj)={1if ci and cj are the same cluster0otherwise

Based on the above equation, the modularity of a community c can be calculated as:[4]

Qc=12m∑i∑jAij𝟏{ci=cj=c}−(∑iki2m𝟏{ci=c})2=Σin2m−(Σtot2m)2

where

* Σin is the sum of edge weights between nodes within the community c (each edge is considered twice); and
* Σtot is the sum of all edge weights for nodes within the community (including edges which link to other communities).

As nodes in different communities do not contribute to the modularity Q, it can be written as:

Q=∑cQc

### The Louvain method algorithm

The Louvain method works by repeating two phases.[1] In phase one, nodes are sorted into communities based on how the modularity of the graph changes when a node moves communities. In phase two, the graph is reinterpreted so that communities are seen as individual nodes. A detailed explanation is provided below.

#### Phase 1

Figure 1: Each node in the graph is randomly assigned to a singleton community

##### Each node in the network is assigned to its own community.

The Louvain method begins by considering each node v in a graph to be its own community. This can be seen in Figure 1, where each dot (representing nodes) is a unique color (representing which community the node belongs to).

##### Nodes are grouped into communities

For each node v, we consider how moving v from its current community C into a neighboring community C' will affect the modularity of the graph partition. In the pseudo-code below, this happens in the for-loop. We select the community C' with the greatest change in modularity, and if the change is positive, we move v into C'; otherwise we leave it where it is. This continues until the modularity stops improving.

Figure 2: Nodes are assigned to communities based on their modularities

function moveNodes(Graph G, Partition P):

old_modularity <- current_modularity_of_partition
for v in V(G), do
# find the community that causes the largest increase in modularity when v is moved into it
C' <- argmax(delta_Q) # delta_Q is the change in modularity
if delta_Q > 0, then
move v into C'
end if
end for
update current_modularity_of_partition
while current_modularity_of_partition > old_modularity
return P
end function

[5]

This process is applied repeatedly and sequentially to all nodes until no modularity increase can occur. Once this local maximum of modularity is hit, the first phase has ended. Figure 2 shows how the graph in Figure 1 might look after one iteration of phase 1.

#### Phase 2

##### Communities are reduced to a single node

For each community in our graph's partition, the individual nodes making up that community are combined and the community itself becomes a node. The edges connecting distinct communities are used to weight the new edges connecting our aggregate nodes.

This process is modeled in the pseudo-code, where the function aggregateGraph returns a new graph whose vertices are the partition of the old graph, and whose edges are calculated using the old graph. This function does not show the edges being weighted, but a simple modification would allow for that information to be tracked.

Figure 3: Communities are reduced to a single node with weighted edges

function aggregateGraph(Graph G, Partition P):
V <- P
E <- [(A,B) | (x,y) is in E(G), x is in A and A is in P, y is in B and B is in P]
return Graph(V,E)
end function

[5]

Figure 3 shows what the graph from Figure 2 would look like after being aggregated. This graph is analogous to the graph in Figure 1 in the sense that each node is assigned to a single community. From here, the process can be repeated so that more nodes are moved into existing communities until an optimal level of modularity is reached.

The pseudo-code below shows how the previous two functions work together to complete the process.

function louvain(Graph G, Partition P):

P <- moveNodes(G, P)
done <- length(P) == length(V(G)) # every community is a single node, despite running moveNodes
if not done, then:
G <- aggregateGraph(G, P)
P <- singletonPartition(G)
end if
while not done
end function

function singletonPartition(Graph G):
return [{v} | v is in V(G)] # each node is placed in its own community
end function

[5]

### Time complexity

Generally, the Louvain method is assumed to have a time complexity of O(nlog⁡n). Richard Blondel, co-author of the paper that originally published the Louvain method, seems to support this notion,[6] but other sources claim the time complexity is "essentially linear in the number of links in the graph,"[7] meaning the time complexity would instead be O(m), where m is the number of edges in the graph. Unfortunately, no source has published an analysis of the Louvain method's time complexity so one is attempted here.

In the pseudo-code above, the function louvain controls the execution of the algorithm. It's clear to see that inside of louvain, moveNodes will be repeated until it is no longer possible to combine nodes into communities. This depends on two factors: how much the modularity of the graph can improve and, in the worst case, if the modularity can improve with every iteration of louvain, it depends on how quickly aggregateGraph will reduce the graph down to a single node.

If, in each iteration of louvain, moveNodes is only able to move one node into a community, then aggregateGraph will only be able to reduce the size of the graph by one. This would cause louvain to repeat v times. Since moveNodes iterates through all nodes in a graph, this would result in a time complexity of 𝒪(n2), where n is the number of nodes.

It is unclear if this situation is possible, so the above result should be considered a loose bound. Blondel et al. state in their original publication that most of the run time is spent in the early iterations of the algorithm because "the number of communities decreases drastically after just a few passes."[1] This can be understood by considering a scenario where moveNodes is able to move each node so that every community has two nodes. In this case, aggregateGraph would return a graph half the size of the original. If this continued, then the Louvain method would have a runtime of nlog2n, although it is unclear if this would be the worst case, best case, average case, or none of those. Additionally, there is no guarantee the size of the graph would be reduced by the same factor with each iteration, and so no single logarithm function can perfectly describe the time complexity.

## Previous uses

* Twitter social Network (2.4 Million nodes, 38 million links) by Josep Pujol, Vijay Erramilli, and Pablo Rodriguez:[8] The authors explore the problem of partitioning Online Social Networks onto different machines.
* Mobile phone Network (4 Million nodes, 100 Million links) by Derek Greene, Donal Doyle, and Padraig Cunningham:[9] Community-tracking strategies for identifying dynamic communities of different dynamic social networks.
* Detecting species in network-based dynamical model.[10]

## Disadvantages

Louvain produces only non-overlapping communities, which means that each node can belong to at most one community. This is highly unrealistic in many real-world applications. For example, in social networks, most people belong to multiple communities: their family, their friends, their co-workers, old school buddies, etc. In biological networks, most genes or proteins belong to more than one pathway or complex. Furthermore, Louvain has been shown to sometimes produce arbitrarily badly connected communities, and has been effectively superseded (at least in the non-overlapping case) by the Leiden algorithm.

A graph illustrating how communities can become disconnected when using the Louvain algorithm.

A worst case example of an arbitrarily badly connected community is a internally disconnected community. An internally disconnected community arises through the Louvain algorithm when a node that had been acting as a "bridge" between two groups of nodes in its community is moved to a new community, leaving the old one disconnected. The remaining nodes in the old community may also be relocated, but if their connection to the community is strong enough despite the removal of the "bridge" node, they will instead remain in place. For an example of this, see the image to the right; note how the removal of the bridge node, node 0, caused the red community to be split into two disjoint subgroups. While this is the worst-case scenario, there are other, more subtle problems with the Louvain algorithm that can also lead to arbitrarily badly connected communities, such as the formation of communities using nodes that are only weakly connected.

An image depicting how the resolution limit of modularity can cause subcommunities to become hidden.

Another common issue with the Louvain algorithm is the resolution limit of modularity \- that is, multiple small communities being grouped together into a larger community. This causes the smaller communities to be hidden; for an example of this, see the visual depiction of the resolution limit to the right. Note how, when the green community is absorbed into the blue community to increase the graph's modularity, the smaller group of nodes that it represented is lost. There is no longer a way to differentiate those nodes from the nodes that were already in the blue community. Conversely, the nodes that were already in the blue community no longer appear distinct from those that were in the green community; in other words, whatever difference caused them to initially be placed in separate communities has been obscured.

Both the resolution limit of modularity and the arbitrarily badly connected community problem are further exasperated by each iteration of the algorithm. Ultimately, the only thing the Louvain algorithm guarantees is that the resulting communities cannot be merged further; in other words, they're well-separated. To avoid the problems that arise from arbitrarily badly connected communities and the resolution limit of modularity, it is recommended to use the Leiden algorithm instead, as its refinement phase and other various adjustments have corrected these issues.[5]

## Comparison to other methods of non-overlapping community detection

When comparing modularity optimization methods, the two measures of importance are the speed and the resulting modularity value. A higher speed is better as it shows a method is more efficient than others and a higher modularity value is desirable as it points to having better-defined communities. The compared methods are, the algorithm of Clauset, Newman, and Moore,[2] Pons and Latapy,[11] and Wakita and Tsurumi.[12]

Modularity Optimization Comparison[13] | Karate  | Arxiv  | Internet  | Web nd.edu  | Phone  | Web uk-2005  | Web WebBase 2001

|
|
|
|
|
|
|

Nodes/links  | 34/77 | 9k/24k | 70k/351k | 325k/1M | 2.6M/6.3M | 39M/783M | 118M/1B
Clauset, Newman, and Moore  | .38/0s | .772/3.6s | .692/799s | .927/5034s | -/- | -/- | -/-
Pons and Latapy  | .42/0s | .757/3.3s | .729/575s | .895/6666s | -/- | -/- | -/-
Wakita and Tsurumi  | .42/0s | .761/0.7s | .667/62s | .898/248s | .56/464s | -/- | -/-
Louvain Method  | .42/0s | .813/0s | .781/1s | .935/3s | .769/134s | .979/738s | .984/152mn

-/- in the table refers to a method that took over 24hrs to run. This table (from[1][14]) shows that the Louvain method outperforms many similar modularity optimization methods in both the modularity and the time categories.

## See also

* Leiden algorithm
* Modularity (networks)
* Community structure
* Network science
* K-means clustering

## References

1. ↑ 1.0 1.1 1.2 1.3 1.4 Blondel, Vincent D; Guillaume, Jean-Loup; Lambiotte, Renaud; Lefebvre, Etienne (9 October 2008). "Fast unfolding of communities in large networks". Journal of Statistical Mechanics: Theory and Experiment 2008 (10). doi:10.1088/1742-5468/2008/10/P10008. Bibcode: 2008JSMTE..10..008B.
2. ↑ 2.0 2.1 Clauset, Aaron; Newman, M. E. J.; Moore, Cristopher (2004-12-06). "Finding community structure in very large networks". Physical Review E 70 (6). doi:10.1103/PhysRevE.70.066111. ISSN 1539-3755. PMID 15697438. Bibcode: 2004PhRvE..70f6111C.
3. ↑ Cohen-Addad, Vincent; Kosowski, Adrian; Mallmann-Trenn, Frederik; Saulpic, David (2020). "Advances in Neural Information Processing Systems (Neurips 2020)". Curran Associates, Inc.. pp. 4055–4066.
4. ↑ Ghosh, Sayan; Halappanavar, Mahantesh; Tumeo, Antonino; Kalyanaraman, Ananth; Lu, Hao; Chavarría-Miranda, Daniel G.; Khan, Arif; Gebremedhin, Assefaw Hadish (2018). "2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21–25, 2018". IEEE Computer Society. pp. 885–895. doi:10.1109/IPDPS.2018.00098. ISBN 978-1-5386-4368-6.
5. ↑ 5.0 5.1 5.2 5.3 Traag, V. A.; Waltman, L.; van Eck, N. J. (2019-03-26). "From Louvain to Leiden: guaranteeing well-connected communities" (in en). Scientific Reports 9 (1): 5233. doi:10.1038/s41598-019-41695-z. ISSN 2045-2322. PMID 30914743. Bibcode: 2019NatSR...9.5233T.
6. ↑ "Louvain method for community detection". https://perso.uclouvain.be/vincent.blondel/research/louvain.html.
7. ↑ "Louvain - Analytics & Algorithms - Ultipa Graph". https://www.ultipa.com/document/ultipa-graph-analytics-algorithms/louvain/v4.5.
8. ↑ Pujol, Josep M.; Erramilli, Vijay; Rodriguez, Pablo (2009). "Divide and Conquer: Partitioning Online Social Networks". arXiv:0905.4918v1 [cs.NI].
9. ↑ Greene, Derek; Doyle, Dónal; Cunningham, Pádraig (May 2011). Tracking the Evolution of Communities in Dynamic Social Networks (PDF) (Technical report). University College Dublin. UCD-CSI-2011-06. Archived from the original (PDF) on 2013-05-12. Retrieved 2014-11-20.
10. ↑ Markovitch, Omer; Krasnogor, Natalio (2018). "Predicting species emergence in simulated complex pre-biotic networks". PLOS ONE 13 (2). doi:10.1371/journal.pone.0192871. PMID 29447212. Bibcode: 2018PLoSO..1392871M.
11. ↑ Pons, Pascal; Latapy, Matthieu (2006). "Computing Communities in Large Networks Using Random Walks". Journal of Graph Algorithms and Applications 10 (2): 191–218. doi:10.7155/jgaa.00124. http://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf.
12. ↑ Wakita, Ken; Tsurumi, Toshiyuki (2007). "Finding Community Structure in Mega-scale Social Networks". arXiv:cs/0702048.
13. ↑ Blondel, Vincent D.; Guillaume, Jean-Loup; Lambiotte, Renaud; Lefebvre, Etienne (2008). "Fast unfolding of communities in large networks". Journal of Statistical Mechanics: Theory and Experiment 2008 (10). doi:10.1088/1742-5468/2008/10/P10008. Bibcode: 2008JSMTE..10..008B.
14. ↑ Aynaud, Thomas; Blondel, Vincent D.; Guillaume, Jean-Loup; Lambiotte, Renaud (2013). "Multilevel Local Optimization of Modularity". in Bichot, Charles-Edmond (in en). Graph Partitioning (1 ed.). Wiley. 13 February 2013. pp. 315–345. doi:10.1002/9781118601181.ch13. ISBN 978-1-84821-233-6. https://onlinelibrary.wiley.com/doi/10.1002/9781118601181.ch13.

* "The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html

* v
* t
* e

Universities of Louvain/Leuven

1425-1797|

| Old University of Leuven|

* Faculty of Theology
* Collegium Trilingue
* Holy Ghost College
* Saint Ivo's College
* Pope's College
* Saint Anne's College
* St Anthony's College
* Trinity College
* Faculty
* Alumni

|

1817-1835|

* State University of Leuven

1834-1835|

* Catholic University of Mechlin

1835-1968|

| Catholic
University
of Louvain|

* Institutions: American College of the Immaculate Conception
* Lovanium University
* Faculty of Theology
Personalities: Pope Gregory XVI
* Rector Pierre de Ram
* Désiré-Joseph Mercier
* Rector Paulin Ladeuze
* Georges Lemaître
Nobel prizes: Auguste Beernaert
* Dominique Pire
Alumni
Belgian American Educational Foundation
* Sedes Sapientiae
* Split of the Catholic University of Louvain

|

Since 1968|

| UCLouvain|

| Campuses|

* Louvain-la-Neuve
* Brussels Woluwe
* FUCaM Mons
* Saint-Louis Brussels
* CHU Namur
* UCLouvain Charleroi

|

Cities|

* Louvain-la-Neuve
* Brussels
* Woluwe-Saint-Lambert
* Saint-Gilles
* Mons
* Tournai
* Charleroi
* Namur
* Dinant
* Yvoir

Faculties|

* Louvain School of Management
* Louvain School of Engineering
* Marie Haps Faculty of Translation and Interpreting
* Faculty of Economic, Social and Political Sciences and Communication
* Faculty of Architecture, Architectural Engineering and Urban Planning

Research|

* Higher Institute of Philosophy
* Cyclotron Research Center
* Center for Operations Research and Econometrics
* Centre for Research on the Epidemiology of Disasters
* Centre d'Etudes des Crises et Conflits Internationaux
* Hoover Chair
* Laboratory for the Analysis of Organisational Communication Systems

Hospitals|

* Cliniques universitaires Saint-Luc
* CHU UCLouvain Namur

Press|

* Presses universitaires de Louvain
* Revue Philosophique de Louvain
* International Philosophical Bibliography
* Cahiers de l'Institut de Linguistique de Louvain
* Revue d'Histoire Ecclésiastique
* Corpus Scriptorum Christianorum Orientalium

Subsidiary entities|

* Musée L
* Aula Magna
* Louvain-la-Neuve Cyclotron
* Louvain Coopération
* Louvain-la-Neuve Science Park
* Initialis Science Park
* Académie Louvain

Rectors|

* Pierre Macq
* Bernard Coulie
* Vincent Blondel

Nobel prizes|

* Christian de Duve
* Albert Claude

Miscellaneous|

* Louvain modularity
* Orchestre Symphonique des Étudiants de Louvain-la-Neuve
* 24h vélo de Louvain-la-Neuve
* Progressive Congolese Students
* ANLO
* Oz
* Ekiga
* Ion Beam Applications
* Kot-à-projet

* Faculty
* Alumni

KU Leuven|

| Campuses|

KULAK

|

Cities|

* Leuven
* Kortrijk
* Antwerp
* Ghent
* Bruges
* Geel
* Diepenbeek
* Aalst
* Sint-Katelijne-Waver
* Brussels

Faculties|

* Institute of Philosophy

Research|

* Leuven Centre for Global Governance Studies
* Rega Institute for Medical Research
* Switch Laboratory

Hospitals|

* UZ Leuven

Press|

* Leuven University Press
* Revue d'Histoire Ecclésiastique
* ITL – International Journal of Applied Linguistics

Subsidiary entities|

* Arenberg Castle
* Arenberg Research-Park
* KU Leuven Association

Rectors|

* Pieter De Somer
* Marc Vervenne
* Mark Waer
* Rik Torfs
* Luc Sels

Other|

* Evangelical Theological Faculty

Academic libraries in Leuven · Universities in Leuven

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Louvain method. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Louvain_method&oldid=4150902"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template