164
Appendix A. RatioCut consistency with two versions of each node
and x V 2 into two different groups A and A as shown in Figure A.1. Thus
min RatioCut = RatioCut(A, A) =
cut(A, A)
|A|
+
cut(A, A)
|A|
=
cut(A, A) ∗ 2n
|A||A|
,
where |A| is the number of the nodes in group A.
By moving x V 2 to A, we get
RatioCut(A + x V 2 , A − x V 2 ) =
cut(A + x V 2 , A − x V 2 ) ∗ 2n
|A + x V 2 ||A − x V 2 |
=
cut(A + x V 2 , A − x V 2 ) ∗ 2n
(|A| + 1)(|A| − 1)
=
cut(A, A) − (d V 1x + d V 2x + q) + (d V 2x −q)
∗2n
(|A| + 1)(|A| − 1)
=
cut(A, A) − d V 1x − 2q
∗ 2n
|A||A| − |A| + |A| − 1
.
Similarly by moving x V 1 to A, we get
RatioCut(A − x V 1 , A + x V 1 ) =
cut(A − x V 1 , A + x V 1 ) ∗ 2n
|A − x V 1 ||A + x V 1 |
=
cut(A, A) − (d V 1x + d V 2x + p) + (d V 1x − p)
∗2n
(|A| − 1)(|A| + 1)
=
cut(A, A) − d V 2x − 2p
∗ 2n
|A||A| + |A| − |A| − 1
.
Since the RatioCut(A, A) is the minimum,
RatioCut(A, A) ≤ RatioCut(A + x V 2 , A − x V 2 )
=⇒
cut(A, A)
|A||A|
≤
cut(A, A) − d V 1x − 2q
|A||A| − |A| + |A| − 1
(A.1)
and RatioCut(A, A) ≤ RatioCut(A − x V 1 , A + x V 1 )
=⇒
cut(A, A)
|A||A|
≤
cut(A, A) − d V 2x − 2p
|A||A| + |A| − |A| − 1
.
(A.2)
We have an even number of nodes in our layered model graph M, if |A| > |A|, then
|A| ≥ |A| + 2. Thus, |A||A| < |A||A| + |A| − |A| − 1. Furthermore, d V 2x ≥ 0 and p ≥ 0.
This implies that (A.2) is not true. Similarly, (A.1) is not true if |A| < |A|.
If |A| = |A|, there is at least one other pair of nodes y V 1 and y V 2 that is separated
into two different groups. By moving x V 1 and x V 2 into one group and y V 1 and y V 2 into
another, the cut value will be reduced, although the number of nodes in each group
is the same as before. This implies RatioCut(A, A) is not the minimum RatioCut if
|A| = |A|.