Groupe d’études et de recherche en analyse des décisions

Classification sur les graphes

Pierre Hansen Professeur titulaire, Département de sciences de la décision, HEC Montréal, Canada

La classification automatique a pour objet de déterminer parmi un ensemble d’objets des sous-ensembles, ou classes d’objets homogènes et bien séparées. Étant donné l’importance croissante des grands réseaux, ou graphes, la classification est un problème suscitant de très nombreuses recherches au sein de diverses communautés : physiciens, biologistes, sociologues, informaticiens, chercheurs opérationnels, ingénieurs. Le critère actuellement le plus utilisé est la modularité, définie par Mark Newman et Michelle Girvan. La modularité d’une classe est la différence entre le nombre d’arrêtes de cette classe et le nombre espéré d’arrêtes en supposant qu’elles soient tirées au hasard en respectant toutefois la distribution des degrés de sommets. Diverses heuristiques permettent d’obtenir rapidement des partitions ou des hiérarchies de partitions de l’ensemble de l’objet considéré avec une modularité proche d’être optimale. Les méthodes exactes sont plus rares. Je présenterai une critique du critère de modularité ainsi que de nouveaux algorithmes pour le partitionnement et la classification hiérarchique. En ayant recours à la génération de colonnes, la taille des problèmes résolus exactement est multipliée par un facteur de 5 environ (travail joint avec Daniel Aloise, Sonia Cafieri, Gilles Caporossi, Leo Liberti et Sylvain Perron).