Variable Neighborhood Search for Edge-Ratio Network Clustering

Sonia Cafieri 1, 2 Pierre Hansen 3 Nenad Mladenovic 4
1 MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
2 IMT - Institut de Mathématiques de Toulouse UMR5219
3 HEC Montréal - HEC Montréal
4 Department of Mathematical Sciences [Brunel]
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.
Type de document :
Chapitre d'ouvrage
S. Butenko et al. Examining Robustness and Vulnerability of Networked Systems, IOS Press, pp 51-64, 2014, NATO Science for Peace and Security Series - D : Information and Communication Security, Volume 37, 978-1-61499-390-2
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
https://hal-enac.archives-ouvertes.fr/hal-01017978
Contributeur : Céline Smith <>
Soumis le : jeudi 3 juillet 2014 - 14:54:36
Dernière modification le : mercredi 23 mai 2018 - 17:58:04
Document(s) archivé(s) le : vendredi 3 octobre 2014 - 11:29:06

Fichier

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

Identifiants

  • HAL Id : hal-01017978, version 1

Collections

MAIAA-OPTIM | MAIAA | ENAC | INSMI | IMT | UNIV-TLSE3 | INSA-TOULOUSE | UNIV-TLSE2 | TDS-MACS

Citation

Sonia Cafieri, Pierre Hansen, Nenad Mladenovic. Variable Neighborhood Search for Edge-Ratio Network Clustering. S. Butenko et al. Examining Robustness and Vulnerability of Networked Systems, IOS Press, pp 51-64, 2014, NATO Science for Peace and Security Series - D : Information and Communication Security, Volume 37, 978-1-61499-390-2. 〈hal-01017978〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

389

Téléchargements de fichiers

121

Picto

Contact  : publications@enac.fr