8.2. Unnormalized spectral Laplacians of signed graphs
99
approach to signed networks by defining a signed graph Laplacian as:
L = D −W = D
+ + D
− −W
+ +W
−
However, there are several difficulties with this definition. We will instead define:
L sign = D
+ − D
− −W = (D
+ −W
+ ) − (D
− −W
− )
and show that it leads to a more natural embedding.
8.2.1 Rayleigh quotients of signed unnormalized
Laplacians
As usual, the Rayleigh quotient provides some insight into the property that the
Laplacian captures. The Rayleigh quotient of the Kunegis Laplacian, L, is:
R L ( f ) =
f L f
f 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 f 2
i
In the numerator, the first term is the sum of the squared distances between positively
connected nodes, the same as for the conventional Laplacian. However, the second
term is the square of terms associated with nodes connected by negative edges. As
a result, the Rayleigh quotient is made smaller by embedding the negatively connected nodes symmetrically around the origin. There is a certain logic to this, since
it certainly tends to place a given pair of negatively connected nodes far apart, but its
global effect is hard to determine and, as we will show, turns out not to be appropriate.
Figure 8.1(a) shows the signed Laplacian L embedding of a toy graph. In the
toy graph, nodes 1, 3, and 5 are positively connected to nodes 2, 4, and 6, respectively, and nodes 2, 4, and 6 are negative connected to each other. Consider the
relationship between node 1 and node 4. Although nodes 2 and 4 are antagonistic
to one another, it does not seem appropriate that the positive relationship between
nodes 1 and 2 should make node 1 more hostile to node 4 than node 2 is. Figure
8.1(a) suggests that the L embedding does not model transitivity of positive and negative connections as it should.
The natural way to deal with negative edges is to maximize the distances between the pairs of nodes that they connect, regardless of where those nodes want to
be embedded given the structure of the rest of the graph. In other words, the problem
with the Kunegis approach is that negatively connected nodes are forced to be on
opposite sides of the origin, when simply being far apart is enough.
Our definition of an unnormalized Laplacian matrix for signed graphs, L sign ,
uses this intuition. The corresponding Rayleigh quotient is:
R L sign ( f ) =
f L sign f
f 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 f 2
i
.
99
approach to signed networks by defining a signed graph Laplacian as:
L = D −W = D
+ + D
− −W
+ +W
−
However, there are several difficulties with this definition. We will instead define:
L sign = D
+ − D
− −W = (D
+ −W
+ ) − (D
− −W
− )
and show that it leads to a more natural embedding.
8.2.1 Rayleigh quotients of signed unnormalized
Laplacians
As usual, the Rayleigh quotient provides some insight into the property that the
Laplacian captures. The Rayleigh quotient of the Kunegis Laplacian, L, is:
R L ( f ) =
f L f
f 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 f 2
i
In the numerator, the first term is the sum of the squared distances between positively
connected nodes, the same as for the conventional Laplacian. However, the second
term is the square of terms associated with nodes connected by negative edges. As
a result, the Rayleigh quotient is made smaller by embedding the negatively connected nodes symmetrically around the origin. There is a certain logic to this, since
it certainly tends to place a given pair of negatively connected nodes far apart, but its
global effect is hard to determine and, as we will show, turns out not to be appropriate.
Figure 8.1(a) shows the signed Laplacian L embedding of a toy graph. In the
toy graph, nodes 1, 3, and 5 are positively connected to nodes 2, 4, and 6, respectively, and nodes 2, 4, and 6 are negative connected to each other. Consider the
relationship between node 1 and node 4. Although nodes 2 and 4 are antagonistic
to one another, it does not seem appropriate that the positive relationship between
nodes 1 and 2 should make node 1 more hostile to node 4 than node 2 is. Figure
8.1(a) suggests that the L embedding does not model transitivity of positive and negative connections as it should.
The natural way to deal with negative edges is to maximize the distances between the pairs of nodes that they connect, regardless of where those nodes want to
be embedded given the structure of the rest of the graph. In other words, the problem
with the Kunegis approach is that negatively connected nodes are forced to be on
opposite sides of the origin, when simply being far apart is enough.
Our definition of an unnormalized Laplacian matrix for signed graphs, L sign ,
uses this intuition. The corresponding Rayleigh quotient is:
R L sign ( f ) =
f L sign f
f 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 f 2
i
.