Show simple item record

dc.contributor.authorBenati, Stefano
dc.contributor.authorPuerto, Justo
dc.contributor.authorRodríguez Chía, Antonio Manuel 
dc.contributor.otherEstadística e Investigación Operativaes_ES
dc.date.accessioned2025-03-19T07:54:28Z
dc.date.available2025-03-19T07:54:28Z
dc.date.issued2017
dc.identifier.issn0377-2217
dc.identifier.urihttp://hdl.handle.net/10498/35899
dc.description.abstractA new combinatorial model for clustering is proposed for all applications in which individual and relational data are available. Individual data refer to the intrinsic features of units, they are stored in a matrix D, and are the typical input of all clustering algorithms proposed so far. Relational data refer to the observed links between units, representing social ties such as friendship, joint participation to social events, and so on. Relational data are stored in the graph G=(V,E), and the data available for clustering are the triplet G=(V,E,D), called attributed graph. Known clustering algorithms can take advantage of the relational structure of G to redefine and refine the units membership. For example, uncertain membership of units to groups can be resolved using the sociological principle that ties are more likely to form between similar units. The model proposed here shows how to take into account the graph information, combining the clique partitioning objective function (a known clustering methodology) with connectivity as the structural constraint of the resulting clusters. The model can be formulated and solved using Integer Linear Programming and a new family of cutting planes. Moderate size problems are solved, and heuristic procedures are developed for instances in which the optimal solution can only be approximated. Finally, tests conducted on simulated data show that the clusters quality is greatly improved through this methodology.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherElsevier B.V.es_ES
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.sourceEuropean Journal of Operational Research - 2017, Vol. 261 n. 1 pp. 43-53es_ES
dc.titleClustering data that are graph connectedes_ES
dc.title.alternativeClustering data that are connected through a networkes_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.identifier.doi10.1016/J.EJOR.2017.02.009
dc.type.hasVersionAMes_ES


Files in this item

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
This work is under a Creative Commons License Attribution-NonCommercial-NoDerivatives 4.0 Internacional