5.1. Conventional directed spectral graph embedding
43
Furthermore, it is easy to prove that both Laplacians have the same eigenvalues and eigenvectors as the conventional Laplacian when the adjacency matrix is
undirected.
Since Chung’s approach is conceptually rigorous and has provable properties,
it is widely used for analyzing directed networks, for example Zhou et al. [120, 121],
Zhou and Burges [119], Huang et al. [40], Chen et al. [15], and Skillicorn and Zheng
[88].
An extra technical step is required for most directed graphs. A random walker
in a directed graph can become trapped at a sink node, one that has only incoming
edges. However, this is easy to detect because the row corresponding to that node
has no non-zero entries. The same problem, however, can happen for an entire region
of the graph — there are no outgoing edges from the region — and this is expensive
to detect in practice. The conventional solution is known as the “Google trick”. It
consists of adding a constant ε matrix to the transition matrix, allowing a random
walker to escape from any node of the graph to any other node, with some low
probability, ε.
In its use by Google, this constant matrix models the behavior of web users
who visit one page and then change to another by some process other than following
links (perhaps typing in a URL directly, or using a bookmark). For social networks
with directed relationships, the semantics of this constant matrix is more problematic. For example, if the edges are directed because they are modelling influence,
then a constant matrix models the ability of every node to influence, weakly, every
other node. It is not obvious what this might represent; perhaps something like mass
media. If edges are directed because they are modelling positive affect, then a constant matrix models a global positive feeling. These are strong assumptions which
may not be appropriate in social network applications.
The use of the Google trick also has two substantial computational drawbacks.
First, the adjacency matrix is now dense which prevents the use of sparse matrix
techniques for the eigendecompositions, and so increases the computational time
and storage required. Second, outlying nodes tend to be placed in positions folded
back towards the center of the embedding. This is because, although the added edges
are individually weak, there are many of them. This tends to make such nodes seem
to be, misleadingly, more important than they actually are.
After these refinements, Chung’s spectral embedding uses these steps [20]:
1. Convert the non-symmetric adjacency matrix of the (directed) social network
to a random walk matrix, R, by dividing each row by the row sum.
2. Add a constant matrix, ε to R, and compute its Laplacian.
3. Compute the principal left eigenvector of this Laplacian matrix and create a
diagonal matrix, Π, with these values on the diagonal.
4. Form the symmetric matrix:
L = I −
Π 1/2 L rw Π −1/2 + Π −1/2 L
rw Π 1/2
2
43
Furthermore, it is easy to prove that both Laplacians have the same eigenvalues and eigenvectors as the conventional Laplacian when the adjacency matrix is
undirected.
Since Chung’s approach is conceptually rigorous and has provable properties,
it is widely used for analyzing directed networks, for example Zhou et al. [120, 121],
Zhou and Burges [119], Huang et al. [40], Chen et al. [15], and Skillicorn and Zheng
[88].
An extra technical step is required for most directed graphs. A random walker
in a directed graph can become trapped at a sink node, one that has only incoming
edges. However, this is easy to detect because the row corresponding to that node
has no non-zero entries. The same problem, however, can happen for an entire region
of the graph — there are no outgoing edges from the region — and this is expensive
to detect in practice. The conventional solution is known as the “Google trick”. It
consists of adding a constant ε matrix to the transition matrix, allowing a random
walker to escape from any node of the graph to any other node, with some low
probability, ε.
In its use by Google, this constant matrix models the behavior of web users
who visit one page and then change to another by some process other than following
links (perhaps typing in a URL directly, or using a bookmark). For social networks
with directed relationships, the semantics of this constant matrix is more problematic. For example, if the edges are directed because they are modelling influence,
then a constant matrix models the ability of every node to influence, weakly, every
other node. It is not obvious what this might represent; perhaps something like mass
media. If edges are directed because they are modelling positive affect, then a constant matrix models a global positive feeling. These are strong assumptions which
may not be appropriate in social network applications.
The use of the Google trick also has two substantial computational drawbacks.
First, the adjacency matrix is now dense which prevents the use of sparse matrix
techniques for the eigendecompositions, and so increases the computational time
and storage required. Second, outlying nodes tend to be placed in positions folded
back towards the center of the embedding. This is because, although the added edges
are individually weak, there are many of them. This tends to make such nodes seem
to be, misleadingly, more important than they actually are.
After these refinements, Chung’s spectral embedding uses these steps [20]:
1. Convert the non-symmetric adjacency matrix of the (directed) social network
to a random walk matrix, R, by dividing each row by the row sum.
2. Add a constant matrix, ε to R, and compute its Laplacian.
3. Compute the principal left eigenvector of this Laplacian matrix and create a
diagonal matrix, Π, with these values on the diagonal.
4. Form the symmetric matrix:
L = I −
Π 1/2 L rw Π −1/2 + Π −1/2 L
rw Π 1/2
2