1

Correlation clustering of graphs and integers
S. Akiyama, L. Aszalós, L. Hajdu, A. Pethő

Abstract—Correlation clustering can be modeled in the following way. Let A be a nonempty set, and ∼ be a symmetricbinary 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 6∼ b, however, these elements belong to the same classof 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 forcorrelation 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. Notethat 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 ofcoprimality. We note that interestingly, the shape of the optimalclustering radically differs for integers and S-units.
Index Terms—correlation clustering, graphs, integers, S-units.

I. I NTRODUCTION
Correlation clustering was introduced in the field of machinelearning. We refer to the paper of Bansal et al. [4], which also
gives an excellent overview of the mathematical background.
Let G be a complete graph on n vertices and label its edges
with +1 or −1 depending on whether the endpoints havebeen deemed to be similar or different. Consider a partitionof the vertices. Two edges are in conflict with respect to thepartition if they belong to the same class, but are different,or they belong to different classes although they are similar.
The ultimate goal of correlation clustering is to find a partition
with minimal number of conflicts. The special feature of thisclustering is that the number of clusters is not specified. In
some applications G is not necessarily a complete graph likein [5] or the labels of the edges are real numbers like in [9].
Correlation clustering admits the following equivalentmodel too. Let A be a nonempty set, ∼ be a tolerance relation
on A, i.e., a reflexive and symmetric binary relation. Consider
a partition (clustering) P of A. We say that two elementsa, b ∈ A are in conflict, if a ∼ b, but a and b belong
to different classes (clusters) of P, or if a 6∼ b, however,
S. Akiyama is with the Institute of Mathematics, University ofTsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, Japan (zip:350-8571), e-mail:akiyama@math.tsukuba.ac.jp
L. Aszalós is with the Faculty of Computer Science, Universityof Debrecen, H-4010 Debrecen, P.O. Box 12, Hungary, e-mail: Aszalos.Laszlo@inf.unideb.hu
L. Hajdu is with the Institute of Mathematics, University of Debrecen, H4010 Debrecen, P.O. Box 12, Hungary, e-mail: hajdul@science.unideb.hu
A. Pethő is with the Faculty of Computer Science, University of Debrecen,
H-4010 Debrecen, P.O. Box 12, Hungary, e-mail: Petho.Attila@inf.unideb.hu

these elements belong to the same class of P. The main
objective is to find an optimal P with respect to ∼, i.e. aclustering yielding the minimal number of conflicts. It is worth
to mention that if we also assume that ∼ is transitive, then it
is an equivalence relation. In this case the optimal clustering
is obviously provided by the equivalence classes of ∼. So
this is the lack of the transitive property which makes the
problem of correlation clustering interesting and important.
Every clustering of A implies an equivalence relation on
A. The number of conflicts in a clustering reflects a kindof distance of ∼ to this equivalence relation. An optimalcorrelation clustering causes the least number of conflicts
among all clusterings, thus it induces a nearest equivalence
relation to ∼.
A typical application of correlation clustering is the classification of unknown topics of (scientific) papers. In this case thepapers represent the elements of A and two papers are considered to be similar (or being in relation ∼), if one of them refers
to the other. The classes of an optimal clustering then can beinterpreted as the topics of the papers. This kind of clusteringhas many applications: image segmentation [12], identifying
biologically relevant groups of genes [2], examining social
coalitions [16], reducing energy consumption in wireless sensor networks [6], modeling physical processes [13], etc.
The number of partitions of sets having n elements grows
exponentially, so the exhaustive search is not available to findan optimal clustering. Bansal et al. [4] showed that to find an
optimal clustering is NP-hard. Beside this, they also proposed
and analyzed algorithms for approximate solutions of the
problem. In fact the correlation clustering can be considered
to be an optimization problem: one should find the clustering
minimizing the number of conflicts. Thus it is possible toapply traditional and modern optimization algorithms to findalmost optimal clusterings. Following this approach, Bakó andAszalós [3] have implemented several traditional methods, andhave also invented some new ones.
In this paper we consider infinite growing sequences oflabeled graphs such that the labeling is hereditary (see Section
II). Then we can define lower and upper densities of edges withlabel +1 as well as of the classes in an optimal correlation
clustering. The aim of Section II is to show relations between
these quantities. Our results show that the choice of thelabeling heavily affects the structure of the optimal clustering.
For example Theorem 1 implies that if the upper density ofedges with +1 is less than 1/2 then there are at least twoclasses in an optimal correlation clustering. The value 1/2 isthe best possible by Remark 1.
In Sections III and IV we investigate particular examples.
To introduce them we switch to the relational model. In thatcase we may assume that Ai , i = 1, 2, . . . is a chain of subsets
of N and ∼i is the restriction of ∼ to Ai . Here ∼ denotes a2reflexive and symmetric relation on N. After fixing the basic
set to N it is natural to use the coprimality to define the relation∼. More precisely, for positive integers a, b ∈ A we set a ∼ b
if gcd(a, b) > 1 or a = b = 1. In Section III we consider thisrelation with sets An of positive integers not exceeding n (n =1, 2, . . . ). The results of this section are published in the paper[1], so we only outline the main results and methods here.
We present a natural greedy algorithm, Algorithm 1, which
computes locally optimal clustering and prove that it behaves
regularly for n < n0 = 3·5·7·11·13·17·19·23 = 111 546 435,
but from n0 on this regularity disappears. Further we showthat its optimal correlation clustering has at least two classes.
In Section IV we give a similar analysis, but for the sets of
S-units (or generalized Hamming numbers) not exceeding n(n = 1, 2, . . . ). The results presented here are all new. We
show that the optimal correlation clustering is in this case
asymptotically trivial, i.e. has only one class. Although theasymptotic result is smooth, there are usually many growingclasses in the early stages, but after a while the largest classstarts to collect all elements like a black hole.
Finally, we give concluding remarks in Section V.

