Chapter 5
Modelling asymmetric
relationships
We have seen that there are advantages to modelling connections between nodes in
a social network as edges of qualitatively different types. We now turn to settings
in which it is appropriate to represent edges as having a direction, from one node
to another node. Arguably this is actually the normal case. Experiments with social groups have shown that relationships are rarely symmetric; A believes that B is
a close friend, while B believes that A is an acquaintance. There are also many settings where direction is obvious: a hierarchical organization such as some businesses
and militaries, where relationship has an element of command; and networks where
relationships reflect influence or information flow from one participant to the other.
As a practical matter, edges with a direction can be represented straightforwardly in an adjacency matrix, by allowing different weights on the i jth and jith
edges. However, the adjacency matrix is now no longer symmetric. The spectral
embedding technique we have used so far requires that the adjacency matrix, and
so the Laplacian derived from it, are symmetric, so we must develop a new method
that deals with this issue. We will develop a layer approach that handles directed
graphs, but first we will review the state-of-the-art approach to spectral embedding
of directed graphs.
5.1 Conventional directed spectral graph
embedding
The conventional way to embed directed graphs is due to Chung [20]. Let W be the
asymmetric adjacency matrix of the directed graph, and P the random-walk matrix
obtained, as usual, by dividing each row by the corresponding row sum.
The following Rayleigh quotient provides some insight into what a good embedding should be like. We want to find embeddings, f , for which this function is
41
Modelling asymmetric
relationships
We have seen that there are advantages to modelling connections between nodes in
a social network as edges of qualitatively different types. We now turn to settings
in which it is appropriate to represent edges as having a direction, from one node
to another node. Arguably this is actually the normal case. Experiments with social groups have shown that relationships are rarely symmetric; A believes that B is
a close friend, while B believes that A is an acquaintance. There are also many settings where direction is obvious: a hierarchical organization such as some businesses
and militaries, where relationship has an element of command; and networks where
relationships reflect influence or information flow from one participant to the other.
As a practical matter, edges with a direction can be represented straightforwardly in an adjacency matrix, by allowing different weights on the i jth and jith
edges. However, the adjacency matrix is now no longer symmetric. The spectral
embedding technique we have used so far requires that the adjacency matrix, and
so the Laplacian derived from it, are symmetric, so we must develop a new method
that deals with this issue. We will develop a layer approach that handles directed
graphs, but first we will review the state-of-the-art approach to spectral embedding
of directed graphs.
5.1 Conventional directed spectral graph
embedding
The conventional way to embed directed graphs is due to Chung [20]. Let W be the
asymmetric adjacency matrix of the directed graph, and P the random-walk matrix
obtained, as usual, by dividing each row by the corresponding row sum.
The following Rayleigh quotient provides some insight into what a good embedding should be like. We want to find embeddings, f , for which this function is
41