2.2. Building layered models
15
flow between the two networks.
In the example so far, the edges connecting different versions have been vertical, but we will generalize the construction to allow “diagonal” edges for some
settings as well.
We have not yet explained how weights are assigned to the edges between
layers. This is obviously a critical choice, since it determines how closely each of
the layers is aligned to the other. Choosing small weights means that the embedding
of each layer will mostly depend on the structure in that layer; choosing large weights
will force the versions of the same nodes to be embedded close together, so that the
structures in one layer will distort the structures in the other layer more strongly.
There are principled ways to choose these new weights. We motivate them
based on the idea of a random walk in the graph.
We can convert the adjacency matrix to a random-walk matrix by dividing
the entries in each row by the sum of that row. The entries are all therefore values
between 0 and 1, and the sum of each row is 1. Now imagine a random walker who
moves around the graph in discrete steps, with the i jth entry of the random-walk
matrix interpreted as the probability that the random walker who is currently at node
i will move to node j in the next step. Because the outgoing edge weights sum to 1,
a random walker is more likely to choose an edge with a higher weight than one with
a lower weight.
This random-walk view of a graph is both intuitive and analytically helpful.
For example, the fraction of time that a walker spends at a particular node, summed
over a long sequence of probabilistic wandering steps, provides an estimate of how
important that node is in the graph. Important nodes are visited often; less important
nodes are visited less often.
This random-walk behavior is more stable if it is made lazy. The probabilities
for each of the outgoing edges are divided by 2, so their sum is 0.5, and the other 0.5
probability is assigned to a self-loop at each node. In other words, at each step the
random walker either stays put at the current node with probability 0.5, or takes one
of the outgoing edges with probabilities proportional to their edge weights, which
are all half what they were in the original random-walk scenario.
We use the idea of lazy random walks to motivate the choice of edge weights
for the vertical edges. In particular, we allocate the “lazy” part of the probability to
the vertical edges, giving them a total weight of 0.5. In the random-walk version of
the larger adjacency matrix, therefore, the row sums of the submatrices on the main
diagonal are 0.5, while the off-main-diagonal matrices are diagonal submatrices with
0.5 on the diameter. We model a random walker in the expanded graph as remaining
within the current layer with probability 0.5, or moving to one of the other layers
with total probability 0.5. If we ignore the typing of the edges, that is we take a
monochrome view of the graph, then the random walker moves in the conventional
lazy way, with the layer transitions appearing as self-loops.
So far, we have only considered two layers. If there are, say, c layers then the
vertical edges between the c versions of the same node form a c-clique with total
edge weight 0.5. In other words, if a random walker leaves the current layer, it has
15
flow between the two networks.
In the example so far, the edges connecting different versions have been vertical, but we will generalize the construction to allow “diagonal” edges for some
settings as well.
We have not yet explained how weights are assigned to the edges between
layers. This is obviously a critical choice, since it determines how closely each of
the layers is aligned to the other. Choosing small weights means that the embedding
of each layer will mostly depend on the structure in that layer; choosing large weights
will force the versions of the same nodes to be embedded close together, so that the
structures in one layer will distort the structures in the other layer more strongly.
There are principled ways to choose these new weights. We motivate them
based on the idea of a random walk in the graph.
We can convert the adjacency matrix to a random-walk matrix by dividing
the entries in each row by the sum of that row. The entries are all therefore values
between 0 and 1, and the sum of each row is 1. Now imagine a random walker who
moves around the graph in discrete steps, with the i jth entry of the random-walk
matrix interpreted as the probability that the random walker who is currently at node
i will move to node j in the next step. Because the outgoing edge weights sum to 1,
a random walker is more likely to choose an edge with a higher weight than one with
a lower weight.
This random-walk view of a graph is both intuitive and analytically helpful.
For example, the fraction of time that a walker spends at a particular node, summed
over a long sequence of probabilistic wandering steps, provides an estimate of how
important that node is in the graph. Important nodes are visited often; less important
nodes are visited less often.
This random-walk behavior is more stable if it is made lazy. The probabilities
for each of the outgoing edges are divided by 2, so their sum is 0.5, and the other 0.5
probability is assigned to a self-loop at each node. In other words, at each step the
random walker either stays put at the current node with probability 0.5, or takes one
of the outgoing edges with probabilities proportional to their edge weights, which
are all half what they were in the original random-walk scenario.
We use the idea of lazy random walks to motivate the choice of edge weights
for the vertical edges. In particular, we allocate the “lazy” part of the probability to
the vertical edges, giving them a total weight of 0.5. In the random-walk version of
the larger adjacency matrix, therefore, the row sums of the submatrices on the main
diagonal are 0.5, while the off-main-diagonal matrices are diagonal submatrices with
0.5 on the diameter. We model a random walker in the expanded graph as remaining
within the current layer with probability 0.5, or moving to one of the other layers
with total probability 0.5. If we ignore the typing of the edges, that is we take a
monochrome view of the graph, then the random walker moves in the conventional
lazy way, with the layer transitions appearing as self-loops.
So far, we have only considered two layers. If there are, say, c layers then the
vertical edges between the c versions of the same node form a c-clique with total
edge weight 0.5. In other words, if a random walker leaves the current layer, it has