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 $O(n\log n)$ .

Histoire

La méthode a été développée en mars 2007 par Étienne Lefebvre dans le cadre de son travail de fin d’étude présenté en août 2007. La méthode est ensuite testée et publiée entre 2007 et 2008 par Vincent Blondel (qui deviendra plus tard recteur de l'UCLouvain), 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 :

$Q={\frac {1}{2m}}\sum \limits _{ij}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),$

où :

$A_{ij}$ représente le poids de l'arête entre les nœuds $i$ et $j$ ;
$k_{i}$ et $k_{j}$ sont la somme des poids des arêtes liées aux nœuds $i$ et $j$ respectivement ;
$m$ est la somme de l'ensemble des poids des arêtes du graphe ;
$c_{i}$ et $c_{j}$ sont les communautés de nœuds ;
$\delta$ 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 $i$ , on calcule le changement de modularité occasionné par la suppression de $i$ de sa propre communauté et son déplacement dans la communauté de chacun des voisins $j$ de $i$ . Cette valeur est calculée en deux étapes : (1) la suppression de $i$ de sa communauté d'origine, et (2) l'insertion de $i$ communauté de $j$ . Les deux équations sont assez similaires, et l'équation pour l'étape (2) est :

$\Delta Q={\bigg [}{\frac {\Sigma _{in}+k_{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 ]}$

Ici, $\Sigma _{in}$ est la somme des poids des arêtes à l'intérieur de la communauté de destination de $i$ , $\Sigma _{tot}$ est la somme des poids de toutes les arêtes liées aux nœuds de la communauté de destination de $i$ , $k_{i}$ est le degré pondéré de $i$ , $k_{i,in}$ est la somme des poids des arêtes entre $i$ et les autres nœuds de la communauté de destination de $i$ , et $m$ 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 $i$ est connecté, $i$ est placé dans la communauté qui entraine la plus grande augmentation de la modularité. Si aucune augmentation n'est possible, $i$ 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
Nombre de nœuds du graphe	34	9k	70k	325k	2.6M	39M	118M
Nombre d'arêtes du graphe	77	24k	351K	1M	6.3M	783M	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 $G=(V,A)$ , Leicht and Newman ^[11] ont proposé une définition

$Q_{d}={\frac {1}{m}}\sum \limits _{ij}{\bigg [}A_{ij}-{\frac {k_{i}^{in}k_{j}^{out}}{m}}{\bigg ]}\delta (c_{i},c_{j}),$

avec $k_{i}^{in}$ resp. $k_{j}^{out}$ la somme des arcs orientés entrants en $i$ resp. sortants de $j$ .

Dugué et Perez adaptent l'algorithme de Louvain pour optimiser la modularité $Q_{d}$ , 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, n^o 10,‎ 9 octobre 2008, 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, n^o 6,‎ 6 décembre 2004 (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 12 mai 2013] (consulté le 20 novembre 2014)
↑ (en) Cristopher Moore, « Finding community structure in very large networks », Physical Review E, vol. 70, n^o 6,‎ 6 décembre 2004, p. 066111 (DOI 10.1103/PhysRevE.70.066111, lire en ligne, consulté le 17 août 2020).
↑ http://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf
↑ Tsurumi, Toshiyuki, « Finding Community Structure in Mega-scale Social Networks », sur arXiv.org, 8 février 2007 (consulté le 17 août 2020).
↑ 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, n^o 11,‎ 2008, p. 118703 (PMID 18517839, DOI 10.1103/PhysRevLett.100.118703, Bibcode 2008PhRvL.100k8703L, arXiv 0709.4500, S2CID 19968041)
↑ (en) Nicolas Dugué et A. Perez Directed Louvain: maximizing modularity in directed networks. (rapport), 2015 (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,‎ octobre 2022, p. 127798 (DOI 10.1016/j.physa.2022.127798, lire en ligne)

"The Louvain method for community detection in large networks", Vincent Blondel

[Louvain-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, n^o 10,‎ 9 octobre 2008, 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, n^o 6,‎ 6 décembre 2004 (ISSN 1539-3755, DOI 10.1103/PhysRevE.70.066111, Bibcode 2004PhRvE..70f6111C, arXiv cond-mat/0408187)

[Louvain_arxiv_2008-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] ttps://arxiv.org/pdf/0905.4918v1.pdf

[5] « Archived copy » [archive du 12 mai 2013] (consulté le 20 novembre 2014)

[6] (en) Cristopher Moore, « Finding community structure in very large networks », Physical Review E, vol. 70, n^o 6,‎ 6 décembre 2004, p. 066111 (DOI 10.1103/PhysRevE.70.066111, lire en ligne, consulté le 17 août 2020).

[7] ttp://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf

[8] Tsurumi, Toshiyuki, « Finding Community Structure in Mega-scale Social Networks », sur arXiv.org, 8 février 2007 (consulté le 17 août 2020).

[9] ttps://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.

[Directed_modularity-11] E. A. Leicht et M. E. J. Newman, « Community Structure in Directed Networks », Physical Review Letters, vol. 100, n^o 11,‎ 2008, p. 118703 (PMID 18517839, DOI 10.1103/PhysRevLett.100.118703, Bibcode 2008PhRvL.100k8703L, arXiv 0709.4500, S2CID 19968041)

[Directed_Louvain-12] (en) Nicolas Dugué et A. Perez Directed Louvain: maximizing modularity in directed networks. (rapport), 2015 (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,‎ octobre 2022, p. 127798 (DOI 10.1016/j.physa.2022.127798, lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]