MĂ©thode de Louvain
La méthode de Louvain est un algorithme hiérarchique d'extraction de communautés applicable à de grands réseaux. La méthode a été proposée par Vincent Blondel et al.[1] de l'Université de Louvain en 2008. Il s'agit d'un algorithme glouton avec une complexité temporelle de .
Histoire
La mĂ©thode a Ă©tĂ© dĂ©veloppĂ©e en mars 2006 par Etienne Lefebvre dans le cadre de son travail de fin dâĂ©tude. La mĂ©thode est ensuite testĂ©e et publiĂ©e entre 2006 et 2008 par Vincent Blondel, actuel recteur de l'universitĂ© catholique de Louvain, Jean-Loup Guillaume, Ătienne Lefebvre et Renaud Lambiotte, chercheurs postdoctoraux. Elle doit son nom Ă l'UCLouvain et son Ă©cole polytechnique et Ă la ville de Louvain-la-Neuve, oĂč elle a Ă©tĂ© rĂ©digĂ©e.
Optimisation de la modularité
La mĂ©thode permet d'effectuer le partitionnement d'un rĂ©seau en optimisant la modularitĂ©. La modularitĂ© est une valeur comprise entre -1/2 et 1 qui mesure la densitĂ© d'arĂȘtes Ă l'intĂ©rieur des communautĂ©s comparĂ©e Ă celle des arĂȘtes reliant les communautĂ©s entre elles. L'optimisation de la modularitĂ© conduit thĂ©oriquement au meilleur partitionnement possible, cependant son calcul effectif pour chacun des groupements de nĆuds possibles est trop long en pratique, d'oĂč l'utilisation d'algorithmes heuristiques. La premiĂšre phase de la mĂ©thode de Louvain consiste Ă trouver de petites communautĂ©s par optimisation locale de la modularitĂ© sur chacun des nĆuds. Dans un second temps, les nĆuds d'une mĂȘme communautĂ© sont regroupĂ©s en un unique nĆud, et la premiĂšre phase est rĂ©pĂ©tĂ©e sur le rĂ©seau nouvellement obtenu. La mĂ©thode est similaire Ă la mĂ©thode antĂ©rieure proposĂ©e par Clauset, Newman et Moore[2], qui amalgame les communautĂ©s dont la fusion produit la plus grande augmentation de la modularitĂ©.
Algorithme
La valeur Ă optimiser est la modularitĂ©, dĂ©finie entre -1/2 et 1, et mesurant la densitĂ© des arĂȘtes Ă l'intĂ©rieur des communautĂ©s par rapport Ă la densitĂ© des arĂȘtes entre les communautĂ©s[3]. Pour un graphe pondĂ©rĂ©, la modularitĂ© Q est dĂ©finie comme :
oĂč :
- reprĂ©sente le poids de l'arĂȘte entre les nĆuds et ;
- et sont la somme des poids des arĂȘtes liĂ©es aux nĆuds et respectivement ;
- est la somme de l'ensemble des poids des arĂȘtes du graphe ;
- et sont les communautĂ©s de nĆuds ;
- est une fonction delta.
Afin de maximiser cette valeur de maniÚre efficace, la méthode de Louvain a deux phases qui se répÚtent de maniÚre itérative.
Tout d'abord, chaque nĆud du rĂ©seau est affectĂ© Ă sa propre communautĂ©. Ensuite, pour chaque nĆud , on calcule le changement de modularitĂ© occasionnĂ© par la suppression de de sa propre communautĂ© et son dĂ©placement dans la communautĂ© de chacun des voisins de . Cette valeur est calculĂ©e en deux Ă©tapes : (1) la suppression de de sa communautĂ© d'origine, et (2) l'insertion de communautĂ© de . Les deux Ă©quations sont assez similaires, et l'Ă©quation pour l'Ă©tape (2) est :
Ici, est la somme des poids des arĂȘtes Ă l'intĂ©rieur de la communautĂ© de destination de , est la somme des poids de toutes les arĂȘtes liĂ©es aux nĆuds de la communautĂ© de destination de , est le degrĂ© pondĂ©rĂ© de , est la somme des poids des arĂȘtes entre et les autres nĆuds de la communautĂ© de destination de , et est la somme des poids de l'ensemble des arĂȘtes du graphe. Ensuite, une fois cette valeur calculĂ©e pour toutes les communautĂ©s auxquelles est connectĂ©, est placĂ© dans la communautĂ© qui entraine la plus grande augmentation de la modularitĂ©. Si aucune augmentation n'est possible, reste dans sa communautĂ© d'origine. Ce processus est appliquĂ© de maniĂšre rĂ©pĂ©tĂ©e et sĂ©quentielle sur tous les nĆuds jusqu'Ă ce qu'aucune augmentation de la modularitĂ© ne se produise. Une fois que ce maximum local est atteint, la premiĂšre phase se termine.
Dans la seconde phase de l'algorithme, tous les nĆuds d'une mĂȘme communautĂ© sont regroupĂ©s, et un nouveau rĂ©seau est construit oĂč les nĆuds sont les communautĂ©s de la phase prĂ©cĂ©dente. Les arĂȘtes entre les nĆuds d'une mĂȘme communautĂ© sont reprĂ©sentĂ©s par des boucles sur le nouveau nĆud, et les arĂȘtes d'une communautĂ© Ă une autre sont reprĂ©sentĂ©es par des arĂȘtes pondĂ©rĂ©es. Une fois le nouveau rĂ©seau crĂ©Ă©, la seconde phase se termine et la premiĂšre phase peut ĂȘtre appliquĂ©e de nouveau sur le rĂ©seau rĂ©sultant.
Utilisations
- RĂ©seau social Twitter (2,4 millions de nĆuds, 38 millions de liens) par Josep Pujol, Vijay Erramilli, et Pablo Rodriguez[4].Visualisation d'un sous-rĂ©seau d'interactions sociales sur Twitter, usant de la mĂ©thode louvain pour dĂ©tecter des "communautĂ©s"
- RĂ©seau de tĂ©lĂ©phonie mobile (4 millions de nĆuds, de 100 millions de liens) par Derek Greene, Donal Doyle, et Padraig Cunningham[5].
Comparaison à d'autres méthodes
Lors de la comparaison des mĂ©thodes d'optimisation de la modularitĂ©, les deux mesures d'importance sont la vitesse de calcul et la valeur de la modularitĂ©. Une vitesse Ă©levĂ©e permet Ă la mĂ©thode d'ĂȘtre adaptĂ©e pour traiter de larges volumes de donnĂ©es. Une modularitĂ© Ă©levĂ©e indique des communautĂ©s mieux dĂ©finies. Les mĂ©thodes comparĂ©es sont l'algorithme de Clauset, Newman, et Moore[6], Pons et Latapy[7], et Watika et Tsurumi[8].
Karate | Arxiv | Internet | Web nd.edu | Téléphone | Web uk-2005 | Web WebBase 2001 | |
---|---|---|---|---|---|---|---|
NĆuds / arĂȘtes | 34/77 | 9k/24k | 70k/351 ko | 325k/1M | 2.6 M/6.3 M | 39M/783M | 118M/1B |
Clauset, Newman et Moore | .38/0s | .772/3.6 s | .692/799s | .927/5034s | -/- | -/- | -/- |
Pons et Latapy | .42/0s | .757/3.3 s | .729/575s | .895/6666s | -/- | -/- | -/- |
Watike et Tsurmi | .42/0s | .761/0,7 s | .667/62s | .898/248s | .56/464s | -/- | -/- |
MĂ©thode de Louvain | .42/0s | .813/0s | .781/1s | .935/3s | .769/134s | .979/738s | .984/152 min |
-/- dans le tableau signifie que la méthode a pris plus de 24 heures pour s'exécuter. Ce tableau[10] montre que la méthode de Louvain surpasse de nombreuses méthodes d'optimisation de la modularité similaires, tant en termes de modularité qu'en temps de calcul.
Dans les graphes orientés
Dans le cas de graphe avec des arĂȘtes orientĂ©es , Leicht and Newman [11] ont proposĂ© une dĂ©finition
avec resp. la somme des arcs orientés entrants en resp. sortants de .
Dugué et Perez adaptent l'algorithme de Louvain pour optimiser la modularité , démontrant les performances de l'algorithme et sa pertinence dans le cadre orienté [12] - [13].
Voir aussi
Références
- (en) Cet article est partiellement ou en totalitĂ© issu de lâarticle de WikipĂ©dia en anglais intitulĂ© « Louvain Modularity » (voir la liste des auteurs).
- Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte et Etienne Lefebvre, « Fast unfolding of communities in large networks », Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no 10,â , P10008 (DOI 10.1088/1742-5468/2008/10/P10008, Bibcode 2008JSMTE..10..008B, arXiv 0803.0476)
- Aaron Clauset, M. E. J. Newman et Cristopher Moore, « Finding community structure in very large networks », Physical Review E, vol. 70, no 6,â (ISSN 1539-3755, DOI 10.1103/PhysRevE.70.066111, Bibcode 2004PhRvE..70f6111C, arXiv cond-mat/0408187)
- Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Ătienne 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
- https://arxiv.org/pdf/0905.4918v1.pdf
- « Archived copy » [archive du ] (consulté le )
- (en) Cristopher Moore, « Finding community structure in very large networks », Physical Review E, vol. 70, no 6,â , p. 066111 (DOI 10.1103/PhysRevE.70.066111, lire en ligne, consultĂ© le ).
- http://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf
- Tsurumi, Toshiyuki, « Finding Community Structure in Mega-scale Social Networks », sur arXiv.org, (consulté le ).
- https://arxiv.org/pdf/0803.0476v2.pdf
- 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.
- E. A. Leicht et M. E. J. Newman, « Community Structure in Directed Networks », Physical Review Letters, vol. 100, no 11,â , p. 118703 (PMID 18517839, DOI 10.1103/PhysRevLett.100.118703, Bibcode 2008PhRvL.100k8703L, arXiv 0709.4500, S2CID 19968041)
- Nicolas Dugué et A. Perez, Directed Louvain: maximizing modularity in directed networks., (lire en ligne)
- (en) Nicolas DuguĂ© et Anthony Perez, « Direction matters in complex networks: A theoretical and applied study for greedy modularity optimization », Physica A: Statistical Mechanics and its Applications, vol. 603,â , p. 127798 (DOI 10.1016/j.physa.2022.127798, lire en ligne)
- "The Louvain method for community detection in large networks", Vincent Blondel