Correlation clustering of graphs and integers
Shigeki Akiyama, László Aszalós, Lajos Hajdu, A. Pethö · University of Debrecen Electronic Archive (University of Debrecen) · 2014
Correlation clustering can be modeled in the following way.Let A be a nonempty set, and ∼ be a symmetric binary relation on A. Consider a partition (clustering) P of A. We say that two distinct elements a, b ∈ A are in conflict, if a ∼ b, but a and b belong to different classes (clusters) of P, or if a ∼ b, however, these elements belong to the same class of P. The main objective in correlation clustering is to find an optimal P with respect to ∼, i.e. a clustering yielding the minimal number of conflicts.We note that correlation clustering, among others, plays an important role in machine learning.In this paper we provide results in three different, but closely connected directions.First we prove general new results for correlation clustering, using an alternative graph model of the problem.Then we deal with the correlation clustering of positive integers, with respect to a relation ∼ based on coprimality.Note that this part is in fact a survey of our earlier results.Finally, we consider the set of so-called S-units, which are positive integers having all prime divisors in a fixed finite set.Here we prove new results, again with respect to a relation defined by the help of coprimality.We note that interestingly, the shape of the optimal clustering radically differs for integers and S-units.