Clustering de métrique et clustering de graphe - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2011

Clustering de métrique et clustering de graphe

Abstract

Ce 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é.
Fichier principal
Vignette du fichier
modularity-hal.pdf (188.96 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00583844 , version 1 (07-04-2011)

Identifiers

  • HAL Id : inria-00583844 , version 1

Cite

Fabien de Montgolfier, Mauricio Soto, Laurent Viennot. Clustering de métrique et clustering de graphe. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2011, Cap Estérel, France. ⟨inria-00583844⟩
237 View
788 Download

Share

Gmail Facebook X LinkedIn More