140
Chapter 10. Combining directed and signed embeddings
ing positive edges, and outgoing positive edges. The edges of the original graph are
connected to these nodes in the obvious way. The four versions of each node are
then connected to each other by an undirected four-clique whose edge weights are
the sum of (the absolute values of) the incident weight of the original version of the
node. Thus both incident positive and negative edges act to make the nexus more
closely bound.
Let W + be the directed adjacency matrix representing the positive edges; W −
the directed adjacency matrix representing the negative edges (so both matrices containing only non-negative entries); DP in and DN in the indegrees of the two adjacency
matrices, and DP out and DN out their outdegrees. The weights on the edges joining
the new versions of the ith node will be the sum of the ith entries of these vectors.
Let D be the matrix with these weights on the diagonal.
Figure 10.1: Replication of each node first into positive and negative versions and
then into in- and out-versions
Define a matrix in which the four versions are connected in a clique as shown
in Figure 10.1. First, each node is duplicated and the positive edges connected to one
copy and the negative edges to the other. Then each of these nodes is duplicated and
the incoming edges connected to one and the outgoing edges to the other. Finally, a
clique is added to connect the four versions of each original node.
More formally, define the adjacency matrix for the graph that captures the
signed structure of the network by:
X =
W + + D
D
D
−W − + D
(10.1)
If the network contains n nodes, then X is a 2n × 2n matrix, but as usual the
added pieces are only diagonals (so linear in n) and, if W + and W − are sparse, then
so is X.
Let bigD be the 2n × 2n matrix:
bigD =
0 D
D 0
and then define a 4n × 4n matrix:
M =
bigD
X
X
bigD
(10.2)
Chapter 10. Combining directed and signed embeddings
ing positive edges, and outgoing positive edges. The edges of the original graph are
connected to these nodes in the obvious way. The four versions of each node are
then connected to each other by an undirected four-clique whose edge weights are
the sum of (the absolute values of) the incident weight of the original version of the
node. Thus both incident positive and negative edges act to make the nexus more
closely bound.
Let W + be the directed adjacency matrix representing the positive edges; W −
the directed adjacency matrix representing the negative edges (so both matrices containing only non-negative entries); DP in and DN in the indegrees of the two adjacency
matrices, and DP out and DN out their outdegrees. The weights on the edges joining
the new versions of the ith node will be the sum of the ith entries of these vectors.
Let D be the matrix with these weights on the diagonal.
Figure 10.1: Replication of each node first into positive and negative versions and
then into in- and out-versions
Define a matrix in which the four versions are connected in a clique as shown
in Figure 10.1. First, each node is duplicated and the positive edges connected to one
copy and the negative edges to the other. Then each of these nodes is duplicated and
the incoming edges connected to one and the outgoing edges to the other. Finally, a
clique is added to connect the four versions of each original node.
More formally, define the adjacency matrix for the graph that captures the
signed structure of the network by:
X =
W + + D
D
D
−W − + D
(10.1)
If the network contains n nodes, then X is a 2n × 2n matrix, but as usual the
added pieces are only diagonals (so linear in n) and, if W + and W − are sparse, then
so is X.
Let bigD be the 2n × 2n matrix:
bigD =
0 D
D 0
and then define a 4n × 4n matrix:
M =
bigD
X
X
bigD
(10.2)