|Affiliations:||Mathematical Institute of the Serbian Academy of Sciences and Arts||Title:||Variable neighborhood search for minimum sum-of-squares clustering on networks||Journal:||European Journal of Operational Research||Volume:||230||Issue:||2||First page:||356||Last page:||363||Issue Date:||16-Oct-2013||Rank:||M21a||ISSN:||0377-2217||DOI:||10.1016/j.ejor.2013.04.027||Abstract:||
Euclidean Minimum Sum-of-Squares Clustering amounts to finding p prototypes by minimizing the sum of the squared Euclidean distances from a set of points to their closest prototype. In recent years related clustering problems have been extensively analyzed under the assumption that the space is a network, and not any more the Euclidean space. This allows one to properly address community detection problems, of significant relevance in diverse phenomena in biological, technological and social systems. However, the problem of minimizing the sum of squared distances on networks have not yet been addressed. Two versions of the problem are possible: either the p prototypes are sought among the set of nodes of the network, or also points along edges are taken into account as possible prototypes. While the first problem is transformed into a classical discrete p-median problem, the latter is new in the literature, and solved in this paper with the Variable Neighborhood Search heuristic. The solutions of the two problems are compared in a series of test examples.
|Keywords:||Minimum sum-of-squares clustering Location on networks Variable neighborhood search||Publisher:||Elsevier||Project:||Serbian–Spanish project AIB2010SE-00318
MTM2009-14039, MTM2012-36163 (Ministry of Science and Innovation, Spain)
FQM-329 (Junta de Andalucia, Spain)
Serbian Ministry of Sciences, Grant no. 172010
Show full item record
checked on Dec 5, 2021
checked on Dec 6, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.