42
Chapter 5. Modelling asymmetric relationships
small:
R( f ) =
∑
n
i, j=1 π i P i j ( f i − f j ) 2
2 ∑
n
i=1 π i f 2
i
where P is the random-walk matrix and π is a measure of the importance of the ith
node. In other words, this function tries to place well-connected important nodes
close together.
P is defined by P i j = W i j /d i or, if D is the diagonal degree matrix, by P =
D −1 W This implies d P = 1 DP = 1 W = d for the undirected case. π is computed
as the principal left eigenvector of the transition matrix P with the corresponding
eigenvalue 1, that is π P = π . Thus π = d/ ∑
n
i=1 d i for undirected graphs. In other
words, for an undirected graph, the degree of a node is directly interpretable as its
importance. The importance of a node is proportional to its accessibility to a random
walker, which is equivalent to the proportion of time a random walker spends at that
node.
In a directed graph, the relationship between degree and importance is more
subtle. From a random-walk perspective, the fraction of time that a random walker
spends at a particular node does not just depend on the total weight of its incoming
edges. It also depends on how accessible its upstream nodes are, which in turn
depends on the weight of the incoming edges to those upstream nodes, and so on.
Thus importance is a property that depends on the global structure of the network,
rather than being a mostly local property as it is for an undirected graph.
The π i in this Rayleigh quotient plays the role of degree in earlier Laplacians.
It captures the property of global importance, and therefore requires that the embeddings of important nodes count for more in the objective function that the Rayleigh
quotient describes. Computing these π i s requires a global computation; they are
the elements of the principal left eigenvector of the transition matrix, P. Call this
eigenvector Π. (Note the similarity to the PageRank calculation used for ranking by
Google.)
Based on this Rayleigh quotient, we define the symmetric Laplacian as:
ˆ
L dir = I −
Π 1/2 PΠ −1/2 + Π −1/2 P Π 1/2
2
and the combinatorial Laplacian as:
L dir = Π −
ΠP + P Π
2
Both of these Laplacians are more sophisticated versions of symmetrizing a matrix
by adding its transpose; in this case adjusting the entries based on the global importance of each node.
It can be proved that
R( f ) =
< f L dir , f >
< f Π, f >
=
< g ˆ
L dir , g >
< g, g >
where g = Π 1/2 f .
Chapter 5. Modelling asymmetric relationships
small:
R( f ) =
∑
n
i, j=1 π i P i j ( f i − f j ) 2
2 ∑
n
i=1 π i f 2
i
where P is the random-walk matrix and π is a measure of the importance of the ith
node. In other words, this function tries to place well-connected important nodes
close together.
P is defined by P i j = W i j /d i or, if D is the diagonal degree matrix, by P =
D −1 W This implies d P = 1 DP = 1 W = d for the undirected case. π is computed
as the principal left eigenvector of the transition matrix P with the corresponding
eigenvalue 1, that is π P = π . Thus π = d/ ∑
n
i=1 d i for undirected graphs. In other
words, for an undirected graph, the degree of a node is directly interpretable as its
importance. The importance of a node is proportional to its accessibility to a random
walker, which is equivalent to the proportion of time a random walker spends at that
node.
In a directed graph, the relationship between degree and importance is more
subtle. From a random-walk perspective, the fraction of time that a random walker
spends at a particular node does not just depend on the total weight of its incoming
edges. It also depends on how accessible its upstream nodes are, which in turn
depends on the weight of the incoming edges to those upstream nodes, and so on.
Thus importance is a property that depends on the global structure of the network,
rather than being a mostly local property as it is for an undirected graph.
The π i in this Rayleigh quotient plays the role of degree in earlier Laplacians.
It captures the property of global importance, and therefore requires that the embeddings of important nodes count for more in the objective function that the Rayleigh
quotient describes. Computing these π i s requires a global computation; they are
the elements of the principal left eigenvector of the transition matrix, P. Call this
eigenvector Π. (Note the similarity to the PageRank calculation used for ranking by
Google.)
Based on this Rayleigh quotient, we define the symmetric Laplacian as:
ˆ
L dir = I −
Π 1/2 PΠ −1/2 + Π −1/2 P Π 1/2
2
and the combinatorial Laplacian as:
L dir = Π −
ΠP + P Π
2
Both of these Laplacians are more sophisticated versions of symmetrizing a matrix
by adding its transpose; in this case adjusting the entries based on the global importance of each node.
It can be proved that
R( f ) =
< f L dir , f >
< f Π, f >
=
< g ˆ
L dir , g >
< g, g >
where g = Π 1/2 f .