TY - JOUR
T1 - Exact algorithms for the minimum s-club partitioning problem
AU - Yezerska, Oleksandra
AU - Mahdavi Pajouh, Foad
AU - Veremyev, Alexander
AU - Butenko, Sergiy
N1 - Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
PY - 2019/5/1
Y1 - 2019/5/1
N2 - Graph clustering (partitioning) is a helpful tool in understanding complex systems and analyzing their structure and internal properties. One approach for graph clustering is based on partitioning the graph into cliques. However, clique models are too restrictive and prone to errors given imperfect data. Thus, using clique relaxations instead may provide a more reasonable and applicable partitioning of the graph. An s-club is a distance-based relaxation of a clique and is formally defined as a subset of vertices inducing a subgraph with a diameter of at most s. In this work, we study the minimum s-club partitioning problem, which is to partition the graph into a minimum number of non-overlapping s-club clusters. Integer programming techniques and combinatorial branch-and-bound framework are employed to develop exact algorithms to solve this problem. We also study and compare the computational performance of the proposed algorithms for the special cases of s= 2 and s= 3 on a test-bed of randomly generated instances and real-life graphs.
AB - Graph clustering (partitioning) is a helpful tool in understanding complex systems and analyzing their structure and internal properties. One approach for graph clustering is based on partitioning the graph into cliques. However, clique models are too restrictive and prone to errors given imperfect data. Thus, using clique relaxations instead may provide a more reasonable and applicable partitioning of the graph. An s-club is a distance-based relaxation of a clique and is formally defined as a subset of vertices inducing a subgraph with a diameter of at most s. In this work, we study the minimum s-club partitioning problem, which is to partition the graph into a minimum number of non-overlapping s-club clusters. Integer programming techniques and combinatorial branch-and-bound framework are employed to develop exact algorithms to solve this problem. We also study and compare the computational performance of the proposed algorithms for the special cases of s= 2 and s= 3 on a test-bed of randomly generated instances and real-life graphs.
KW - Combinatorial branch-and-bound
KW - Graph-based clustering
KW - Integer programming
KW - Partitioning
KW - s-Clubs
UR - http://www.scopus.com/inward/record.url?scp=85030567631&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85030567631&partnerID=8YFLogxK
U2 - 10.1007/s10479-017-2665-2
DO - 10.1007/s10479-017-2665-2
M3 - Article
AN - SCOPUS:85030567631
SN - 0254-5330
VL - 276
SP - 267
EP - 291
JO - Annals of Operations Research
JF - Annals of Operations Research
IS - 1-2
ER -