RSS

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

09/07/2013
Intervenant(s) : François QUEYROI (LaBRI, Université Bordeaux I)
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.

Plus d'informations ici …
romain.campigotto (at) nulllip6.fr
Mentions légales
Carte du site