User Tools

Site Tools


chicoutimi_2016:clustering_graphes_modularites

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / Session by session cutdown

Clustering de graphes: modularités

Le terme modularité est maintenant utilisé pour désigner une mesure ravivée par Mark Newman bien que le terme décrit un concept présent dans nombre de domaines.

Pour ce qui concerne l'analyse de réseaux, la modularité est une mesure de la qualité d'un partitionnement des sommets d'un graphe, par rapport à une distribution des arêtes C_i$.

On définit les quantités:

  • la proportion d'arêtes qui connectent des sommets de et . Plus précisément:
  • La quantité est donc proportionnelle au nombre d'arêtes internes au cluster .
  • est la proportion d'arêtes incidentes au cluster (y compris les arêtes internes à .

La modularité du clustering est égale à:

La quantité correspond à une distribution “au hasard” des arêtes du graphes, tout en respectant la distribution du nombre d'arêtes incidents à chacun des clusters . En effet, prenant une arête, on peut choisit au hasard le cluster “source” auquel elle est incidente avec une distribution de probabilité ; puis ce cluster étant arrêté, on choisit au hasard vers quel cluster “cible” elle va avec une distribution de probabilité .

On obtient une valeur positive de lorsqu'on s'éloigne d'une distribution “au hasard” des arêtes. Une valeur nulle ou négative est signe d'un mauvais découpage du graphe.

La modularité admet aussi une autre formulaiton, fonction des entrées la matrice d'adjacence et des degrés des sommets .

où désigne le cluster auquel appartient le sommet , et si et seulement si , c'est-à-dire que les sommets sont du même cluster, et 0 sinon.

La modularité de Newman admet une propriété qui rend son calcul “abordable”.

  • On peut calculer l'incidence du déplacement d'un sommet isolé (formant un cluster à lui seul) dans un cluster . On calcule le des modularités:

où est obtenu de en déplaçant le sommet isolé vers le cluster :

où:

  • désigne le nombre (les poids des) d'arêtes incidentes à dans ;
  • désigne les poids des arêtes internes à ;
  • désigne les poids des arêtes incidentes (interns ou externes) à ;
  • On calcule une formule similaire correspondant au fait de “sortir” un sommet d'un cluster.
  • On peut donc facilement calculer le du déplacement d'un sommet d'un cluster à un autre (on le “sort”, puis on déplace ce sommet nouvellement isolé dan sun nouveau cluster).

Une autre mesure introduite par Mancoridis et al. cerne cette notion:

  • Mancoridis, S. et al. (1998). Using automatic clustering to produce high-level system organizations of source code. IEEE International Workshop on Program Understanding (IWPC’98).

Le premier terme calcule la densité interne moyenne des clusters, alors que le second terme calcule la densité externe.

La mesure de Mancoridis possède certaines propriétés utiles:

  • Elle varie dans l'intervalle .
  • Sa moyenne approche -0.2, son écart-type 0.2 et elle peut être estimée par un loi normale.
  • La version de Mancoridis correspond au cas des graphes orientés. On peut l'adapter au cas des graphes non orientés.
  • On peut aussi introduire une version où les moyennes sont pondérées.
    • Queyroi, F. et al. (2014). “Assessing the quality of multilevel graph clustering.” Data Mining and Knowledge Discovery 28(4): 1107-1128.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/clustering_graphes_modularites.txt · Last modified: 2016/05/16 04:23 by melancon