Partitionnement de graphes attribués par des méthodes basées sur la distance de Gromov-Wasserstein

Le clustering de graphes attribués consiste à diviser un graphe, dont les nœuds possèdent des attributs, en différentes classes, permettant d’identifier des communautés ou de segmenter des réseaux complexes. Ce problème est en particulier présent dans le cas des réseaux routiers qui peuvent être représentés comme des graphes possédant des attributs, tels que des courbes de flux de trafic ou des histogrammes de vitesse. Pour tenir compte à la fois de la structure topologique du graphe et des attributs, nous nous concentrerons ici sur des méthodes de partitionnement basées sur les distances, en particulier les k-Fréchet means et des méthodes issues du transport optimal, utilisant la distance de Gromov–Wasserstein. Les performances des méthodes développées seront évaluées à l’aide d’un cadre de simulation, permettant d’analyser leur sensibilité au bruit et l’influence du choix de la structure cible. Enfin, les méthodes seront illustrées sur des données réelles de trafic dans une ville française.