AccueilđŸ‡«đŸ‡·Chercher

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

  • 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 social Twitter (2,4 millions de nƓuds, 38 millions de liens) par Josep Pujol, Vijay Erramilli, et Pablo Rodriguez[4]
  • 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].

Comparaison de méthodes d'optimisation de la modularité[9]
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

  1. 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)
  2. 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)
  3. 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
  4. https://arxiv.org/pdf/0905.4918v1.pdf
  5. « Archived copy » [archive du ] (consulté le )
  6. (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 ).
  7. http://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf
  8. Tsurumi, Toshiyuki, « Finding Community Structure in Mega-scale Social Networks », sur arXiv.org, (consulté le ).
  9. https://arxiv.org/pdf/0803.0476v2.pdf
  10. 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.
  11. 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)
  12. Nicolas Dugué et A. Perez, Directed Louvain: maximizing modularity in directed networks., (lire en ligne)
  13. (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)
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.