Indexed by:
Abstract:
Lower bounded correlation clustering problem is a generalization of the classical correlation clustering problem, which has many applications in protein interaction networks, cross-lingual link detection, and communication networks, etc. In the lower bounded correlation clustering problem, we are given a complete graph and an integer L. Each edge is labelled either by a positive sign + or a negative sign - whenever the two endpoints of the edge are similar or dissimilar respectively. The goal of this problem is to partition the vertex set into several clusters, subject to an lower bound L on the sizes of clusters so as to minimize the number of disagreements, which is the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. In this paper, we propose the lower bounded correlation clustering problem and formulate the problem as an integer program. Furthermore, we provide two polynomial time algorithms with constant approximate ratios for the lower bounded correlation clustering problem on some special graphs.
Keyword:
Reprint Author's Address:
Source :
COMPUTATIONAL DATA AND SOCIAL NETWORKS, CSONET 2021
Year: 2021
Volume: 13116
Page: 39-49
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 4
Affiliated Colleges: