170
Appendix B. NCut consistency with multiple versions of each node
k = |x A | and k = |x A | be the number of copies of the node x in two partitions, where
k + k = c and k ≥ 1, k ≥ 1;
d Ax and d Ax be the total degree of nodes x A and x A without the added edges. Thus, the
total degrees of all versions of the node x in the bigger matrix M is (2c−1)(d Ax +d Ax )
since each version connects to other c − 1 versions (counting twice) and the total
given edges of the node is also counted.
Let p be the sum of edge’s weight from x A to nodes in A except x A . Let q be the sum
of edge’s weight from x A to nodes in A except x A .
Thus
min NCut = NCut(A, A) =
cut(A, A) ∗ vol(V )
vol(A)vol(A)
.
where Vol(V ) = ∑
n
i=1 ∑
c
j=1 (t i j ) = (2c − 1) ∑
n
i=1 (d Ai + d Ai ).
By moving x A to A, we get
NCut(A + x A , A − x A ) =
cut(A + x A , A − x A ) ∗ vol(V )
vol(A + x A )vol(A − x A )
=
cut(A, A) − (kd Ax +kd Ax +q) + (d Ax −q)
∗ vol(V )
(vol(A) + t Ax )(vol(A) − t Ax )
=
cut(A, A) − kd Ax − (k − 1)d Ax − 2q
∗ vol(V )
(vol(A) + kd Ax + (c + k − 1)d Ax )(vol(A) − kd Ax − (c + k − 1)d Ax )
.
Similarly by moving x A to A, we get
NCut(A−x A , A + x A ) =
cut(A − x A , A + x A ) ∗ vol(V )
vol(A − x A )vol(A + x A )
=
cut(A, A) − kd Ax − (k − 1)d Ax − 2p
∗ vol(V )
(vol(A) − kd Ax − (c + k − 1)d Ax )(vol(A) + kd Ax + (c + k − 1)d Ax )
.
Since the NCut(A, A) is the minimum,
NCut(A, A) ≤ NCut(A + x A , A − x A )
=⇒
cut(A, A)
vol(A)vol(A)
≤
cut(A, A) − kd Ax − (k − 1)d Ax − 2q
(vol(A) + kd Ax + (c + k − 1)d Ax )(vol(A) − kd Ax − (c + k − 1)d Ax )
(B.5)
and
NCut(A, A) ≤ NCut(A − x A , A + x A )
=⇒
cut(A, A)
vol(A)vol(A)
≤
cut(A, A) − kd Ax − (k − 1)d Ax − 2p
(vol(A) − kd Ax − (c + k − 1)d Ax )(vol(A) + kd Ax + (c + k − 1)d Ax )
.
(B.6)