Évaluation et optimisation d’une partition hiérarchique de graphe

François Queyroi, LaBRI (Université Bordeaux I)
Mardi 09 juillet 2013 à 14h, salle 25-26/101
Abstract

Des travaux en sociologie, géographie ou biologie suggèrent la présence d'une structure de communautés multi-niveaux au sein des réseaux complexes. Cette structure peut être modélisée par un partitionnement hiérarchique des sommets d'un graphe. Plusieurs algorithmes ont été proposés récemment pour répondre à ce problème. En revanche, la question de l'évaluation d'une partition hiérarchique a été peu étudiée.

Je présenterai une généralisation des mesures de qualité additives au partitionnements multi-niveaux. Cette généralisation s’interprète comme un parcours des nœuds de l'arbre de partition réalisé en propageant le "gain" de chaque groupe à ses descendants. Je discuterai également plusieurs applications possible utilisant ce nouveau type de mesure ; notamment l'optimisation de la hiérarchie produite lors du déroulement de l'algorithme de Louvain.

This entry was posted in Events