48
Chapter 5. Modelling asymmetric relationships
3. Compute the first k singular values α i and the corresponding singular vectors
u i and v i of A.
4. Modify and combine the embedding vectors as:
f i =
(2D out + D in ) −1/2 u i
(2D in + D out ) −1/2 v i
.
and embed the graph into k − 1 dimensions by using the k − 1 vectors f i (omitting the trivial vector 1 with singular value 1).
The range of eigenvalues λ of the directed Laplacian matrix L drw is from 0
and 2. However, the range of singular values α of matrix A is between 0 and 1. The
eigenvalues of the other “half” of L drw are λ 2n−i = 2 − α i with eigenvectors
f 2n−i =
(2D out + D in ) −1/2 u i
−(2D in + D out ) −1/2 v i
In contrast to previous approaches, our directed graph embedding has the following advantages:
1. The directional information about each original edge is now encoded by the
structure of the (undirected) connections between the new versions of the original nodes; that is, the graph to be embedded is now undirected. This avoids
the need to use the Google trick to address reducibility, and therefore keeps
the graph sparse. This is a great performance advantage.
2. Because the (expanded) graph is undirected, there is no need to compute a left
eigenvector to determine each node’s importance. Degree in the undirected
graph, a local property, suffices.
These two advantages are obtained at the cost of making the graph nominally twice
as big, but the additional cost remains linear in the original size of the network;
we can use sparse matrix decomposition techniques, and so this adds only a small
constant factor.
5.3 Applications of directed networks
We have shown that our methods are mathematically well behaved and motivated.
As applications of our methods for embedding and clustering, we use a synthetic
dataset and four real-world directed networks to demonstrate the effectiveness of the
directed graph spectral embedding. By comparing our results with Chung’s directed
embeddings we show how our approach is an improvement.
In the embedding of directed networks, there are two versions of each node,
one corresponding to incoming edges and the other to outgoing edges. The position
of each member of a pair is important, but so is their distance from one another —
Chapter 5. Modelling asymmetric relationships
3. Compute the first k singular values α i and the corresponding singular vectors
u i and v i of A.
4. Modify and combine the embedding vectors as:
f i =
(2D out + D in ) −1/2 u i
(2D in + D out ) −1/2 v i
.
and embed the graph into k − 1 dimensions by using the k − 1 vectors f i (omitting the trivial vector 1 with singular value 1).
The range of eigenvalues λ of the directed Laplacian matrix L drw is from 0
and 2. However, the range of singular values α of matrix A is between 0 and 1. The
eigenvalues of the other “half” of L drw are λ 2n−i = 2 − α i with eigenvectors
f 2n−i =
(2D out + D in ) −1/2 u i
−(2D in + D out ) −1/2 v i
In contrast to previous approaches, our directed graph embedding has the following advantages:
1. The directional information about each original edge is now encoded by the
structure of the (undirected) connections between the new versions of the original nodes; that is, the graph to be embedded is now undirected. This avoids
the need to use the Google trick to address reducibility, and therefore keeps
the graph sparse. This is a great performance advantage.
2. Because the (expanded) graph is undirected, there is no need to compute a left
eigenvector to determine each node’s importance. Degree in the undirected
graph, a local property, suffices.
These two advantages are obtained at the cost of making the graph nominally twice
as big, but the additional cost remains linear in the original size of the network;
we can use sparse matrix decomposition techniques, and so this adds only a small
constant factor.
5.3 Applications of directed networks
We have shown that our methods are mathematically well behaved and motivated.
As applications of our methods for embedding and clustering, we use a synthetic
dataset and four real-world directed networks to demonstrate the effectiveness of the
directed graph spectral embedding. By comparing our results with Chung’s directed
embeddings we show how our approach is an improvement.
In the embedding of directed networks, there are two versions of each node,
one corresponding to incoming edges and the other to outgoing edges. The position
of each member of a pair is important, but so is their distance from one another —