Clustering de métrique et clustering de graphe

Fabien de Montgolfier 1, 2 Mauricio Soto 1, 2 Laurent Viennot 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Résumé : 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é.
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00583844
Contributor : Fabien de Montgolfier <>
Submitted on : Thursday, April 7, 2011 - 11:47:11 AM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM
Long-term archiving on : Friday, July 8, 2011 - 2:36:19 AM

File

modularity-hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00583844, version 1

Citation

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⟩

Share

Metrics

Record views

366

Files downloads

890