Appendix B
NCut consistency with
multiple versions of each
node
Theorem 2: The versions of a node will be placed in the same cluster based on
NCut with multiple versions of each node, when the added edge weight between two
versions of a same node is equal to the sum of the degrees of the two versions.
Proof of NCut consistency with two versions of each node (c = 2): Following the illustration of Figure A.1, assume there is a minimum NCut which separates
at least a pair of nodes x V 1 and x V 2 into two different groups A and A, as shown in
Figure A.1. Thus
min NCut = NCut(A, A) =
cut(A, A)
vol(A)
+
cut(A, A)
vol(A)
=
cut(A, A) ∗ vol(V )
vol(A)vol(A)
,
where vol(A) is the degree summation of the nodes in group A, and vol(V ) is the
degree summation of all the nodes in our double copy structure, means Vol(V ) =
∑
n
i=1 (t V 1i + t V 2i ) = 3 ∑
n
i=1 (d V 1i + d V 2i ). Here t V 1i = 2d V 1i + d V 2i and t V 2i = d V 1i +
2d V 2i are the total degrees of the two versions of node i in the bigger graph M.
By moving x V 2 to A, we get
NCut(A + x V 2 , A − x V 2 ) =
cut(A + x V 2 , A − x V 2 ) ∗ vol(V )
vol(A + x V 2 )vol(A − x V 2 )
=
cut(A, A) − (d V 1x +d V 2x +q) + (d V 2x −q)
∗ vol(V )
(vol(A) + t V 2x )(vol(A) − t V 2x )
=
cut(A, A) − d V 1x − 2q
∗ vol(V )
(vol(A) + d V 1x + 2d V 2x )(vol(A) − d V 1x − 2d V 2x )
.
167