102
Chapter 8. Modelling positive and negative relationships
The minimum of the Rayleigh quotient R L sign can be viewed as a relaxation of
the minimization of SRcut. The proof follows the same strategy as in von Luxburg
[101]. The details of the proof can be found in Appendix C.
8.3 Normalized spectral Laplacians of signed
graphs
Using the unnormalized Laplacian has the same issues for signed graphs as it does
for unsigned graphs, so it is natural to consider versions of the normalized Laplacians
to represent signed graphs.
Kunegis et al. [48] also proposed two versions of signed normalized Laplacians:
L rw = I − D
−1 W,
and L sym = I − D
−1/2 W D
−1/2 .
However, these two normalized Laplacians have the same issue as the Kunegis unnormalized signed Laplacian.
We restrict ourselves to the case of the random-walk Laplacian and extend it
to the signed case in a different way. We derive two normalized Laplacian matrices
for signed graphs — the simple normalized signed graph Laplacian:
L sns = D
−1 (D
+ − D
− −W ) = D
−1
(D
+ −W
+ ) − (D
− −W
− )
,
and the balanced normalized signed graph Laplacian:
L bns = D
−1 (D
+ −W ) = D
−1 (D
+ −W
+ +W
− ).
As before, we justify each in two ways: arguing from Rayleigh quotients as objective functions whose minima represent good node placement, and from cut functions that are the signed analogues of standard cuts.
8.3.1 Rayleigh quotients of signed random-walk
Laplacians
The Rayleigh quotient corresponding to Kunegis’s L rw is:
R L rw ( f ) =
f L f
f D f
=
1
2 ∑
n
i, j=1
w
+
i j ( f i − f j ) 2 + w
−
i j ( f i + f j ) 2
∑
n
i=1 d i f 2
i
.
As before, the numerator can be made smaller by placing nodes connected by negative edges on opposite sides of the origin. Figure 8.3(a) is the normalized version of
Figure 8.1(a) and shows that, as before, the L rw embedding does not model transitivity of positive and negative connections as it should.
Chapter 8. Modelling positive and negative relationships
The minimum of the Rayleigh quotient R L sign can be viewed as a relaxation of
the minimization of SRcut. The proof follows the same strategy as in von Luxburg
[101]. The details of the proof can be found in Appendix C.
8.3 Normalized spectral Laplacians of signed
graphs
Using the unnormalized Laplacian has the same issues for signed graphs as it does
for unsigned graphs, so it is natural to consider versions of the normalized Laplacians
to represent signed graphs.
Kunegis et al. [48] also proposed two versions of signed normalized Laplacians:
L rw = I − D
−1 W,
and L sym = I − D
−1/2 W D
−1/2 .
However, these two normalized Laplacians have the same issue as the Kunegis unnormalized signed Laplacian.
We restrict ourselves to the case of the random-walk Laplacian and extend it
to the signed case in a different way. We derive two normalized Laplacian matrices
for signed graphs — the simple normalized signed graph Laplacian:
L sns = D
−1 (D
+ − D
− −W ) = D
−1
(D
+ −W
+ ) − (D
− −W
− )
,
and the balanced normalized signed graph Laplacian:
L bns = D
−1 (D
+ −W ) = D
−1 (D
+ −W
+ +W
− ).
As before, we justify each in two ways: arguing from Rayleigh quotients as objective functions whose minima represent good node placement, and from cut functions that are the signed analogues of standard cuts.
8.3.1 Rayleigh quotients of signed random-walk
Laplacians
The Rayleigh quotient corresponding to Kunegis’s L rw is:
R L rw ( f ) =
f L f
f D f
=
1
2 ∑
n
i, j=1
w
+
i j ( f i − f j ) 2 + w
−
i j ( f i + f j ) 2
∑
n
i=1 d i f 2
i
.
As before, the numerator can be made smaller by placing nodes connected by negative edges on opposite sides of the origin. Figure 8.3(a) is the normalized version of
Figure 8.1(a) and shows that, as before, the L rw embedding does not model transitivity of positive and negative connections as it should.