Representing temporal networks by a sequence of discrete snapshots naturally leads to a matrix representation
\((A_t,\ t\in [ 1,T] )\), where
\(A_t=(a_{t,i,j},\ i,j\in V)\) is the adjacency matrix of the network
\(\mathcal{G}_t\). However, it is also possible to embed the snapshots
\(\mathcal{G}_t\) inside a single
concatenated network
\(\mathcal{G}^{\rm{conc}}\), which has vertex-set
\([ 1,T+1] \times V\). In this representation, each edge
\((u,v)\in E_t\) is seen as a directed edge from vertex
\((t,u)\) to
\((t+1,v)\). This representation is inspired by the application to cattle trade movements, in which an edge (
u,
v) at time
\(t\) represents the movement of an animal between two holdings, such that that animal is present in holding
\(u\) at time
\(t\), then in holding
\(v\) at time
\(t+1\). Of course, it would also be possible to use edges in
\(E_t\) to represent movements from time-slice
\(t-1\) to time-slice
\(t\). Using our convention however, in matrix form, the concatenated network
\(\mathcal{G}^{\rm{conc}}\) has an adjacency matrix defined by blocks:
$$\begin{aligned} A^{\rm{conc}} = \begin{pmatrix} 0 &{}\quad A_1 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \\ &{}\quad 0 &{}\quad A_2 &{}\quad \cdots &{}\quad 0 \\ &{}\quad &{}\quad 0 &{}\quad \ddots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad A_{T} \end{pmatrix}. \end{aligned}$$
(3)
Note that this matrix is of dimension
\(TN\times (T+1)N\). We will also sometimes consider the
wrapped network
\(\mathcal{G}^\text {wrap}\). This network has vertex-set
\([ 1,T ] \times V\) and edges from
\(E_T\) go from layer
\(T\) to layer 1. Its matrix representation is then
$$\begin{aligned} A^{\rm{wrap}} = \begin{pmatrix} 0 &{}\quad A_1 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \\ &{}\quad 0 &{}\quad A_2 &{}\quad \cdots &{}\quad 0 \\ &{}\quad &{}\quad 0 &{}\quad \ddots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad A_{T-1} \\ A_T &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \end{pmatrix}. \end{aligned}$$
(4)
Optionally, each of these networks can be augmented to include self-loops linking each vertex
\((t,i)\) to its representation
\((t+1,i)\) in the next time-slice (using the convention that
\(T+1=1\) in the case of the wrapped network). This will be useful when considering lazy random walks, which can stay in a given vertex for some amount of time before moving using an outgoing edge.
TempoRank centrality. There are at least two extensions of PageRank centrality to the temporal networks. Here, we will focus on TempoRank centrality (Rocha and Masuda
2014), but we note that a different approach was considered in Rozenshtein and Gionis (
2016), also taking advantage of the close relationship between PageRank scores and the stationary distributions of random walks on the network. The temporal PageRank approach of Rozenshtein and Gionis (
2016) defines a time-dependent score
\(\mathbf {r}(u,t)\) for each node
\(u\) and each time-stamp
\(t\) recorded in the temporal network by considering the number of time-respecting random walks reaching
\(u\) before time
\(t\). Nodes that can be reached by many time-respecting walks will then have a high temporal PageRank score at time
\(t\). This approach is particularly useful in the case of streaming graphs, and the authors describe an efficient algorithm to update the temporal PageRank scores as more interactions are recorded, accurately reflecting rising and falling influence of a given node as time passes. However, such an approach is not well-suited to our context of outbreak mitigation on cattle trade networks, due to the periodic nature of such networks. Indeed, there is a strong annual and seasonal periodicity in the activity of certain holdings. The corresponding nodes will then have low temporal PageRank scores after long periods of inactivity, while being of critical importance in epidemic transmission during their activity period.
By contrast, the TempoRank score introduced in Rocha and Masuda (
2014) summarizes all temporal information contained in a set of time-stamped edges into a single score by averaging over all observation times. TempoRank centrality considers the wrapped network
\(\mathcal{G}^\text {wrap}\) associated with a given temporal network
\(\mathcal{G}\). With the application to cattle trade networks in mind, we will assume that
\(\mathcal{G}\), hence also
\(\mathcal{G}^\text {wrap}\) are directed. Let
\(q\ge 0\) be a
laziness parameter and
\(d\ge 0\) be a
teleportation parameter. The transition matrix for the lazy random walk with teleportation is then defined by:
$$\begin{aligned} (B_t)_{i,j} = {\left\{ \begin{array}{ll} q+(1-q)d/N + (1-q)(1-d) ,\ &{} \text {if}\, {\rm{odeg}}_t(i)=0,\ i=j\\ (1-q)d/N,\ &{} \text {if}\, {\rm{odeg}}_t(i)=0,\ i\ne j \\ q+(1-q)d/N,\ &{} \text {if}\, {\rm{odeg}}_t(i)>0,\ i=j,\\ (1-q)[d/N + a_{t,i,j}(1-d)/{\rm{odeg}}_t(i)],\ &{} \text {if}\, {\rm{odeg}}_t(i)>0,\ i\ne j, \end{array}\right. } \end{aligned}$$
(5)
with the out-degree
\({\rm{odeg}}_t(i)\) defined by:
$$\begin{aligned} {\rm{odeg}}_t(i) = \sum _{j\ne i} a_{t,i,j}. \end{aligned}$$
(6)
In other words, random walkers stay in place with probability
\(q\) (note that the authors of Rocha and Masuda (
2014) used a degree-dependent probability
\(q^{\text {deg}_t(i)}\) of staying in place). If they decide to move, they teleport to a uniformly chosen vertex with probability
\(d\), or move along a uniformly chosen outgoing edge with probability
\(1-d\). Note that if the current vertex is isolated at time
\(t\) (
\({\rm{odeg}}_i (t)=0\)), there is no such outgoing edge, and they stay in place (this occurs with probability
\((1-q)(1-d)\)). Using the wrapped network representation of (
4), we then get the following transition matrix on
\(\mathcal{G}^ \text {wrap}\):
$$\begin{aligned} B^\text {wrap} = \begin{pmatrix} 0 &{}\quad B_1 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \\ &{}\quad 0 &{}\quad B_2 &{}\quad \cdots &{}\quad 0 \\ &{}\quad &{}\quad 0 &{}\quad \ddots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad B_{T-1} \\ B_T &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \end{pmatrix}. \end{aligned}$$
(7)
By definition,
\(B^{{\rm{wrap}}}\) is a stochastic matrix, and, by the Perron-Frobenius theorem, admits a (unique up to a multiplicative constant) left 1-eigenvector
\(\Pi\) with nonnegative elements. Writing left 1-eigenvectors under the form
\(\Pi =(\pi _1\ \dots \ \pi _T)\in {\mathbb{R}}^{TN}\) with
\(\pi _i\in {\mathbb{R}}^N\), we see that they need to satisfy the equations:
$$\begin{aligned} \pi _T B_T= \pi _1,\ \pi _1 B_1= \pi _2,\dots , \pi _{T-1} B_{T-1}= \pi _T, \end{aligned}$$
(8)
which is equivalent to
$$\begin{aligned} \begin{aligned} \pi _TB_T B_1\cdots B_{T-1}&= \pi _T,\\ \pi _1 B_1 B_2\cdots B_T&= \pi _1, \\&\dots \\ \pi _{T-1} B_{T_1} B_T\cdots B_{T-2}&= \pi _{T-1}. \end{aligned} \end{aligned}$$
(9)
In other words, the
\(\pi _t\) are the stationary distributions of the random walks
\((X_{mT+t})\) as
\(m\rightarrow \infty\), where
\(X\) has one-step transition matrix given by (
5). Averaging over time, we define:
$$\begin{aligned} \mathsf {TR}(x) = \frac{1}{T} \sum _{t=1}^T \pi _t(x) \end{aligned}$$
(10)
We will also consider the following version of TempoRank that takes into account the existence of outgoing edges in a given time-slice. We will call it
out-TempoRank centrality. It gives no weight to vertices with no outgoing edges, by contrast with regular TempoRank centrality.
$$\begin{aligned} \mathsf {oTR}(x) = \frac{1}{T}\sum _{t=1}^T \pi _t(x)\mathbf {1}_{{\rm{odeg}}_t(x)>0} \end{aligned}$$
(11)