Hidden dependence of spreading vulnerability on topological complexity

Many dynamical phenomena in complex systems concern spreading that plays out on top of networks with changing architecture over time—commonly known as temporal networks. A complex system's proneness to facilitate spreading phenomena, which we abbreviate as its “spreading vulnerability,” is often surmised to be related to the topology of the temporal network featured by the system. Yet, cleanly extracting spreading vulnerability of a complex system directly from the topological information of the temporal network remains a challenge. Here, using data from a diverse set of real-world complex systems, we develop the “entropy of temporal entanglement” as a quantity to measure topological complexities of temporal networks. We show that this parameter-free quantity naturally allows for topological comparisons across vastly different complex systems. Importantly, by simulating three different types of stochastic dynamical processes playing out on top of temporal networks, we demonstrate that the entropy of temporal entanglement serves as a quantitative embodiment of the systems' spreading vulnerability, irrespective of the details of the processes. In being able to do so, i.e., in being able to quantitatively extract a complex system's proneness to facilitate spreading phenomena from topology, this entropic measure opens itself for applications in a wide variety of natural, social, biological, and engineered systems.

Figure 1

Temporal entanglement. (a) An example of a temporal network, in terms of agent-to-agent contacts as interactions among eight numbered agents, at snapshots taken at integer units of sampling time. Snapshots are shown as time layers; the agent-to-agent contacts at integer times are shown as black links within the corresponding time layer. The agents' temporal paths (strings) from one snapshot to the next are shown as gray lines. The changes in the topology of the agent-to-agent contacts from one snapshot to the next make the strings weave through and entangle with each other. (b) Entanglement of the strings at $t=0$, extracted from panel (a); shown explicitly are the temporal paths (strings), labeled by Roman agent indices, and the events in dark blue circles, labeled by Greek indices. Events are the connected components of the agents' contact network at $t=0$. (c) Calculation of the agent-to-agent propagator matrix $P\left(0\right)$ as $P\left(0\right)=Q^{\left(\text{in}\right)}\left(0\right)Q^{\left(\text{out}\right)}\left(0\right)$. The $i\alpha \mathrm{th}$element of the agent-to-event propagator matrix $Q^{\left(\text{in}\right)}\left(0\right)$ is the probability of a random walker to start at agent $i$ prior to $t=0$ and end at event $\alpha$ at $t=0$ in one hop. Similarly, the $\alpha i\mathrm{th}$element of the event-to-agent propagator matrix $Q^{\left(\text{out}\right)}\left(0\right)$ is the probability of a random walker to start at event $\alpha$ at $t=0$ and end at agent $i$ subsequent to $t=0$ in one hop.

Figure 2

Entropy of temporal entanglement for two real-world temporal networks: contacts among high school (Thiers13 data set day 2, left column) and primary school (LyonSchool data set day 1, right column) students. [(a), (b)] $S(t,\mathrm{\Delta }t)$ for four values of $\mathrm{\Delta }t$: 20 s (gray), 5 min (orange), 15 min (red), and 30 min (darker red); for any value of $t$, note that $S(t,\mathrm{\Delta }t)$ is monotonically increasing with $\mathrm{\Delta }t$; and $x$ axes denote the time of day. Vertical dashed lines correspond to 5-min intervals, expanded in panels (c) and (d), chosen to reflect one high-entropy and one low-entropy situation per panel. [(c), (d)] Aggregated contact networks within the 5-min intervals (only connected components with at least 4 students are shown), demonstrating high (resp. low) connectivity in high-$S$ (resp. low-$S$) cases. Metadata reveal that the situations correspond to school breaks and ongoing classes respectively (students belonging to the same classroom are represented by the same node color).

Figure 3

Standardized mixing propensity $s$ and the systems' vulnerability $V$ to spreading phenomena (for precise definitions of both, see Sec. 3b below). (a) Mixing propensity vs the number of events per agent as a system-characterizing property, shown for 12 complex systems: from green (slow rate of increase) to red (fast rate of increase). The systems are noted in panel (b) in the same color coding. (b) Pearson's correlation between $S(t,\mathrm{\Delta }t)$ and $V_i(t,\mathrm{\Delta }t)$, with $i\in (\text{maj},\text{del},\text{dis})$, corresponding to a majority-vote model, a transport delay model, and an epidemiological susceptible-infected (SI) model respectively (see text and Appendix pp1-s2 for details). (c) The full time-series of $S(t,\mathrm{\Delta }t)$ and $V_i(t,\mathrm{\Delta }t)$ on day 2 of the Baboons data set [27]. Displayed on the $x$ axis are the times of day. $\mathrm{\Delta }t=20$ min (i.e., 60 units of sampling time intervals) is used. (d) Same as in panel (c), but using day 2 of the Hospital data set [28].

Figure 4

Three agents A, B, and C interacting in sequence. (Left) A propagation process that is in reality allowed. (Right) A propagation process that is in reality impossible, but is allowed when the agent interactions information in the temporal dimension is collapsed.

Figure 5

(a) Event $\alpha$ taking place at time $t$ for one of the connected components with $n$ agents, labeled by Roman indices. (b) As a working example, we consider the same event structure for eight agents at $t=0$ as in Fig. 1 in the main text of the paper.

Figure 6

The $8\times 8P$ matrix constructed as $P=Q^{\text{(in)}}{Q}^{\text{(out)}}$ from Fig. 5.

Figure 7

Constructing the $Q_{\text{c}}^{\text{(in)}}$ and the $Q_{\text{c}}^{\text{(out)}}$ for the working example, containing the agents' actual contact network at $t=0$ in Fig. 1 of the main text.

Figure 8

The $8\times 8P^{\text{(c)}}$ matrix constructed as $P^{\text{(c)}}=Q_{\text{c}}^{\text{(in)}}{Q}_{\text{c}}^{\text{(out)}}$ from Fig. 7.

Figure 9

Evolution of entanglement entropy $S$, and the state variable $V_{\text{dis}}$, for three values of $\beta$, using $\mathrm{\Delta }t=15$ min, for day 2 in the Baboons data set. Pearson's correlation values ($r$) are also noted in the figure (which are the values only for this particular day). Note that Fig. 3 of the main text uses 5 days of the Baboons data set, leading to a slightly smaller Pearson's correlation value for $\beta =0.8$, namely 0.93.