Random walks on temporal networks

Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various time scales, and their dynamics has profound consequences for any processes in which they are involved. The first empirical analysis of the temporal patterns characterizing dynamic networks are still recent, so that many questions remain open. Here, we study how random walks, as a paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals, and characterize the fundamental quantities that impact any general process taking place upon them. Furthermore, we introduce different randomizing strategies that allow us to single out the role of the different properties of the empirical networks. We show that the random walk exploration is slower on temporal networks than it is on the aggregate projected network, even when the time is properly rescaled. In particular, we point out that a fundamental role is played by the temporal correlations between consecutive contacts present in the data. Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.

Figure 1

Distributions of $P\left(\Delta t\right)$ (duration of contacts), $P\left(\omega \right)$ (total contact time between pairs of agents), $P_i\left(\tau \right)$ (gap times of a single individual $i$), and $P\left(\tau \right)$ (global gap times). In the case of $P_i\left(\tau \right)$, we only plot the gap times distribution of the agent which engages in the largest number of conversation, but the other agents exhibit a similar behavior. All distributions are heavy tailed, indicating the bursty nature of face-to-face interactions, for the four empirical contact sequences considered.

Figure 2

(Top) Distribution of the temporal duration of the shortest time-respecting paths, normalized by its maximum value $T$. (Inset) Probability distribution $P\left(l_s\right)$ of the shortest path length measured over time-respecting paths, and normalized with its mean value $\langle l_s\rangle$. Note that the different data sets collapse. (Bottom) Probability distribution of the duration of the shortest $P\left(\Delta t_s\right)$ and fastest $P\left(\Delta t_f\right)$ time-respecting paths, for the eswc data set. (Inset) Probability distribution of the shortest $P\left(l_s\right)$ and fastest $P\left(l_f\right)$ path length for the same data set.

Figure 3

(Top) Probability distribution $P_i\left(\tau \right)$ of a single individual and $P\left(\Delta t\right)$ (inset) for the extended contact sequences SRep, SRan, and SStat, for the 25c3 data set. The weight distribution $P\left(w\right)$ of the original contact sequence is preserved for every extension. (Bottom) Probability distribution of gap times $P\left(\tau \right)$ for all the agents in the SRep, SRan, and SStat extensions of the 25c3 data set.

Figure 4

Normalized coverage $C\left(t\right)/N$ as a function of the rescaled time $\overline{p}t/N$, for the SRep, SRan, and SStat extension of empirical data. The numerical evaluation of Eq. (13) is shown as a dashed line, and each panel in the figure corresponds to one of the empirical data sets considered. The exploration of the empirical repeated data sets (SRep) is slower than the other cases. Moreover, the SRan is in agreement with the theoretical prediction, and the SStat case shows a close (but systematically slower) behavior. This indicates that the main slowing down factor in the SRep sequence is represented by the irregular distribution of the interactions in time, whose contribution is eliminated in the randomized sequences.

Figure 5

Number of new conversations $n\left(t\right)$ started per unit time in the SRep (black solid dots), SRan (red open squares), and SStat (green diamonds) extensions of the school data set.

Figure 6

Asymptotic residual coverage $1-C\left(t\right)/N$ as a function of $\overline{p}t/N$ for the SRep (top) and SRan (bottom) extended sequences, for different data sets.

Figure 7

Rescaled mean first passage time ${\tau }_i$, shown against the strength $s_i$, normalized with the total strength $N\langle s\rangle$, for the SRep, SRan, and SStat extensions of empirical data. The dashed line represents the prediction of Eq. (12). Each panel in the figure corresponds to one of the empirical data sets considered.

Figure 8

Mean first-passage time at node $i$, in units of rescaled time $\overline{p}t$, vs the strength $s_i$, normalized with the total strength $N\langle s\rangle$, for RW processes on the SRep data set extension. All data collapse close to the continuous line whose slope, $\alpha \simeq 0.75$, differs from the theoretical one, $\alpha =1.0$, shown as a dashed line.

Figure 9

Normalized coverage $C\left(t\right)/N$ as function of the rescaled time $\overline{p}t/N$ for the different data sets. The inset shows the probability distribution $P\left(\Delta t_{\mathrm{new}}\right)$ of the time lag $\Delta t_{\mathrm{new}}$ between the discovery of two new vertices. Only the discovery of the first $5\%$ of the network is considered, to avoid finite size effects [46].

Figure 10

Coverage $C\left(t\right)/N$ as a function of the number of new conversation realized up to time $t$, normalized by the mean number of new conversation per unit of time $\overline{n}$ for different data sets.

Figure 11

Rank plot of the coverage $C_i$ obtained starting from node $i$ in the contact sequence of duration $T$, averaged over ${10}^3$ runs. In the inset, we show a rank plot of the coverage $C_i\left(\Delta T\right)$ up to a fixed time $\Delta T={10}^3$.

Figure 12

Correlation between the probability of node $i$ to be reached by the RW, $P_r\left(i\right)$, and the rescaled strength $\overline{p}T{s}_i/N\langle s\rangle$ for different datasets. The curves obtained by different dataset collapse, but they do not follow the mean-field behavior predicted by of Equation (17) (dashed line). The inset shows the same data on a linear scale, to emphasize the deviation from mean-field.

Figure 13

Correlation between the probability of node $i$ to be reached by a RW of length $T/2$, $P_r\left(i\right)$, and the rescaled strength $\overline{p}T{s}_i/N\langle s\rangle$ for different data sets, where $s_i$ is computed on the whole data set of length $T$. The inset shows the same data on a linear scale.