8.4. Applications of signed networks
105
We define two normalized signed cuts:
SNScut(A 1 , ..., A k ) =
k
∑
i=1
W + (A i , A i ) −W − (A i , A i )
vol(A i )
=
k
∑
i=1
cut + (A i , A i ) − cut − (A i , A i )
vol(A i )
BNScut(A 1 , ..., A k ) =
k
∑
i=1
W + (A i , A i ) +W − (A i , A i )
vol(A i )
=
k
∑
i=1
W + (A i , A i ) +W − (A i ,V ) −W − (A i , A i )
vol(A i )
=
k
∑
i=1
cut + (A i , A i ) + vol − (A i ) − cut − (A i , A i )
vol(A i )
Both objective functions are derived from the normalized cut for signed graphs. The
minimum of the SNScut function tries to find a solution with the fewest positive
edges and the most negative edges between groups. The solution based on BNScut
function tries to minimize the positive edges between groups and the negative edges
within each group. These sound equivalent, since the maximum of the negative edges
between groups is equal to the minimum of the negative edges within each group,
that is W − (A i , A i ) = vol − (A i ) − cut − (A i , A i ). However, there will be a difference
between the mimima when vol(A i ) of each group A i is considered. The difference
between the two normalized signed cut objective functions leads to two different
normalized signed Laplacian clusterings.
SNScut corresponds to the Laplacian matrix L sns and BNScut corresponds to
the Laplacian matrix L bns . We prove this using the same strategy as in von Luxburg
[101]. The details of the proofs can be found in Appendix D and Appendix E for L sns
and L bns , respectively.
These proofs show that our definitions of Laplacian matrices, derived from a
Rayleigh quotient point of view, agree with reasonable definitions of cuts for signed
graphs. As usual, the quality of the solution to the relaxed problem is not guaranteed
to be optimal, but is almost always good in practice [101].
8.4 Applications of signed networks
Our embedding approach allows the question of how to model the enemy of my
enemy to be answered rigorously. Figure 8.4 shows two embeddings of graphs containing only negative edges. In both cases, it is clear that the edges from “me” to
my enemy, and from my enemy to his enemy are approximately orthogonal. In other
words, the enemy of my enemy is embedded exactly in between complete reflexivity
and complete transitivity — the embedding algorithm is agnostic about the behavior
of transitivity in the absence of other information (for example, other positive edges).
This intuitive result also answers the question about how many dimensions
should be retained in an embedding to get good results from a clustering algorithm.
105
We define two normalized signed cuts:
SNScut(A 1 , ..., A k ) =
k
∑
i=1
W + (A i , A i ) −W − (A i , A i )
vol(A i )
=
k
∑
i=1
cut + (A i , A i ) − cut − (A i , A i )
vol(A i )
BNScut(A 1 , ..., A k ) =
k
∑
i=1
W + (A i , A i ) +W − (A i , A i )
vol(A i )
=
k
∑
i=1
W + (A i , A i ) +W − (A i ,V ) −W − (A i , A i )
vol(A i )
=
k
∑
i=1
cut + (A i , A i ) + vol − (A i ) − cut − (A i , A i )
vol(A i )
Both objective functions are derived from the normalized cut for signed graphs. The
minimum of the SNScut function tries to find a solution with the fewest positive
edges and the most negative edges between groups. The solution based on BNScut
function tries to minimize the positive edges between groups and the negative edges
within each group. These sound equivalent, since the maximum of the negative edges
between groups is equal to the minimum of the negative edges within each group,
that is W − (A i , A i ) = vol − (A i ) − cut − (A i , A i ). However, there will be a difference
between the mimima when vol(A i ) of each group A i is considered. The difference
between the two normalized signed cut objective functions leads to two different
normalized signed Laplacian clusterings.
SNScut corresponds to the Laplacian matrix L sns and BNScut corresponds to
the Laplacian matrix L bns . We prove this using the same strategy as in von Luxburg
[101]. The details of the proofs can be found in Appendix D and Appendix E for L sns
and L bns , respectively.
These proofs show that our definitions of Laplacian matrices, derived from a
Rayleigh quotient point of view, agree with reasonable definitions of cuts for signed
graphs. As usual, the quality of the solution to the relaxed problem is not guaranteed
to be optimal, but is almost always good in practice [101].
8.4 Applications of signed networks
Our embedding approach allows the question of how to model the enemy of my
enemy to be answered rigorously. Figure 8.4 shows two embeddings of graphs containing only negative edges. In both cases, it is clear that the edges from “me” to
my enemy, and from my enemy to his enemy are approximately orthogonal. In other
words, the enemy of my enemy is embedded exactly in between complete reflexivity
and complete transitivity — the embedding algorithm is agnostic about the behavior
of transitivity in the absence of other information (for example, other positive edges).
This intuitive result also answers the question about how many dimensions
should be retained in an embedding to get good results from a clustering algorithm.