User Tools

Site Tools


chicoutimi_2016:algorithmes_de_girvan-newman

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / Session by session cutdown

Algorithmes de Girvan-Newman

Dans une série de papier Michelle Girvan et Mark Newman ont introduit des approches pour partitionner les graphes permettant d'y identifier des communautés: un découpage des sommets en sous-ensembles distincts, des clusters tels que et .

Algorithme divisif
  • Newman, M. E. J. and M. Girvan (2004). “Finding and evaluating community structure in networks.” Physics Reviews E 69(026113).

La littérature est bavarde sur ce sujet.

  • Auber, D., Y. Chiricota, et al. (2003). Multiscale navigation of Small World Networks. IEEE Symposium on Information Visualisation, Seattle, GA, USA, IEEE Computer Science Press, 75-81.
  • Chiricota, Y. and G. Melançon (2007). “Visually mining relational data.” International Review on Computers and Software 2(3).

Le principe de l'algorithme est simple:

  • Une arête du graphe est “supprimer” à chaque itération. On itère jusqu'à épuisement des arêtes.
    • A chaque itération le choix de l'arête à supprimer se fait fonction d'une mesure de centralité (qui rend compte du rôle de l'arête dans le graphe).
  • La centralité d'une arête mesure combien elle apporte de “cohésion” au graphe (elle reflète le nombre de plus court chemins qui y passent).
    • La suppression d'une arête de forte centralité est donc susceptible d'éclater le graphe en 2 ou plusieurs “composantes” dont les arêtes sont plutôt tournées à vers l'intérieur de la composante.
    • La suppression d'une arête est susceptible d'éclater une composante du graphe.
  • A chaque suppression d'arêtes, on évalue la modularité du graphe.
    • Les clusters sont les composantes connexes induites de la suppression des arêtes.
    • On peut ainsi tracer une courbe montrant l'évolution de la modularité fonction des suppression successives des arêtes: les arêtes supprimées sont externes aux clusters, les arêtes restantes sont internes aux clusters.
    • Le clustering calculé par l'algorithme est celui correspondant au maximum sur la courbe.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/algorithmes_de_girvan-newman.txt · Last modified: 2016/05/14 14:04 by melancon