Appendix E
Signed normalized
Laplacian L bns clustering
In the case k = 2, we use the same defined indicator vector u as in Appendix D:
n
∑
i, j=1
w
−
i j u
2
i =
n
∑
i=1
d
−
i u
2
i
= ∑
i∈A
d
−
i
vol(A)
vol(A)
+ ∑
i∈A
d
−
i
vol(A)
vol(A)
=
vol − (A)vol(A)
vol(A)
+
vol − (A)vol(A)
vol(A)
=
vol − (A)vol(V )
vol(A)
− vol
− (A) +
vol − (A)vol(V )
vol(A)
− vol
− (A)
=
vol − (A)vol(V )
vol(A)
+
vol − (A)vol(V )
vol(A)
− vol
− (V ).
Then,
u
(D
+ −W )u =
n
∑
i, j=1
1
2
w i j (u i − u j )
2 + w
−
i j u
2
i
=
cut
+ (A, A) − cut
− (A, A)
vol(V )
vol(A)
+
vol(V )
vol(A)
+
vol − (A)vol(V )
vol(A)
+
vol − (A)vol(V )
vol(A)
− vol
− (V )
=vol(V ) ∗ BNScut(A, A) − vol
− (V )
Thus, R L bns (u) = BNScut(A, A) − vol − (V )/vol(V ).
Since vol − (V )/vol(V ) is constant for a graph, the problem of minimizing
BNScut(A, A) can be equivalently rewritten as: min
A⊂V
R L bns (u).
181