of generality we may assume that the classes are arranged in
non-increasing order with respect to cardinality, that is|Pj (n)| ≥ |Pj+1 (n)| (j = 1, . . . , m(n) − 1).
Define the upper and lower cluster densities of Pj (n) by
ρj = lim supn→∞|Pj (n)|n→∞n|Pj (n)|,nρj = lim inf

for j = 1, . . . , m(n). If j > m(n) then we set Pj (n) = ∅.
Clearly we have ρj ≥ ρj+1 and ρj ≥ ρj+1 for j ≥ 1.
Theorem 1. We haveX
ρ2i ≤ 2g,

ρ1 2 ≤ 2g

i

and
g−

X

ρi ρj ≤

X

i<j

ρ2i ,

g−

i

X

ρi ρj ≤

X

i<j

ρ2i .

j

P

Proof. We claim that i ρi ≤ 1. In fact, for any m ∈ N andany ε > 0, there exists an n0 ∈ N such thatρj − ε/m ≤ |Pj (n)|/n

II. C ORRELATION CLUSTERING OF GRAPHS

for j ≤ m and n ≥ n0 . Thus

In this section we consider the problem of correlation
clustering not for a single graph, but for an increasing familyof graphs. For n ≥ 1, let Kn be the complete graph of nvertices. Write V (Kn ) and E(Kn ) for the set of vertices andedges of Kn , respectively. Take an arbitrary labelingmX

cn : E(Kn ) → {−1, 1}of the edges of Kn , subject to the hereditary (consistency)
condition that for some embedding
σn−1 : Kn−1 → Kn
of Kn into Kn−1 the coloring is invariant, that iscn−1 (e) = cn (σn−1 (e)) for e ∈ E(Kn−1 ).
Thus

σ

σ

1
2
K1 −→
K2 −→
...

can be considered as an increasing sequence of labeled graphs.
We define the upper and lower densities of the edges having
label 1 in the usual way:g = lim supn→∞

g = lim infn→∞|{e ∈ E(Kn ) : cn (e) = 1}|=|E(Kn )||{e ∈ E(Kn ) : cn (e) = 1}|= lim inf.
n→∞n(n − 1)/2
Here and later on, |H| denotes the number of elements ofthe set H. Let P(n) be an optimal clustering of (Kn , cn ),with classes P1 (n), P2 (n), . . . , Pm(n) (n). Here without lossmX
|Pj (n)|n=1n+ ε ≤ 1 + ε.

As one can choose ε and m arbitrarily, the above inequality
proves our claim. This fact is used in the last part of the proofof the first inequality.
As Pj (n) is an optimal cluster, in the induced graph toPj (n) of (Kn , cn ), at least half of the edges belonging toeach vertex of Pj (n) must have label 1. Indeed, if this does
not hold for some vertex v of Pj (n), then the cluster Pj (n)can be divided into Pj (n) \ {v} and {v}, and in the newclustering the number of conflicts is less. This implies thatamong |E(Pj (n))| edges, there are at least |E(Pj (n))|/2
edges with label 1. From the inequality
1X|E(Pj (n))| ≤ |{e ∈ E(Kn ) : cn (e) = 1}|,(1)
2 j
for any m ∈ N and ε1 > 0, there exists an n1 ∈ N such thatm

1 X ((ρj − ε1 )n)((ρj − ε1 )n − 1)
≤
2 j=1
2

|{e ∈ E(Kn ) : cn (e) = 1}|=|E(Kn )||{e ∈ E(Kn ) : cn (e) = 1}|= lim supn(n − 1)/2
n→∞
and

j=1

ρj ≤

≤ |{e ∈ E(Kn ) : cn (e) = 1}|
for n ≥ n1 . Thus for any ε2 > 0m

1 X ((ρj − ε1 )n)((ρj − ε1 )n − 1)n(n − 1)≤ (g + ε2 )
2 j=1
2
2
holds for infinitely many n. Dividing by n2 /2 and letting ntend to ∞, we obtain the first inequality, since m, ε1 , and ε2
are arbitrary.
It is also clear from (1) that for any ε1 > 0 and ε2 > 0, wehave((ρ1 − ε1 )n)((ρ1 − ε1 )n − 1)≤23n(n − 1)
2
for infinitely many n, giving the second inequality.
Consider now two clusters Pi (n) and Pj (n). Among the|Pi (n)|·|Pj (n)| edges joining the two clusters in Kn , the number of edges labeled by 1 can be at most |Pi (n)| · |Pj (n)|/2.
Indeed, otherwise we could decrease the number of conflicts
by taking Pi (n) ∪ Pj (n) as a new cluster. So
1X|Pi (n)| · |Pj (n)|2 i<j≤ |{e ∈ E(Kn ) : cn (e) = 1}| ≤ (g + ε2 )is an upper bound for the number of edges labeled by 1,
connecting two distinct clusters Pi (n) and Pj (n). On the other
hand, for any ε3 > 0 and for infinitely many n, there exist at
least
X|E(Pj (n))|(g − ε3 )|E(Kn )| −edges labeled by 1, connecting two distinct clusters Pi (n) andPj (n). Thus we get the inequality
1X|Pi (n)| · |Pj (n)| ≥2 i<jX≥ (g − ε3 )|E(Kn )| −|E(Pj (n))|
for infinitely many n. Therefore for any ε2 > 0, we have1X((ρ + ε2 )n)((ρj + ε2 )n) ≥2 i<j i≥ (g − ε3 )Proof. The statement follows from

