Modularité (réseaux)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La modularité est une mesure pour la qualité d'un partitionnement des nœuds d'un graphe, ou réseau, en communautés. Elle est principalement utilisée en analyse des réseaux sociaux. Elle a été introduite par M. E. J. Newman. 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 et 1 inclus. 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[modifier | modifier le code]


Q = \sum_{ij} \left[ \frac {A_{ij}}{2m} - \frac{k_i*k_j}{(2m)(2m)} \right] \delta(c_{i}, c_{j})

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

Valeurs remarquables[modifier | modifier le code]

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

La modularité vaut -1 pour un graphe et une partition pour lesquels il n'y a aucune arête reliant 2 noeuds de la même classe mais au moins une arête reliant 2 noeuds 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.

Critiques[modifier | modifier le code]

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.

Référence[modifier | modifier le code]