Graph Clustering Based on Mixing Time of Random Walks

Abstract : Clustering of a graph is the task of grouping its nodes in such a way that the nodes within the same cluster are well connected, but they are less connected to nodes in different clusters. In this paper we propose a clustering metric based on the random walks' properties to evaluate the quality of a graph clustering. We also propose a randomized algorithm that identifies a locally optimal clustering of the graph according to the metric defined. The algorithm is intrinsically distributed and asynchronous. If the graph represents an actual network where nodes have computing capabilities, each node can determine its own cluster relying only on local communications. We show that the size of clusters can be adapted to the available processing capabilities to reduce the algorithm's complexity.
Type de document :
Communication dans un congrès
IEEE International Conference on Communications (ICC 2014), Jun 2014, Sydney, Australia. pp.4089-4094, 〈http://icc2014.ieee-icc.org/〉. 〈10.1109/ICC.2014.6883961〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01087693
Contributeur : Mahmoud El Chamie <>
Soumis le : mercredi 26 novembre 2014 - 15:00:26
Dernière modification le : samedi 27 janvier 2018 - 01:31:42
Document(s) archivé(s) le : vendredi 27 février 2015 - 12:26:07

Fichier

CamReadyICC2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Konstantin Avrachenkov, Mahmoud El Chamie, Giovanni Neglia. Graph Clustering Based on Mixing Time of Random Walks. IEEE International Conference on Communications (ICC 2014), Jun 2014, Sydney, Australia. pp.4089-4094, 〈http://icc2014.ieee-icc.org/〉. 〈10.1109/ICC.2014.6883961〉. 〈hal-01087693〉

Partager

Métriques

Consultations de la notice

260

Téléchargements de fichiers

178