https://doi.org/10.1140/epjb/e2014-50026-4
Regular Article
Edge-ratio network clustering by Variable Neighborhood Search
1 ENAC, MAIAA, 31055 Toulouse, France
2 University of Toulouse, IMT, 31400 Toulouse, France
3 GERAD, HEC Montréal, Montréal H3T 2A7, Canada
4 LAMIH, University of Valenciennes, 59313 Valenciennes, France
a
e-mail: sonia.cafieri@enac.fr
Received: 12 January 2014
Received in final form: 2 April 2014
Published online: 21 May 2014
The analysis of networks and in particular the identification of communities, or clusters, is a topic of active research with applications arising in many domains. Several models were proposed for this problem. In reference [S. Cafieri, P. Hansen, L. Liberti, Phys. Rev. E 81, 026105 (2010)], a criterion is proposed for a graph bipartition to be optimal: one seeks to maximize the minimum for both classes of the bipartition of the ratio of inner edges to cut edges (edge-ratio), and it is used in a hierarchical divisive algorithm for community identification in networks. In this paper, we develop a VNS-based heuristic for hierarchical divisive edge-ratio network clustering. A k-neighborhood is defined as move of k entities, i.e., k entities change their membership from one to another cluster. A local search is based on 1-changes and k-changes are used for shaking the incumbent solution. Computational results on datasets from the literature validate the proposed approach.
Key words: Statistical and Nonlinear Physics
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2014
