5.4. Summary
67
Figure 5.17: Edges between the in and out versions of each node from the 10th
component
5.4 Summary
A second way in which edges can have rich properties is by being directed — representing relationships that are of different intensities between the same two individuals. Such asymmetries are common in the real world. They cause difficulties
for the spectral embedding approach, however, because the natural representation
as an adjacency matrix is asymmetric, but spectral embeddings require symmetric
matrices.
Chung’s approach represents a well-motivated way to compute a symmetric
Laplacian from an asymmetric adjacency matrix. However, it has two weaknesses:
for most matrices, the “Google trick” has to be used to address reducibility, which
in turn makes the matrices dense, with substantial performance costs; and as a result
it tends to fold peripheral nodes inwards in the embedding, creating a misleading
impression of their importance.
We have shown that a variation of the layer approach can avoid all of these
problems. By creating a bipartite layered graph of undirected edges, the computations can remain sparse, the eigendecomposition can be done using SVD, and we
get new information about net flow from the lengths of the edges between in and out
versions of the same node.
Notes
The simplest way to convert a directed matrix into an undirected matrix is to ignore the directionality of edges via the transformation W = W +W , where W is the
directed matrix and W is the resulting symmetric matrix. This ignores the useful
information of edge direction.
67
Figure 5.17: Edges between the in and out versions of each node from the 10th
component
5.4 Summary
A second way in which edges can have rich properties is by being directed — representing relationships that are of different intensities between the same two individuals. Such asymmetries are common in the real world. They cause difficulties
for the spectral embedding approach, however, because the natural representation
as an adjacency matrix is asymmetric, but spectral embeddings require symmetric
matrices.
Chung’s approach represents a well-motivated way to compute a symmetric
Laplacian from an asymmetric adjacency matrix. However, it has two weaknesses:
for most matrices, the “Google trick” has to be used to address reducibility, which
in turn makes the matrices dense, with substantial performance costs; and as a result
it tends to fold peripheral nodes inwards in the embedding, creating a misleading
impression of their importance.
We have shown that a variation of the layer approach can avoid all of these
problems. By creating a bipartite layered graph of undirected edges, the computations can remain sparse, the eigendecomposition can be done using SVD, and we
get new information about net flow from the lengths of the edges between in and out
versions of the same node.
Notes
The simplest way to convert a directed matrix into an undirected matrix is to ignore the directionality of edges via the transformation W = W +W , where W is the
directed matrix and W is the resulting symmetric matrix. This ignores the useful
information of edge direction.