In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nod...In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between clusters.This problem is NP-hard.We design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all edges.As a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.展开更多
The Correlation Clustering Problem(CorCP) is a significant clustering problem based on the similarity of data.It has significant applications in different fields,such as machine learning,biology,and data mining,and ma...The Correlation Clustering Problem(CorCP) is a significant clustering problem based on the similarity of data.It has significant applications in different fields,such as machine learning,biology,and data mining,and many different problems in other areas.In this paper,the Balanced 2-CorCP(B2-CorCP) is introduced and examined,and a new interesting variant of the CorCP is described.The goal of this clustering problem is to partition the vertex set into two clusters with equal size,such that the number of disagreements is minimized.We first present a polynomial time algorithm for the B2-CorCP on M-positive edge dominant graphs(M≥ 3).Then,we provide a series of numerical experiments,and the results show the effectiveness of our algorithm.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11901605 and 12101069)the disciplinary funding of Central University of Finance and Economics(CUFE)+1 种基金the Emerging Interdisciplinary Project of CUFEthe Fundamental Research Funds for the Central Universities and Innovation Foundation of BUPT for Youth(No.500421358).
文摘In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between clusters.This problem is NP-hard.We design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all edges.As a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.
基金supported by the National Natural Science Foundation of China (Nos. 12131003,12101594,11771386,11728104,and 11201333)the Beijing Natural Science Foundation Project (No. Z200002)+1 种基金the China Postdoctoral Science Foundation (No. 2021M693337)the Natural Sciences and Engineering Research Council of Canada (NSERC) (No. 06446)。
文摘The Correlation Clustering Problem(CorCP) is a significant clustering problem based on the similarity of data.It has significant applications in different fields,such as machine learning,biology,and data mining,and many different problems in other areas.In this paper,the Balanced 2-CorCP(B2-CorCP) is introduced and examined,and a new interesting variant of the CorCP is described.The goal of this clustering problem is to partition the vertex set into two clusters with equal size,such that the number of disagreements is minimized.We first present a polynomial time algorithm for the B2-CorCP on M-positive edge dominant graphs(M≥ 3).Then,we provide a series of numerical experiments,and the results show the effectiveness of our algorithm.
