Julien Darlay
Jeudi 23 mai 2013 à 11h, salle 25-26/101
La détection de communautés est un problème d’analyse de données où les informations peuvent être représentées comme un graphe. Les sommets correspondent aux observations et les arêtes représentent des interactions entre les observations. On cherche généralement une partition des sommets du graphe en classes induisant des sous-graphes denses, c’est-à-dire des groupes d’observations presque toutes deux à deux similaires. Dans ce contexte, nous proposons une fonction objectif pour le problème de partition de graphe basée sur la densité définie par Goldberg. La densité d’un graphe est le rapport entre le nombre d’arêtes et le nombre de sommets. La densité d’une partition d’un graphe est alors définie comme la somme des densités des sous-graphes induits par chaque classe de la partition. Nous montrons que le problème consistant à trouver la partition de densité maximale est un problème NP-difficile et non approximable. Lorsque le graphe est un arbre, nous montrons qu’il existe un algorithme polynomial pour trouver la partition optimale. Nous proposons une heuristique à base de recherche locale à l’aide de LocalSolver que nous évaluons sur des instances de la littérature.