2
X
X
X
g+
ρ ρj ≤ ρ  ≤ 2g + 2
ρρ
i

j

i<j

Corollary 1. Using the previous notation, we have
X
X
p
p
g≤
ρj and
g≤
ρj .
j

j

Proof. The first assertion follows from

2
X
X
g≤g+
ρi ρj ≤ 
ρj 
i<j

j

using the third inequality of Theorem 1. The proof of thesecond inequality is similar.
P∞
We say that the clusters are full if j=1 ρj = 1.
Not all clusterings are full. For example, we may introduce
an ordering of vertices of Kn and let P1 (n) be the first halfof the vertices and remaining Pj (n) be singletons for j ≥ 2.
Then we have ρ1 = 1/2 and ρj = 0 for j ≥ 2.
Corollary 2. Assume that the optimal clusters are full. If g =g = g then we have
X
X
1/2 −
ρi ρj ≤ g ≤ 1 −ρi ρj .
i<j

i<j

In particular, ρ1 = 1 and ρj = 0 for j > 1 holds if and only
if g = 1.

i<jP
and j ρj = 1. Since ρj+1 ≥ ρj by definition, the inequality
shows that ρ1 ρ2 > 0 holds if and only if g < 1.
The last statement shows that the edges labeled by 1 must
be of density 1 in order to have only one non-empty class(namely, the whole Kn ) in an optimal clustering. At this point
we need to introduce some new notions.
A graph G is locally stable if the degree of each vertex is
at least d(|G| − 1)/2e. It is globally stable if for any partition
V (G) = A ∪ B (disjoint), there are at least d|A| · |B|/2eedges connecting A and B. Denote by G(Pj (n)) the graphobtained from the graph induced by the optimal cluster Pj (n)of (Kn , cn ), by removing all its edges labeled by −1. Then
G(Pj (n)) is globally stable, since otherwise a corresponding
partition A ∪ B gives a lower number of conflicts. For brevity,
we say that Pj (n) is globally stable if G(Pj (n)) has thisproperty.
Theorem 2. If Kn is a single cluster, then its global stability
implies that this is an optimal clustering (consisting of one
cluster).
Proof. Assume that Kn = P is globally stable and consider
a different partitionn(n − 1) X ((ρj + ε2 )n)(((ρj + ε2 )n) − 1)−22
jfor infinitely many n. This implies the third inequality. The
proof of the last inequality is similar, and our statement
follows.

i j

j

Kn =

