44
Chapter 5. Modelling asymmetric relationships
and use an eigendecomposition to embed L in the standard way.
The drawbacks of the Chung approach are not trivial. Computational times are
long, even for networks of moderate size, and the resulting embedding, as we shall
show, has significant distortions.
5.2 Directed edge layered approach
We now develop a new way to embed directed networks, using our layer intuition,
but in a different way than the way it was used for typed networks. The common
theme is that we transform information about the properties of edges into patterns
of connection of those edges, which can then be simplified to undirected, untyped,
although still weighted, edges.
The key idea, as before, is to split each node v into two versions, v in and v out .
The in versions are placed in one layer, and the out versions in another.
If we have a directed edge from, say, node p to node q, then it becomes an
undirected edge from p out to q in . The out versions of each node are the connection
points for the outgoing edges of directed edges, and the in versions are the connection
points for the incoming edges. The connection pattern encodes the direction of the
edges, allowing them to be undirected in the expanded graph. The original directed
edges become connections between a layer containing the outgoing versions of each
node, and a layer containing the incoming versions of each layer.
As before, we add edges (“between the layers” but vertically) to connect v in
and v out . The weight associated with these edges is the sum of the in-degree and
out-degree of the nodes v in and v out , because this weight provably ensures that both
v in and v out will be placed in the same cluster by any reasonable clustering of the
larger graph, and also ensures that the result of the directed embedding agrees with
the embedding of the graph if edge directions are ignored.
Unlike the previous embedding of typed edges, all of the edges connect from
one layer to the other; those from the original graph as “diagonal” edges, and the
added edges as “vertical” edges. As a result, the graph is bipartite (there are no
connections within each layer).
The resulting 2n-node graph is symmetric, and so standard spectral embedding
techniques can be used to embed it. Formally, let W be the (non-symmetric) adjacency matrix of the directed graph, and D in and D out be the diagonal matrices of the
in-degrees and out-degrees, respectively: din 1 , ...din n and dout 1 , ...dout n . Let M be
the adjacency matrix of the larger graph in which nodes have been split into in and
out copies. M is a 2n × 2n matrix defined as
M =
0
W + D in + D out
W + D in + D out
0
.
Let T be the diagonal degree matrix of M with the degrees t 1out , ...t nout ,t 1in , ...t nin ,
where t iout = din i + 2 ∗ dout i and t iin = 2 ∗ din i + dout i . The corresponding Laplacian
matrices are:
L d = T − M,
Chapter 5. Modelling asymmetric relationships
and use an eigendecomposition to embed L in the standard way.
The drawbacks of the Chung approach are not trivial. Computational times are
long, even for networks of moderate size, and the resulting embedding, as we shall
show, has significant distortions.
5.2 Directed edge layered approach
We now develop a new way to embed directed networks, using our layer intuition,
but in a different way than the way it was used for typed networks. The common
theme is that we transform information about the properties of edges into patterns
of connection of those edges, which can then be simplified to undirected, untyped,
although still weighted, edges.
The key idea, as before, is to split each node v into two versions, v in and v out .
The in versions are placed in one layer, and the out versions in another.
If we have a directed edge from, say, node p to node q, then it becomes an
undirected edge from p out to q in . The out versions of each node are the connection
points for the outgoing edges of directed edges, and the in versions are the connection
points for the incoming edges. The connection pattern encodes the direction of the
edges, allowing them to be undirected in the expanded graph. The original directed
edges become connections between a layer containing the outgoing versions of each
node, and a layer containing the incoming versions of each layer.
As before, we add edges (“between the layers” but vertically) to connect v in
and v out . The weight associated with these edges is the sum of the in-degree and
out-degree of the nodes v in and v out , because this weight provably ensures that both
v in and v out will be placed in the same cluster by any reasonable clustering of the
larger graph, and also ensures that the result of the directed embedding agrees with
the embedding of the graph if edge directions are ignored.
Unlike the previous embedding of typed edges, all of the edges connect from
one layer to the other; those from the original graph as “diagonal” edges, and the
added edges as “vertical” edges. As a result, the graph is bipartite (there are no
connections within each layer).
The resulting 2n-node graph is symmetric, and so standard spectral embedding
techniques can be used to embed it. Formally, let W be the (non-symmetric) adjacency matrix of the directed graph, and D in and D out be the diagonal matrices of the
in-degrees and out-degrees, respectively: din 1 , ...din n and dout 1 , ...dout n . Let M be
the adjacency matrix of the larger graph in which nodes have been split into in and
out copies. M is a 2n × 2n matrix defined as
M =
0
W + D in + D out
W + D in + D out
0
.
Let T be the diagonal degree matrix of M with the degrees t 1out , ...t nout ,t 1in , ...t nin ,
where t iout = din i + 2 ∗ dout i and t iin = 2 ∗ din i + dout i . The corresponding Laplacian
matrices are:
L d = T − M,