Évaluation et optimisation d'une partition hiérarchique de graphe
Tuesday, July 9, 2013Franç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.
More details here …
romain.campigotto (at) nulllip6.fr