84
Chapter 7. Modelling relationships that change over time
network at one time has on its structure at other times, and so is a critical choice for
the global model. We prefer to use a larger value of β in order to align the embedding
of each node across time. As a result, this will also tend to align the larger structures
such as clusters, communities, and cuts.
We have already seen that most realistic social networks have edges that are
directed, so we also want to be able to model edges within the original social network
that are directed. In this case, the “vertical” edges that connect versions of the same
node across time can also be directed. These connections form a directed c-clique.
We have seen that there are two ways to model these directed edges: using
Chung’s embedding, or using our new directed embedding. With Chung’s technique,
the algorithm has these 6 steps.
Algorithm: Given temporal adjacency matrices W t , α, β .
1. Compute the aggregate network matrix A t as:
If t = 1, A 1 = W 1 ; else, A t = W t + α ∗ A t−1 .
2. Convert each matrix A t to a random walk matrix R t .
3. Connect the snapshot random walk matrices R t together to build a larger random walk matrix M rw with total probability β for random walks to another
snapshot.
4. Let Π be the diagonal matrix whose entries are those of the stationary distribution of M rw . Construct the Laplacian matrix:
L = I −
Π 1/2 M rw Π −1/2 + Π −1/2 M
rw Π 1/2
2
.
5. Compute the eigenvalues λ i and corresponding eigenvectors g i of L.
6. Modify the embedding vectors f i = Π −1/2 g i and embed the graph into k dimensions by using the k vectors f i corresponding to the k smallest non-zero
eigenvalues.
For the composition of the temporal approach with the new directed approach,
the algorithm is much simpler.
Algorithm: Given temporal adjacency matrices W t , α, β .
1. Compute the aggregate network matrix A t as above.
2. Apply the new directed approach (Algorithm 5.2.2) to the aggregate matrix A t .
Chapter 7. Modelling relationships that change over time
network at one time has on its structure at other times, and so is a critical choice for
the global model. We prefer to use a larger value of β in order to align the embedding
of each node across time. As a result, this will also tend to align the larger structures
such as clusters, communities, and cuts.
We have already seen that most realistic social networks have edges that are
directed, so we also want to be able to model edges within the original social network
that are directed. In this case, the “vertical” edges that connect versions of the same
node across time can also be directed. These connections form a directed c-clique.
We have seen that there are two ways to model these directed edges: using
Chung’s embedding, or using our new directed embedding. With Chung’s technique,
the algorithm has these 6 steps.
Algorithm: Given temporal adjacency matrices W t , α, β .
1. Compute the aggregate network matrix A t as:
If t = 1, A 1 = W 1 ; else, A t = W t + α ∗ A t−1 .
2. Convert each matrix A t to a random walk matrix R t .
3. Connect the snapshot random walk matrices R t together to build a larger random walk matrix M rw with total probability β for random walks to another
snapshot.
4. Let Π be the diagonal matrix whose entries are those of the stationary distribution of M rw . Construct the Laplacian matrix:
L = I −
Π 1/2 M rw Π −1/2 + Π −1/2 M
rw Π 1/2
2
.
5. Compute the eigenvalues λ i and corresponding eigenvectors g i of L.
6. Modify the embedding vectors f i = Π −1/2 g i and embed the graph into k dimensions by using the k vectors f i corresponding to the k smallest non-zero
eigenvalues.
For the composition of the temporal approach with the new directed approach,
the algorithm is much simpler.
Algorithm: Given temporal adjacency matrices W t , α, β .
1. Compute the aggregate network matrix A t as above.
2. Apply the new directed approach (Algorithm 5.2.2) to the aggregate matrix A t .