Authors: Cafieri, Sonia
Hansen, Pierre
Mladenović, Nenad 
Title: Edge-ratio network clustering by Variable Neighborhood Search
Journal: European Physical Journal B
Volume: 87
Issue: 5
Issue Date: 1-Jan-2014
Rank: M23
ISSN: 1434-6028
DOI: 10.1140/epjb/e2014-50026-4
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.
Publisher: Springer Link

Show full item record


checked on May 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.