|Mathematical Institute of the Serbian Academy of Sciences and Arts
|Variable neighborhood search for minimum sum-of-squares clustering on networks
|European Journal of Operational Research
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.
|Minimum sum-of-squares clustering Location on networks Variable neighborhood search
|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 Feb 22, 2024
checked on Feb 21, 2024
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.