Modularité (réseaux)

La modularité est une mesure de la qualité d'un partitionnement des nœuds d'un graphe, ou réseau, en communautés (ou classes). Elle est principalement utilisée en analyse des réseaux sociaux. Elle a été introduite par M. E. J. Newman en 2004[1]. C'est aussi une fonction d'optimisation pour certaines tâches de détection de communautés dans les graphes.

Le principe est qu'un bon partitionnement d'un graphe implique un nombre d'arêtes intra-communautaires important et un nombre d'arêtes inter-communautaires faible.

La modularité est décrite comme la proportion des arêtes incidentes sur une classe donnée moins la valeur qu'aurait été cette même proportion si les arêtes étaient disposées au hasard entre les nœuds du graphe. La modularité prend ses valeurs entre $-1/2$ et $1$ inclus[2]. On peut considérer qu'un graphe a une structure de communautés significative quand une partition obtient un score de modularité supérieur à 0,3.

Formule

La modularité d'un partitionnement $c$ (où $c_{i}$ indique la classe attribuée au nœud $i$ ), s'exprime de la manière suivante :

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

où A_ij est la valeur de la matrice d'adjacence entre les sommets i et j, k_i est la somme des poids des arêtes adjacentes à i, m est le nombre d'arêtes du graphe et $\delta$ est le delta de Kronecker qui vaut 1 si ses arguments sont égaux et 0 sinon.

Valeurs remarquables

La modularité est positive pour un graphe et une partition pour lesquels il n'y a aucune arête reliant 2 nœuds de classes différentes mais au moins une arête reliant 2 nœuds de la même classe.

La modularité est négative pour un graphe et une partition pour lesquels il n'y a aucune arête reliant 2 nœuds de la même classe mais au moins une arête reliant 2 nœuds de classes différentes.

La modularité tend vers 0 lorsque l'on partitionne aléatoirement un graphe dans lequel les arêtes sont distribuées aléatoirement.

La modularité vaut $-1/2$ pour un graphe à deux nœuds reliés par une seule arête où chacun des nœuds est placé dans sa propre communauté[2].

La modularité vaut 1 pour des graphes sans arêtes[2].

Et dans le cas d'une clique à n nœuds où tous les nœuds sont dans la même communauté (les noeuds ne sont pas liés à eux-mêmes, i.e. $A_{ii}=0$ ), la modularité vaut:

$Q={\frac {1}{2.{\frac {n(n-1)}{2}}}}\left(\sum _{ij,i\neq j}\left[1-{\frac {(n-1)^{2}}{2.{\frac {n(n-1)}{2}}}}\right]\times 1+\sum _{ij,i=j}\left[0-{\frac {(n-1)^{2}}{2.{\frac {n(n-1)}{2}}}}\right]\times 1\right)={\frac {1}{n(n-1)}}\left((n^{2}-n)\left[1-{\frac {n-1}{n}}\right]+n\left[0-{\frac {n-1}{n}}\right]\right)=0$

Critiques

Un reproche souvent levé à l'encontre de la modularité est sa limite de résolution. En effet, si l'on est confronté à des communautés de tailles différentes à l'intérieur d'un même graphe, certaines communautés, même bien définies, pourront ne pas être distinguées dans la partition de modularité optimale.

Il est également reproché à la modularité de présenter de nombreux minima locaux ce qui le rend difficile à optimiser. De plus, la modularité peut présenter deux minima très proches en valeur pour deux partition très différentes[3].

Notes et références

(en) M.E.J. Newman, « Modularity and community structure in networks », PNAS,‎ 6 juin 2006, p. 8577 - 8582 (lire en ligne [PDF])
(en) Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Höfer, Zoran Nikoloski et Dorothea Wagner, « On modularity clustering », IEEE, vol. 20,‎ 26 décembre 2007, p. 2 (DOI 10.1109/TKDE.2007.190689, lire en ligne [PDF], consulté le 15 décembre 2021)
(en) Benjamin H. Good, Yves-Alexandre et Aaron Clauset, « The performance of modularity maximization in practical contexts », Physical Review E.,‎ 15 avril 2010, p. 7 (lire en ligne [PDF], consulté le 24 février 2022)

Bibliographie

(en) M. E. J. Newman, « Modularity and community structure in networks », Proc. Natl. Acad. Sci. USA, vol. 103, n^o 23,‎ 2006, p. 8577–8582 (PMID 16723398, PMCID 1482622, DOI 10.1073/pnas.0601602103, lire en ligne, consulté le 11 juillet 2008)

Portail des sciences

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) M.E.J. Newman, « Modularity and community structure in networks », PNAS,‎ 6 juin 2006, p. 8577 - 8582 (lire en ligne [PDF])

[:0-2] (en) Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Höfer, Zoran Nikoloski et Dorothea Wagner, « On modularity clustering », IEEE, vol. 20,‎ 26 décembre 2007, p. 2 (DOI 10.1109/TKDE.2007.190689, lire en ligne [PDF], consulté le 15 décembre 2021)

[3] (en) Benjamin H. Good, Yves-Alexandre et Aaron Clauset, « The performance of modularity maximization in practical contexts », Physical Review E.,‎ 15 avril 2010, p. 7 (lire en ligne [PDF], consulté le 24 février 2022)