Clustering de métrique et clustering de graphe

International audienceCe papier s'intéresse aux liens entre deux concepts : d'une part le clustering de graphes, mesuré par la modularité de Newman, et d'autre part le clustering d'un espace métrique, mesuré par la somme des carrés des distances au barycentre des clusters. Nous montrons qu'en passant de l'espace à un graphe de façon ''naturelle'' (par boules unitaires) et en appliquant un algorithme ''naturel'' de clustering (par r-net), on obtient un clustering de modularité bornée inférieurement (en fonction de la dimension de grille de l'espace et pour certains rayons de r-net). Quelques simulations en espace euclidien viennent illustrer le propos en comparant deux algorithmes pour les deux mesures de qualité