Modularité (réseaux)

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

${\displaystyle 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 ${\displaystyle \delta }$ est le delta de Kronecker qui vaut 1 si ses arguments sont égaux et 0 sinon.

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 ${\displaystyle -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. ${\displaystyle A_{ii}=0}$), la modularité vaut:

${\displaystyle 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}$

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].

• (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)