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
Abstract: 
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

SCOPUSTM   
Citations

7
checked on Dec 2, 2021

Page view(s)

7
checked on Dec 3, 2021

Google ScholarTM

Check

Altmetric

Altmetric


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