Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1 handwiki -- 1039 2022-11-10 01:40:36

Video Upload Options

Do you have a full video?

Confirm

Are you sure to Delete?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. Louvain Modularity. Encyclopedia. Available online: https://encyclopedia.pub/entry/33791 (accessed on 27 July 2024).
HandWiki. Louvain Modularity. Encyclopedia. Available at: https://encyclopedia.pub/entry/33791. Accessed July 27, 2024.
HandWiki. "Louvain Modularity" Encyclopedia, https://encyclopedia.pub/entry/33791 (accessed July 27, 2024).
HandWiki. (2022, November 10). Louvain Modularity. In Encyclopedia. https://encyclopedia.pub/entry/33791
HandWiki. "Louvain Modularity." Encyclopedia. Web. 10 November, 2022.
Louvain Modularity
Edit

The Louvain Method for community detection is a method to extract communities from large networks created by Blondel et al. from the University of Louvain (affiliation of authors has given the method its name). The method is a greedy optimization method that appears to run in time [math]\displaystyle{ O(n \log n) }[/math].

community detection large networks louvain

1. 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 and 1 that measures the density of edges inside communities to edges outside communities. Optimizing this value theoretically results in the best possible grouping of the nodes of a given network, however going through all possible iterations of the nodes into groups is impractical so 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[1] that connects communities whose amalgamation produces the largest increase in modularity.

2. Algorithm

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

[math]\displaystyle{ Q = \frac{1}{2m}\sum\limits_{ij}\bigg[A_{ij} - \frac{k_i k_j}{2m}\bigg]\delta (c_i,c_j), }[/math]

where

  • [math]\displaystyle{ A_{ij} }[/math] represents the edge weight between nodes [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math];
  • [math]\displaystyle{ k_i }[/math] and [math]\displaystyle{ k_j }[/math] are the sum of the weights of the edges attached to nodes [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math], respectively;
  • [math]\displaystyle{ 2m }[/math] is the sum of all of the edge weights in the graph;
  • [math]\displaystyle{ c_i }[/math] and [math]\displaystyle{ c_j }[/math] are the communities of the nodes; and
  • [math]\displaystyle{ \delta }[/math] is a simple delta function.

In order to maximize this value efficiently, the Louvain Method has two phases that are repeated iteratively.

First, each node in the network is assigned to its own community. Then for each node [math]\displaystyle{ i }[/math], the change in modularity is calculated for removing [math]\displaystyle{ i }[/math] from its own community and moving it into the community of each neighbor [math]\displaystyle{ j }[/math] of [math]\displaystyle{ i }[/math]. This value is easily calculated by two steps: (1) removing [math]\displaystyle{ i }[/math] from its original community, and (2) inserting [math]\displaystyle{ i }[/math] to the community of [math]\displaystyle{ j }[/math]. The two equations are quite similar, and the equation for step (2) is: [2]

[math]\displaystyle{ \Delta Q = \bigg[ \frac{\Sigma_{in} + 2k_{i,in}}{2m} - \bigg(\frac{\Sigma_{tot} + k_i}{2m}\bigg)^2 \bigg]-\bigg[\frac{\Sigma_{in}}{2m} - \bigg(\frac{\Sigma_{tot}}{2m}\bigg)^2-\bigg(\frac{k_i}{2m}\bigg)^2\bigg] }[/math]

Where [math]\displaystyle{ \Sigma_{in} }[/math] is sum of all the weights of the links inside the community [math]\displaystyle{ i }[/math] is moving into, [math]\displaystyle{ \Sigma_{tot} }[/math] is the sum of all the weights of the links to nodes in the community [math]\displaystyle{ i }[/math] is moving into, [math]\displaystyle{ k_i }[/math] is the weighted degree of [math]\displaystyle{ i }[/math], [math]\displaystyle{ k_{i,in} }[/math] is the sum of the weights of the links between [math]\displaystyle{ i }[/math] and other nodes in the community that [math]\displaystyle{ i }[/math] is moving into, and [math]\displaystyle{ m }[/math] is the sum of the weights of all links in the network. Then, once this value is calculated for all communities [math]\displaystyle{ i }[/math] is connected to, [math]\displaystyle{ i }[/math] is placed into the community that resulted in the greatest modularity increase. If no increase is possible, [math]\displaystyle{ i }[/math] remains in its original community. 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.

In the second phase of the algorithm, it groups all of the nodes in the same community and builds a new network where nodes are the communities from the previous phase. Any links between nodes of the same community are now represented by self loops on the new community node and links from multiple nodes in the same community to a node in a different community are represented by weighted edges between communities. Once the new network is created, the second phase has ended and the first phase can be re-applied to the new network.

3. Previous Uses

  • Twitter social Network (2.4 Million nodes, 38 million links) by Josep Pujol, Vijay Erramilli, and Pablo Rodriguez:[3] 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:[4] Community-tracking strategies for identifying dynamic communities of different dynamic social networks.
  • Detecting species in network-based dynamical model.[5]

4. Comparison to Other Methods

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,[6] Pons and Latapy,[7] and Watika and Tsurumi.[8]

Modularity Optimization Comparison[9]
  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 -/- -/- -/-
Watike and Tsurmi .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 [10][11]) shows that the Louvain method outperforms many similar modularity optimization methods in both the modularity and the time categories.

References

  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. Bibcode: 2004PhRvE..70f6111C.  https://dx.doi.org/10.1103%2FPhysRevE.70.066111
  2. 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: https://arxiv.org/abs/0803.0476
  3. https://arxiv.org/pdf/0905.4918v1.pdf
  4. "Archived copy". Archived from the original on 2013-05-12. https://web.archive.org/web/20130512153616/http://www.csi.ucd.ie/files/ucd-csi-2011-06.pdf. Retrieved 2014-11-20. 
  5. Markovitch, Omer; Krasnogor, Natalio. "Predicting species emergence in simulated complex pre-biotic networks". PLoS ONE 13 (2): e0192871. doi:10.1371/journal.pone.0192871. http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0192871. 
  6. http://journals.aps.org/pre/abstract/10.1103/PhysRevE.70.066111
  7. http://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf
  8. https://arxiv.org/abs/cs/0702048
  9. https://arxiv.org/pdf/0803.0476v2.pdf
  10. 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): P10008. doi:10.1088/1742-5468/2008/10/P10008. Bibcode: 2008JSMTE..10..008B.  https://dx.doi.org/10.1088%2F1742-5468%2F2008%2F10%2FP10008
  11. Multilevel local optimization of modularity, T. Aynaud, V.D. Blondel, J.-L. Guillaume, R. Lambiotte - in Graph Partitioning, 315-345, Publisher John Wiley & Sons, 2011.
More
Information
Subjects: Others
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
View Times: 510
Entry Collection: HandWiki
Revision: 1 time (View History)
Update Date: 10 Nov 2022
1000/1000
Video Production Service