François Queyroi
Mardi 09 juillet 2013 à 14h, salle 25-26/101
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 sinterprè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.