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é.
Type de document :
Communication dans un congrès
Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2011, Cap Estérel, France. 2011
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00583844
Contributeur : Fabien De Montgolfier <>
Soumis le : jeudi 7 avril 2011 - 11:47:11
Dernière modification le : mardi 17 avril 2018 - 11:23:45
Document(s) archivé(s) le : vendredi 8 juillet 2011 - 02:36:19

Fichier

modularity-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00583844, version 1

Collections

Citation

Fabien De Montgolfier, Mauricio Soto, Laurent Viennot. Clustering de métrique et clustering de graphe. Ducourthial, Bertrand et Felber, Pascal. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2011, Cap Estérel, France. 2011. 〈inria-00583844〉

Partager

Métriques

Consultations de la notice

319

Téléchargements de fichiers

720