`
[

Qi .

i=1

Let c(Qi , Qj ) be the total number of conflicts between Qi and
Qj , that is
X 1 + cn (e),c(Qi , Qj ) =2ewhere the sum is taken over all edges between Qi , Qj . By the
global stability of P, the partition[Pi = Qi ∪ 
Qj 
j:j6=igives not less conflicts. So we see that[Xc(Qi ,Qj ) =c(Qi , Qj ) ≥ 0
j:j6=ij:j6=ifor all i. Summing these inequalities we obtainX(` − 1)c(Qi , Qj ) ≥ 0.
i<jS`

Thus the partition i=1 Qi gives not less conflicts than P, andthe statement follows.
Lemma 1. Complete bipartite graphs Km,m and Km,m+1 areglobally stable.
Proof. Let U , V be the vertex sets of Km,m . (That is, all edgesof Km,m run between U and V .) Let A ∪ B be a partition of
the vertex set U ∪ V . Put x = |A ∩ U |, y = |A ∩ V |. Thenm − x = |B ∩ U |,m − y = |B ∩ V |.

4

The number of edges between A and B isx(m − y) + y(m − x) = m(x + y) − 2xy.
This is not less than|A| · |B|/2 = (x + y)(2m − x − y)/2.
For Km,m+1 , the computation is similar. With the same
notation, the number of edges between A and B isx(m + 1 − y) + y(m − x) = m(x + y) + x − 2xy.
This is not less than|A| · |B|/2 = (x + y)(2m + 1 − x − y)/2
since
x − 2xy − (x + y)(1 − x − y)/2 = (x − y)(x − y + 1)/2 ≥ 0
holds for x, y ∈ Z. This implies the statement.
Remark 1. In the proof of Theorem 1 we only used thefact that G(Pj (n)) is locally stable. However, the second
inequality is the best possible in the sense that the constant2 cannot be chosen smaller. Indeed, consider the naturalembeddingKm,m ⊂ Km,m+1 ⊂ Km+1,m+1 ⊂ . . . ,and consider Km,n to be a subgraph of Km+n . Define thelabeling cm+n by(
1,
if e ∈ E(Km,n ),cm+n (e) =−1, if e ∈ E(Km+n ) \ E(Km,n ).
Then this labeling ck is consistent and asymptotically k 2 /4
edges have label 1. This gives an example that g = 1/2,
ρ1 = 1 and ρj = 0 for j > 1, which attains the equality forthe second inequality of Theorem 1.
III. C ORRELATION CLUSTERING OF POSITIVE INTEGERS
WITH RESPECT TO COPRIMALITY

As we have mentioned already in the introduction, it isobvious that the role of the relation ∼ (or, in the graph model,
the definitions of the labels ±1) is crucial for the structureof the optimal clustering. This motivates the investigations in
the present section. We mention that the results presented here
were published in the paper [1].
Consider the sequence of complete graphs Kn together witha hereditary labeling cn : E(Kn ) 7→ {−1, 1}. Labeling thevertices of Kn by the integers An = {1, . . . , n} the mapping
cn implies a reflexive and symmetric relation ∼n on An . By
the hereditary property of cn we may assume that ∼n admits
this property, too, i.e., the restriction of ∼n+1 to An is equal
to ∼n .
Let, more generally, An ⊂ N be finite and satisfying
An ⊆ An+1 for n = 1, 2, . . . . Assume that there is areflexive and symmetric relation ∼n on An . Further assume
that the restriction of ∼n+1 to An is equal to ∼n . SettingA = ∩∞
n=1 An we have A ⊆ N. Define the relation ∼ on A
as follows: for a, b ∈ A we set a ∼ b if there exist n ≥ 1such that a, b ∈ An and a ∼n b. By the hereditary propertyof ∼n the relation ∼ is well defined on A, moreover it isreflexive and symmetric. Of course we can consider ∼ on N,
too. This justifies that in the sequel we consider a relation on
N. Divisibility is the best understood relation of integers. As
it is not symmetric (2|4 but 4 - 2) we cannot use it in ourinvestigations. Fortunately the coprime relation, i.e. a ∼ b if
gcd(a, b) > 1 or if a = b = 1, is closely related to divisibility
and is symmetric.
In this section we work with sets An of positive integers
greater than 1, but not exceeding n (for n = 2, 3, . . . ).
Moreover we assume that An is equipped with the above
defined coprime relation. Note that the behavior of the gcd
among the first n positive integers has been investigated frommany aspects; see e.g. a paper of Nymann, [14].
Bakó and Aszalós [3] have made several experiments concerning the optimal clustering of An with respect to ∼. They
have discovered that the classes of a near optimal clustering
have regular structure. In the sequel denote by pi the i-thprime, i.e., p1 = 2, p2 = 3, . . . . Set
Ai,n = {m : m ≤ n, pi |m, pj - n (j < i)}.
In other words, Ai,n is the set of integers at most n, which
are divisible by pi , but coprime to the smaller primes. Aszalós
and Bakó found that[2, n] ∩ Z =

∞
[

Aj,n

(2)

j=1

is an optimal correlation clustering for n ≤ 20 and very
probably for n ≤ 500, too. Notice that Aj,m = ∅ for all large
enough j, i.e., the union on the right hand side is actuallyfinite.
The main result of this section (and of [1]) is that forn0 = 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 = 111 546 435
the decomposition (2) is not optimal. We prove that the numberof conflicts in[2, n0 ] ∩ Z = (A1,n0 ∪ {n0 }) ∪ (A2,n0 \ {n0 })∞[Aj,n (3)j=3

is less than in (2) with n = n0 . We cannot prove that (2)is optimal for n < n0 . However, we show that the natural
greedy algorithm (Algorithm 1), presented below, produces
the clustering (2) for all n < n0 , and it yields (3) for n = n0 .
As we have mentioned already in the introduction, by resultsfrom [4] we know that to find an optimal correlational clustering is an NP-hard problem. Hence to find an approximation of
the optimal solution, it is natural to use some kind of greedy
algorithm. For the sets An we use the following approach.
The optimal clustering for A2 = {2} is itself. Assume that
we have a partition of An−1 with n > 2, and adjoin n tothat class, which causes the less new conflicts. As a result weobtain a locally optimal clustering, which is not necessarily
globally optimal on An .
Starting with a partition of An−1 this algorithm returns apartition of An such that the conflicts caused by putting n into
one of the classes is minimal. The output of Algorithm 1 on

5

Algorithm 1 Natural greedy algorithm
Require: an integer n ≥ 2
Ensure: a partition P of N
1: P ← {{2}};2: if n = 2 then return P
3: end if
4: m ← 3
5: while m ≤ n do
6:
PM ← P ∪ {{m}}7:M ← CONFLICTS(PM , m).
the number of conflicts with respect to the partition PM
caused by the pairs (m, a), a < m
8:C ← number of classes in P
9:
j←1
10:
while j ≤ C do11:
O ← OP(j, P) . OP (j, P) denotes the j-th classin the partition P.
12:
P1 ← P \ {O}13:
P1 ← P1 ∪ {O ∪ {m}}14:
M1 ← N U PAIR(P1 , m)
. the number of pairs(m, a) with a < m causing a conflict in the partition P1
15:
if M1 < M then16:
M ← M117:
PM ← P1
18:
end if19:
end while
20: end while
21: return PM
the input n is denoted by G(n). It is certainly a clustering of
An . As one can easily check, we obtainG(3)= {{2}, {3}}G(4)= {{2, 4}, {3}}G(5)= {{2, 4}, {3}, {5}}Lemma 2. Let n > 2 be an integer. Write G(n − 1) ={P1 , . . . , PM } and set P0 = ∅. For 1 ≤ j ≤ M let
Ej,n = {m : m ∈ Pj , gcd(m, n) = 1}
andBj,n = {m : m ∈ Pj , gcd(m, n) > 1}.
Define E0,n = B0,n = ∅. Let J be the smallest index for which|Bj,n | − |Ej,n | (j = 0, . . . , M ) is maximal. Then G(n) =0{P00 , . . . , PM
} such that(Pj ∪ {n}, if j = J,
0
Pj =
Pj ,
otherwise.
This lemma has the following important consequence.
Corollary 3. The following assertions are true.
(1) If n is even, then n ∈ A1,n .
(2) If n is a prime, then {n} ∈ G(n).
(3) If the smallest prime factor of n is pi and n ∈ Sj,n , thenj ≤ i.
The next result gives a useful bound for the sizes of the setsAi,u .
Lemma 3. Let u be an odd integer. Then we have |A1,u | =u−1
2 . Further, if pi is an odd prime, then

i−1 
u Y
1
|Ai,u | −1−
≤ 2i−2 .
pi
p``=1

The next lemma provides an estimation for |Bj,n | − |Ej,n |,whereG(6) = {{2, 4, 6}, {3}, {5}}
..
.
G(15)

ingredients of the proof. On this way, we recall several lemmas
from [1], always without proofs.
The first important information we need is to characterizethat class of G(n − 1) to which Algorithm 1 adjoins n. Thisis done with the following

Bj,n = {m : m ∈ Aj,n−1 , gcd(m, n) > 1}

= {{2, 4, 6, 8, 10, 12, 14}, {3, 9, 15},{5}, {7}, {11}, {13}}.

For these values of n one can readily show that the above
partitions provide (in fact the unique) optimal clusterings forAn (2 ≤ n ≤ 15), as well.
The main result of this section is the following
Theorem 3. If m < n0 = 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 =111 546 435 then∞[G(m) =
Aj,m
(4)

and
Ej,n = {m : m ∈ Aj,n−1 , gcd(m, n) = 1}.
Note that the elements of Bj,n and Ej,n are those elements of
Aj,n−1 , which are, and which are not in the relation ∼ withn, respectively.
Lemma 4. Let q1 < · · · < qt be odd primes, α1 , . . . , αtpositive integers and n = q1α1 · · · qtαt . Let j ≥ 2 be such thatpj < q1 . Then
|Bj,n | − |Ej,n | − Cn,j,t ≤ 2t+j−2

j=1

holds, where

holds. However, we haveG(n0 ) = (A1,n0 ∪ {n0 }) ∪ (A2,n0 \ {n0 })∞[Sj,n0 .

j=3

Elements of the proof of Theorem 3. Since the complete proofof Theorem 3 is given in [1], here we only indicate the main


!
j−1 
t 
Y
1
1
n−1 Y
1−
1−2
1−
.
Cn,j,t =
pj
p`
qk
`=1

k=1

The next lemma plays an important role in the proof of
Theorem 3. We use the previous notation.

6

Lemma 5. Let n = q1α1 · · · qtαt with q1 < · · · < qt odd primes
and α1 , . . . , αt positive integers. Then

 

ϕ(n)
n
1
1
|E1,n | ==1−··· 1 −
,
2
2
q1
qt
n−1
− |E1,n |.
|B1,n | =2
Now, in principle, we are ready to give the main steps ofthe proof of Theorem 3. However, the proof is rather detailed,tricky and complicated, so we restrict ourselves to indicate
how the argument proceeds. We refer the interested reader
again to [1] for details.
Step 1. We start with confirming the cases where n is odd
and 3 | n. The difficult part is to show that (4) holds
for n < n0 . This assertion is verified by comparing theestimates of Lemmas 2, 3, 4, and 5, some computer search, andapplying a tool from prime number theory namely, estimatesfor expressions of the form

Y
1
.
1−
p
p<x
For the latter one can use e.g. formulas from [15].
Step 2. Next we check Theorem 3 for integers n with one
or two prime factors. For this we need to combine Lemmas
2, 3, and 4, involved computer search, and the following twolemmas are also needed. The first one verifies Theorem 3 if
n is a prime power.
Lemma 6. Let p = pi ≥ 3 be a prime. If p ≤ 67 and pα < n0 ,α > 0 then pα ∈ Ai,n . In general, n = pα ∈ Ai,n holds forα ≤ 4.
The second lemma proves our theorem for n with two
distinct prime divisors, where the smaller one is at most 53.
Lemma 7. Let p = pi ≥ 3 and q > p be primes. If p ≤ 53
and pα q β < n0 , α, β > 0 then pα q β ∈ Ai,n . In general,n = pq ∈ Ai,n is valid whenever q < p3 .

until a certain large value of n (in fact up to n0 ), but at thatpoint the regularity vanishes. From the proof it is clear thatn0 is the first, but not at all the last integer, which behavesin this irregular way. For example, the number 3n0 is odd
and is divisible by 3, however, adjoining it to A1,n causes
less conflicts than adjoining it to A2,n . Let A∗i,n denote theclass containing pi , produced by Algorithm 1. We can neither
guess the structure of these sets, nor what is their asymptotic
behavior. For example, it would be interesting to know whether
the limit|A∗1,n |lim
n→∞nexists or not, or is|A∗1,n |lim sup=1nn→∞
or not.
On the other hand Theorem 1 shade some light to theasymptotic behavior of the optimal correlation clustering of(An , ∼). Indeed denote by g, g, g, and ρj , j ≥ 1 the quantities
defined in Section II in the case (An , ∼). The next theorem
is new.
Theorem 4. With the above notation we haves 6
ρ1 ≤ 2 1 − 2 = 0.885520071...
π
In particular the optimal correlation clustering of (An , ∼) has
at least two classes.
Proof. First we prove that in the actual case g exists, i.e.,g = g = g. Indeed we haveang = lim,n→∞ bnwherean = |{(a, b) : 1 ≤ a ≤ b ≤ n, gcd(a, b) > 1}| ,andbn = |{(a, b) : 1 ≤ a ≤ b ≤ n}| =Step 3. Consider now numbers n with three distinct prime
factors. Unfortunately, for such values of n we could not
find any general assertion or formula like in Lemma 6 or 7.
However, our previous calculations yielded that here we may
assume that the smallest prime factor of n is at least 19. For
each prime 29 ≤ p ≤ 43 we computed all integers, which
are divisible by p, lie below a preliminary computed bound,and have three distinct prime divisors, which are at least p.
Then we used a variant of the wheel algorithm, see e.g. [17],to handle these cases. Altogether, up to this point we could
cover all values of n whose smallest prime factor is at most
47.
Step 4. To cover the remaining values of n (which have only“large” prime factors), we applied again formulas concerning
the distribution of primes. Namely, we used estimates for π(x),from [15]. This finishes the proof of Theorem 3. 2
We proved that applying Algorithm 1 for An (n ≥ 1), theoutputs (i.e. the clusterings of the An ) have a regular shapen(n − 1).
2

Obviouslyan= bn − |{(a, b) : 1 ≤ a ≤ b ≤ n, gcd(a, b) = 1}|nX= bn −ϕ(d),d=1where ϕ(x) denotes Euler’s totient function. It is well known,see e.g. [11], thatnX
3ϕ(d) = 2 n2 + O(n log n).
π
d=1Combining everything together we get
6
g = 1 − 2.
π
By the second assertion of Theorem 1 we getρ21 ≤ 2g,
which together with the last inequality implies the statementof the theorem.

7

IV. C ORRELATION CLUSTERING OF S- UNITS WITHRESPECT TO COPRIMALITY

In this section we perform a similar analysis as in Section
III, with the same relation, but the set of positive integers
replaced by the set of positive integers having all prime
divisors in a preliminary fixed finite set. As it will turn out, thismodification changes the structure of the optimal clustering
drastically. All the results presented in this section are new.
To formulate our results in this direction, we need to
introduce some notions and notation. In what follows, let
S = {p1 , . . . , pk } be a finite set of primes. Those positive
integers which has no prime divisors outside S will be called
S-units, and their set is denoted by ZS . This terminology is
widely used in number theory, but in computer science theelements of the set ZS for S = {2, 3, 5} are also called
Hamming numbers, see e.g. [8]. For a given positive x ∈ R,
let ZS (x) denote the subset of ZS consisting of S-units not
greater than x. The sets ZS (n), n = 1, 2, . . . play the samerole as An in the last section. First we give a sharp upperbound for the number of elements of ZS (x) and some of its
subsets. For this we need some preparation. The following
result due to Davenport [7] will be very useful.
Lemma 8 ([7, Theorem]). Let R be a closed bounded region
in the n dimensional space Rn and let N(R) and V(R) denotethe number of points with integral coordinates in R and thevolume of R, respectively. Suppose that:• Any line parallel to one of the n coordinate axes intersects R in a set of points which, if not empty, consists ofat most h intervals.
• The same is true (with m in place of n) for any of them dimensional regions obtained by projecting R on oneof the coordinate spaces defined by equating a selectionof n − m of the coordinates to zero; and this conditionis satisfied for all m from 1 to n − 1.
Then
n−1
X
|N(R) − V(R)| ≤hn−m Vm ,m=0where Vm is the sum of the m dimensional volumes of the
projections of R on the various coordinate spaces obtainedby equating any n − m coordinates to zero, and V0 = 1 byconvention.
The next lemma will also play an important role later on.
Lemma 9. Let y1 , . . . , yr , x be positive real numbers, and let
N (y, x) denote the number of non-negative integer solutions
n1 , . . . , nr of the inequality
0 ≤ y1 n1 + · · · + yr nr ≤ x.

(5)

Then we have
N (y, x) = c(y)xr + O(xr−1 ),where c(y) is the volume of the r-dimensional polyhedrondefined by the inequalitiesxi≥

0 (i = 1, . . . , r),y1 x1 + · · · + yr xr≤

1.

Proof. It is clear that the non-negative integers n1 , . . . , nrsatisfy (5) if and only if the lattice point (n1 , . . . , nr ) belongs
to the polyhedron P (y, x) defined by the inequalitiesxi≥

0 (i = 1, . . . , r),y1 x1 + · · · + yr xr≤x.

Hence it is sufficient to bound the number of lattice points
inside P (y, x). Obviously, P (y, x) satisfies the conditions ofLemma 8. Moreover, the volume of P (y, x) equals xr times
the volume of P (y, 1). The domains Vm occurring in Lemma
8 are polyhedra of dimensions at most r − 1, hence their
total volume can be bounded by O(xr−1 ), and the statement
follows.
Now using Lemma 9 we can easily bound the number of
elements of ZS (x).
Corollary 4. Letting cS = c(log p1 , . . . , log pk , 1), we have
|ZS (x)| = cS (log x)k + O((log x)k−1 ).
Proof. A positive integer m belongs to ZS (x) if and only ifm ≤ x and there exist non-negative integers n1 , . . . , nk suchthatm = pn1 1 · · · pnk k .
This implies that0 ≤ log m = n1 log(p1 ) + · · · + nk log(pk ) ≤ log x.
Since log p1 , . . . , log pk > 0 are real numbers, the conditionsof Lemma 9 are satisfied, and the statement follows.
Now we shall investigate correlation clustering on ZS
equipped with the same coprimality relation which we usedin Section III. More precisely, for a, b ∈ ZS let a ∼ b, if andonly if gcd(a, b) > 1 or a = b = 1. For an integer n ≥ 1 let
P be a partition of ZS (n). As before, we say that the S-units
a and b are in conflict with respect to P, if either they are in
the same class but a 6∼ b, or they are in different classes andstill a ∼ b. As before, the purpose of correlation clustering is
to find a partition with minimal number of conflicts.
The partition of ZS (n) with only one class (i.e. when allelements of ZS (n) belong to the same class) is called thetrivial partition.
Lemma 10. Let CS (n) denote the number of conflicts in thetrivial partition of ZS (n). Then we have
CS (n) ≤ c(log n)k ,where c is a positive constant.
Proof. In case of the trivial partition, two different S-units
are in conflict precisely when they are coprime. Thus wehave to count those pairs of S-units (a, b), a 6= b which are
coprime. Let a, b be distinct S-units (not necessarily elements
of ZS (n)), and assume that gcd(a, b) = 1. Then there existsa T ⊆ S, such that
Y α
Y α
a=
pj j , b =pj j .
pj ∈T

pj ∈S\T8

If T = ∅ or S \ T = ∅ then the empty product is defined as 1,
i.e. the pairs (a, b) with a = 1 or b = 1 are included. Theseequations mean that a is a T -unit, and b is an (S \ T )-unit.
Hence for fixed T ⊆ S, the (S \ T )-units up to n are thepositive integers which are coprime to the T -units in ZS (n).
ThusX
|ZT (n)| · |ZS\T (n)|.
CS (n) ≤T ⊆S

Using Corollary 4 and |T | + |S \ T | = k, we obtain thatX
CS (n) ≤cT cS\T (log n)|T | (log n)|S\T | +T ⊆S+ O((log n)|T |+|S\T |−1 =


X
= 
cT cS\T  (log n)k + O((log n)k−1 ).
T ⊆S

set is just ZS\{pi } (n). Thus by Corollary 4 we obtain|Za |≥ cS (log n)k + O((log n)k−1 ) −− cS\{pi } (log n)k−1 + O((log n)k−2 )k= cS (log n) + O((log n)

k−1

(6)

).

Consider now an optimal clustering of ZS (n), denoted by
P. In view of Lemma 10, the number of conflicts with respect
to P is at most c(log n)k , where c is a positive constant.
Assume that the elements of Zpi are distributed in r
different classes, which contain m1 , . . . , mr elements of Zpi ,respectively. As the elements divisible by pi corresponding
to different classes are in conflict, thus the total number ofconflicts with respect to P is at leastXV =mj1 mj2 .
1≤j1 <j2 ≤rAssume that

Clearly, for fixed S the sumXmax mj ≤ (log n)1/2 .

1≤j≤rcT cS\TThen by (6) we haveT ⊆S

is independent of n, hence it is a constant. This proves thestatement.
Denoting by g = g(ZS ) and ρ1 = ρ1 (ZS ) the densities
defined in Section II, in the actual case we obtain
Corollary 5. We haver ≥ cS (log n)k−1/2 ,whencer2c2
r(r − 1)>
≥ S (log n)2k−1 ,2
44
whose magnitude is larger than that of the conflicts of thetrivial partition. This implies that for an optimal clusteringV ≥max mj > (log n)1/2

g = ρ1 = 1.
Proof. Corollary 4 and Lemma 10
P imply g = 1 immediately.
Thus by Corollary 1 we haveρ ≥ 1, which together
P j jwith the obvious inequalityj ρj ≤ 1 implies that any
optimal clustering of ZS (n) is full. Hence we have ρ1 = 1 by
Corollary 2.
The equality ρ1 = 1 does not mean that the optimalcorrelation clustering is asymptotically trivial, i.e. the optimalcorrelation clustering of ZS (n) is trivial for all large enoughn. Thus the statement of the next theorem is much sharper asthat of the last corollary.
Theorem 5. Suppose that n is large enough. Then the optimalcorrelation clustering of ZS (n) is given by the trivial partition.
Proof. If k = 1, i.e. S contains only one element, then all
members of ZS are divisible by it. Thus ∼ is an equivalence
relation on ZS , which corresponds to the trivial partition.
Hence the proof is complete for k = 1 and we may assumek ≥ 2 in the sequel.
Let 1 ≤ i ≤ k arbitrary, and let a ∈ ZS (n) be suchthat pi | a. Denote by Za the set of elements b ∈ ZS (n)with a 6= b, gcd(a, b) > 1. It is clear that Za contains allelements of ZS (n) \ {a}, which are multiples of pi . Thus
the number of these elements can be bounded by the numberof elements of the set obtained from ZS (n) by omitting its
elements which are not divisible by pi . Observe that the latter1≤j≤r

holds.
Let now d > (c + 1)/cS , where c is the constant given in
Lemma 10. Suppose that(log n)1/2 < max mj < |Zpi | − d.
1≤j≤rAssume further that the mj take their maximum for j = 1.
Then
V ≥ m1 (m2 + · · · + mr )= m1 (m1 + · · · + mr − m1 )= m1 (|Zpi | − m1 ).

The function m1 (|Zpi | − m1 ) can attain its minimum in theendpoints of the given interval. If m1 = (log n)1/2 , then by(6) we haveV ≥ cS (log n)k+1/2 ,while m1 = |Zpi | − d implies
V ≥ d(|Zpi | − d) > (c + 1)(log n)k + O((log n)k−1 ).
Hence we get that the number of conflicts in both endpoints
are larger than that of the trivial partition.
This implies that there exists a class, say P1 , in which thenumber of multiples of pi is at least |Zpi | − d. Suppose thatd > 0 and let a be such that pi |a, but a ∈/ P1 . Then a is in
conflict with all the elements of P1 ∩ Zpi , and the number ofsuch elements is|Zpi | − d = cS (log n)k + O((log n)k−1 ).

9

128

point the structure of such a clustering is deemed to change.
Finally, we have considered the set of so-called S-units, under
the same relation as for positive integers. Here we have provedthat interestingly, in contrast with the case of positive integers,
after some point the optimal clustering is always given by thetrivial clustering (consisting of a single class).

2
3
5

64

size of partitions

32
16
8

ACKNOWLEDGMENT

4
2
1
0

10

20

30

40

50

60

70

80

90

100

no of numbers

Fig. 1. Simulation result: from the 96th Hamming numbers the correlation
clustering gives only one cluster.

Moving a to P1 , these conflicts will disappear. Of course, newconflicts can arise, on the one hand with those d − 1 multiples
of pi which are not in P1 , and on the other hand, with theelements not divisible by pi . Altogether, the number of new
conflicts can be at mostd + |ZS\{pi } (n)| = O((log n)k−1 ).
That is, if P is an optimal correlation clustering and if n islarge enough, then all multiples of pi must belong to the sameclass. Since pi has been chosen arbitrarily, thus all elements
must belong to the same class, and the theorem follows.
Remark 2. Theorem 5 describes completely the optimalcorrelation clustering of ZS (n) only if n is large enough.
Choosing S as the set of the first k primes, ZS (n) = An if
n < pk+1 , thus the optimal correlation clusterings of ZS (n)and An are identical. By the results of Section III the numberof clusters and their sizes of the optimal correlation clusteringof ZS (n) are growing for small n-s. After a certain point thistendency changes, all but one clusters become smaller until
only one cluster survives, like a black hole. Our experiments
show that this happens already for relatively small values ofn, as you can see in Fig. 1 for the Hamming numbers.
This means that locally optimal algorithms, like Algorithm
1, cannot give globally optimal solution for the correlation
clustering problem.
V. C ONCLUSION
In this paper we have considered the problem of correlation
clustering, introduced in [4], from three different but closely
related aspects. First we have derived new results for thegraph model of the problem, considering an increasing familyof graphs. We have obtained results concerning the optimalclustering in the general case. Then we have investigatedparticular sets with a specific relation. The reason for doing so
is that clearly, the choice of the underlying relation strongly
influences the structure of the optimal clustering. First we
have considered positive integers and a relation based upon
coprimality. Our main result here (recalled from [1]) has beenthat a natural greedy algorithm provides a “locally” optimalclustering up to a certain positive integer n0 , however, at someWe are grateful to the referees for their valuable remarks.
Our research was supported in part by the OTKA grants
NK104208, NK101680, and K100339, by the Japanese Society
for the Promotion of Science (JSPS), Grant in aid 24540012,
and by the TÁMOP-4.2.2.C-11/1/KONV-2012-0001 project.
The project is implemented through the New Hungary Development Plan, cofinanced by the European Social Fund andthe European Regional Development Fund.
R EFERENCES[1] L. Aszalós, L. Hajdu, and A. Pethő, On a correlational clustering ofintegers, arXiv:1404.0904 [math.NT].
[2] M. Bakó, and L. Aszalós, Combinatorial optimization methods for correlation clustering, In: Coping with complexity/D. Dumitrescu, Rodica
Ioana Lung, Ligia Cremene, Casa Cartii de Stiinta, Cluj-Napoca, 2–12,
2011.
[3] N. Bansal, A. Blum, and S. Chawla, Correlational clustering, Machine
Learning, 56 (2004), 89–113.
[4] A. Bhattacharya, and R. K. De, Divisive Correlation Clustering Algorithm (DCCA) for grouping of genes: detecting varying patterns in
expression profiles. Bioinformatics 24 11. (2008): 1359–1366.
[5] Y. Chen, S. Sanghavi, and H. Xu, Clustering sparse graphs. Advancesin neural information processing systems. (2012) 2204–2212.
[6] Z. Chen, S. Yang, L. Li, and Z. Xie, A clustering approximation mechanism based on data spatial correlation in wireless sensor networks,
Wireless Telecommunications Symposium (WTS), 2010.
[7] H. Davenport, On a principle of Lipschitz, J. London Math. Soc. 26,(1951). 179–183. Corrigendum ibid. 39 (1964), 580.
[8] E.W. Dijkstra, A discipline of programming. Vol. 4. Englewood Cliffs:
Prentice-Hall, 1976. 129-133.
[9] T. DuBois, J. Golbeck, J. Kleint, and A. Srinivasan, Improving recommendation accuracy by clustering social networks with trust. Recommender Systems & the Social Web 532 (2009): 1-8.
[10] P. Kanani, and A. McCallum, Resource-bounded information gathering
for correlation clustering In Computational Learning Theory 07, Open
Problems Track, COLT 2007, 625-627, 2007.
[11] L.K. Hua, Introduction to Number Theory, Springer-Verlag, 1982.
[12] Z. Néda, F. Răzvan, M. Ravasz, A. Libál, and G. Györgyi, Phasetransition in an optimal clusterization model Physica A: Statistical
Mechanics and its Applications, 362 (2):357–368, 2006.
[13] J. E. Nymann, On the probability that k positive integers are relatively
prime, J. Number Theory 4 (1972), 469–473.
[14] J. B. Rosser, and L. Schoenfeld, Approximate formulas for somefunctions of prime numbers, Illinois J. Math. 6 (1962), 64–94.
[15] K. Sungwoong, S. Nowozin, P. Kohli, and D. Y. Chang, Higher-Order
Correlation Clustering for Image Segmentation, In: Advances in Neural
Information Processing Systems 24. J. Shawe-Taylor, R.S. Zemel, P.L.
Bartlett, F. Pereira, and K.Q. Weinberger, Curran Associates, Inc. 1530–
1538, 2011.
[16] B. Yang, W. K. Cheung, and J. Liu, Community mining from signedsocial networks, IEEE Transactions on Knowledge and Data Engineering
19 10 (2007): 1333-1348.
[17] H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978),127–185.