 |
Chapitre d'ouvrage
Variable Neighborhood Search for Edge-Ratio Network Clustering
Abstract : Edge-ratio clustering was introduced in [Cafieri et al., Phys.Rev. E 81(2):026105, 2010], as a criterion for optimal graph bipartitioning in hierarchical divisive algorithms for cluster identification in networks. Exact algorithms to perform bipartitioning maximizing the edge-ratio were shown to be too time consuming to be applied to large datasets. In this paper, we present a Variable Neighborhood Search (VNS)-based heuristic for hierarchical divisive edge ratio network clustering. We give a full description including the structure of some algorithmic procedures which are used to implement the main steps of the heuristic. Computational results show that the proposed algorithm is very efficient in terms of quality of the bipartitions, moreover the computing time is much smaller than that one for exact algorithms.
Littérature citée [20 références]
https://hal-enac.archives-ouvertes.fr/hal-01017978
Contributeur : Céline Smith Connectez-vous pour contacter le contributeur
Soumis le : jeudi 3 juillet 2014 - 14:54:36
Dernière modification le : lundi 4 avril 2022 - 15:24:12
Archivage à long terme le : : vendredi 3 octobre 2014 - 11:29:06
Contributeur : Céline Smith Connectez-vous pour contacter le contributeur
Soumis le : jeudi 3 juillet 2014 - 14:54:36
Dernière modification le : lundi 4 avril 2022 - 15:24:12
Archivage à long terme le : : vendredi 3 octobre 2014 - 11:29:06
Fichier
Cafieri_NATO2014.pdf
Fichiers produits par l'(les) auteur(s)