Reconstructing irreducible links in temporal networks: which tool to choose depends on the network size

2.1.1. Interval partition

In our previous work [19], we demonstrated that dividing the overall observation window into successive intervals improves the accuracy of the reconstruction. Therein, we compared a naïve supervised partitioning method, which divides the time series at random, with an unsupervised one (the Bayesian Block (BB) method [31]). We found that the latter should be preferred for its performance over artificial network benchmarks, its freedom from the need of prior information about the interval partition, and its implementability on relatively short time series.

The BB method [31] employs maximum likelihood and marginal posterior functions to distinguish statistically significant features from random observational errors. It starts with considering the first time step t  =  1, and then it adds and analyzes the subsequent time instants $t = 2, \dots, T$, approximating the time series in piece-wise constant segments, where a homogeneous number of links is observed. The algorithm coherently builds on iterations from past time steps to efficiently compute future interval partition.

In our application, the BB method analyzes the total number of temporal links created in the entire network at time t

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \Omega^{{\rm ts}} (t) = \sum_{i,j = 1; i \leqslant j}^{N} A_{ij}^{{\rm ts}}(t), \label{W_t_tot} \nonumber \end{align} \tag{ 1 }$$

and returns the interval partition, which divides the overall time window T into I disjoint intervals indexed by $\Delta = 1, \ldots, I$, containing approximately a uniform total number of connections [31]. The superscript '${\rm ts}$' indicates that these variables are estimated from the time series of the individual links. From the knowledge of the interval partition, we determine the length, $\tau(\Delta)$, of the generic $\Delta$th interval under the closure relation $\sum_{\Delta=1}^{I} \tau(\Delta) =T$.

2.1.2. Parameter estimation

In order to detect the backbone network, we should determine the extent by which each pair of nodes i and j  will interact by simple chance. The EADM is based on a heterogeneously distributed parameter, the activity, which represents the propensity of generating links over time [21]. The probability that node i interacts with node j  at time t is the product of the two activities [5, 19],

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle p_{ij}(t) = a_i(t) a_j(t). \label{probability_random} \nonumber \end{align} \tag{ 2 }$$

Individual activities are estimated according to the weighted configuration model [19, 32].

Since the I intervals found by the BB method are disjoint, we can analyze each of them separately. For instance, we consider the generic $\Delta$th time interval that starts at $t = t_{{\rm in}}(\Delta)$ and ends at $t = t_{{\rm in}}(\Delta)+\tau(\Delta) -1$. The activity of node i at time $t \in \left[t_{{\rm in}}(\Delta), t_{{\rm in}}(\Delta)+\tau(\Delta) -1 \right]$ is computed through the following formula:

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle a_i \left( t \right) = \frac{s_{i}^{\mathrm{ts}} \left(\Delta \right)}{\sqrt{2 W^{\mathrm{ts}}(\Delta)\tau(\Delta)}}, \label{Estimation_activity_EADM} \nonumber \end{align} \tag{ 3 }$$

where $s_{i}^{\mathrm{ts}} \left(\Delta \right)$ and $W^{\mathrm{ts}}(\Delta) \gg 1$ are the node strength and the total number of temporal links generated in the network in the $\Delta$th interval, respectively. Specifically, $s_{i}^{\mathrm{ts}} \left(\Delta \right)$ and $W^{\mathrm{ts}}(\Delta)$ are computed from $A^{{\rm ts}}(t)$ through

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle s_{i}^{\mathrm{ts}} \left(\Delta \right) &= \sum_{j = 1}^{N} \sum_{t = t_{{\rm in}}(\Delta)}^{t_{{\rm in}}(\Delta)+\tau(\Delta)-1} A_{ij}^{\mathrm{ts}}(t) \ {\rm and}\nonumber \\ W^{\mathrm{ts}}(\Delta)&=\frac{1}{2} \sum_{i = 1}^{N} s_{i}^{\mathrm{ts}}(\Delta). \end{align} \tag{ 4 }$$

Once the activities are estimated according to equation (3), the probability in equation (2) can be computed as

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle p_{ij}(t) = \frac{s_{i}^{\mathrm{ts}} \left(\Delta \right)s_{j}^{\mathrm{ts}} \left(\Delta \right)}{2 W^{\mathrm{ts}}(\Delta)\tau(\Delta)}. \label{probability_random_estimated} \nonumber \end{align} \tag{ 5 }$$

2.1.3. Statistical filter

The typical objective of a statistical filter is to test whether a specific link ij can be explained by the null hypothesis. If it were explained by the null model, it should be filtered out, otherwise it should be included in the backbone network. The same statistical test has to be applied to each of the N_E links that appear at least once over the entire observation window.

The EADM requires to compare the total number of connections between node i and node j , $\overline{w}_{i j}^{\mathrm{ts}}$, observed in the entire observation window with its expected quantity, ${\rm E} \left[\overline{w}_{ij}\right]$. The observed number of connections can be computed from $A_{ij}^{\mathrm{ts}}(t)$ as

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \overline{w}_{i j}^{\mathrm{ts}} = \sum_{\Delta=1}^I w_{i j}^{\mathrm{ts}} \left(\Delta \right) = \sum_{\Delta=1}^I \sum_{t = t_{{\rm in}}(\Delta)}^{t_{{\rm in}}(\Delta)+\tau(\Delta)-1} A_{ij}^{\mathrm{ts}}(t). \label{weigth_links} \nonumber \end{align} \tag{ 6 }$$

The expected number of connections between nodes i and j  in the time window T is calculated as the sum of the binomial random variables given in equation (2) [19]

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm E} \left[\overline{w}_{ij}\right] = \sum_{t=1}^{T} p_{ij}(t). \label{Expected_links} \nonumber \end{align} \tag{ 7 }$$

The sum of non-identical binomial random variables in equation (7) is a Poisson binomial distribution, which is usually approximated by the Poisson distribution [33–35], due to a lack of closed-form expression.

The confidence that the observed weight, $\overline{w}_{i j}^{\mathrm{ts}}$, could be explained by its corresponding expected weight, ${\rm E} \left[\overline{w}_{ij}\right]$ in equation (7), is computed according to the cumulative function of the Poisson distribution

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \alpha_{ij} \equiv 1 - \sum_{x = 0}^{\overline{w}_{i j}^{\mathrm{ts}}-1} P \left(x; {\rm E}\left[ \overline{w}_{ij} \right] \right), \label{p_value_EADM_ETFM} \nonumber \end{align} \tag{ 8 }$$

where $P \left(x; {\rm E}\left[ \overline{w}_{ij} \right] \right)$ indicates the Poisson distribution with random variable x and expected value ${\rm E}\left[ \overline{w}_{ij} \right]$. Equation (8) represents the p-value, $\alpha_{ij}$, that the observed link ij can be explained by the null hypothesis of being extracted from a Poisson distribution. If the p-value is below a pre-defined threshold, then the link is deemed as significant and retained in the backbone network.

From equation (8), a total of N_E p-values are computed, one for each link created at least once in the overall network evolution. The interval partition begets better estimation of the expected number of links between nodes i and j , in equation (7), thereby improving on the estimation of the p-values through equation (8).

As detailed in table 2, the interval partition is carried using the BB method [31], thereby following section 2.1.1. Similarly, the statistical filter is equivalent to the one of the EADM, explained in section 2.1.3. Here, we detail the main difference between the EADM and ETFM, which pertains to the activity estimation.

Similar to the EADM, the probability that node i interacts with node j  at time t is the product of the two individual activities, as given in equation (2). However, the ETFM estimates the activities in a maximum likelihood sense, based on the approach introduced in [5]. Specifically, given that the intervals returned from the BB method are disjoint, we can apply the maximum likelihood presented in [5] to each of the I intervals. The input parameters of the maximum likelihood are computed according to the EADM in equation (3).

For instance, in the $\Delta$th interval, starting at $t = t_{{\rm in}}(\Delta)$ and ending at $t = t_{{\rm in}}(\Delta)+\tau(\Delta)-1$, individual activities are assumed to be constant and estimated according to equation (3). Some nodes in the network, however, do not generate nor receive connections. These nodes have an activity equal to zero and they should be discarded in the maximum likelihood computation. Hence, from the set of all possible activities at time t, ${\boldsymbol a}(t) = \left(a_1(t), \dots, a_{N}(t) \right)$, the maximum likelihood estimation is applied only to those entries with a_i(t)  >  0. Assuming that there are $n(\Delta) \leqslant N$ of these nodes, we indicate the reduced set of optimal activities as ${\boldsymbol a^*}(t) = \left(a_1^*(t), \dots, a_{n(\Delta)}^*(t) \right)$.

The estimation of the optimal activity values is carried similar to [5], whereby

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \sum_{j = 1; j\neq i}^{n(\Delta)} & \frac{w_{ij}^{{\rm ts}}\left(\Delta \right) - \tau\left(\Delta \right) a_i^*\left(t \right)a_j^*\left(t \right)}{1 - a_i^*\left(t \right)a_j^*\left(t \right)} = 0, \nonumber \\ a_i^*\left(t \right) &\in \left(0, 1 \right), \quad i = 1, \dots, n\left(\Delta \right). \label{maxlikelihood_ETFM} \nonumber \end{align} \tag{ 9 }$$

All the individual activities are constant (between zero and one) within the $\Delta$th interval, and $w_{ij}^{{\rm ts}} \left(\Delta \right)$ is given by equation (6). Once the optimal values for the activities are estimated from equation (9), they can be used to estimate the probability in equation (2).

According to table 2 and similar to the EADM and ETFM, the interval partition is carried out through the BB method implemented on the time series of the individual links [31]. The parameter estimation and the statistical filter are different from the EADM and they are explained in the following.

2.3.1. Parameter estimation

In the TDF, parameters are estimated directly from the time series, without relying on any expected quantity like the activities for the EADM and ETFM. For instance, in the $\Delta$th interval that starts at $t = t_{{\rm in}}(\Delta)$ and ends at $t = t_{{\rm in}}(\Delta)+\tau(\Delta) -1$, a number of connections between node i and node j  are observed, $w_{ij}^{{\rm ts}}\left(\Delta \right)$, in equation (6). Similar to the disparity filter [6], two normalized quantities are computed by dividing $w_{ij}^{{\rm ts}}\left(\Delta \right)$ either by the strength of node i, $s_{i}^{{\rm ts}}\left(\Delta \right)$, or node j , $s_{j}^{{\rm ts}}\left(\Delta \right)$, in equation (4), respectively, such that

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle r_{ij}^{{\rm ts}}(t) = \frac{w_{ij}^{{\rm ts}}\left(\Delta \right)}{s_{i}^{{\rm ts}}\left(\Delta \right)}. \label{probability_EDP} \nonumber \end{align} \tag{ 10 }$$

These quantities must satisfy the closure condition $\sum_{j} r_{ij}^{{\rm ts}} (t) = 1$ $\forall t \in [t_{{\rm in}}(\Delta), t_{{\rm in}}(\Delta) + \tau(\Delta) -1 ]$. Note that while $w_{ij}^{{\rm ts}}\left(\Delta \right) = w_{ji}^{{\rm ts}}\left(\Delta \right)$, in general $r_{ij}^{{\rm ts}}(t) \neq r_{ji}^{{\rm ts}}(t)$ since the strengths of nodes i and j  can be different.

Over the entire time window T, the normalized weight, $\overline{r}_{ij}^{{\rm ts}}$, is computed using a weighted time average starting from the results of equation (10), yielding

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \overline{r}_{ij}^{{\rm ts}} = \frac{1}{T} \sum_{\Delta = 1}^{I} \frac{w_{ij}^{{\rm ts}}\left(\Delta \right) \tau \left(\Delta \right)}{s_{i}^{{\rm ts}}\left(\Delta \right)}. \label{probability_EDP_2} \nonumber \end{align} \tag{ 11 }$$

Here, the longer is the interval, the greater is its contribution to the overall average. If only one interval is returned by applying the BB method to the time series, equation (11) reduces to the estimation of the classical disparity filter [6].

2.3.2. Statistical filter

The TDF statistical filter takes two quantities as input: the normalized weights computed according to equation (11) and the observed degree of either node i, $\overline{k}_{i}^{{\rm ts}}$, or node j , $\overline{k}_{j}^{{\rm ts}}$, over the entire network evolution. The node degree is computed from equation (6) as

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \overline{k}_{i}^{{\rm ts}} = \sum_{j=1}^{N} \mathcal{H} \left[\overline{w}_{i j}^{\mathrm{ts}} - 1 \right], \nonumber \end{align} \tag{ 12 }$$

where $\mathcal{H}$ is the Heaviside function that takes a value equal to one when $\overline{w}_{i j}^{\mathrm{ts}} \geqslant 1$, and zero otherwise.

The TDF null hypothesis is that a node connects uniformly at random with all its neighbours. For node i with degree $\overline{k}_{i}^{{\rm ts}}$, the TDF considers as a baseline that node i exchanges an equal number of connections with all its neighbors, which results in all normalized weights from equation (11) being equal to $1/\overline{k}_{i}^{{\rm ts}}$. Irreducible links included in the backbone network have a normalized weight $\overline{r}_{i}^{{\rm ts}}$ greater than the expectation from the null hypothesis.

The advantage of the TDF with respect to the original disparity filter [6] is that it accounts for time-variations in node properties, through equation (10). The disparity filter in its original incarnation can be only applied to weighted networks. A p-value has to be associated with any link in the network. We use the same formula proposed for the disparity filter [6], namely,

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \gamma_{ij} \equiv 1 - \left(\overline{k}_i^{{\rm ts}} - 1 \right) \int_{0}^{\overline{r}_{ij}^{{\rm ts}}} \left(1 - x \right)^{\overline{k}_{i}^{{\rm ts}} - 2} {\rm d}x, \label{disparity_filter} \nonumber \end{align} \tag{ 13 }$$

where $\gamma_{ij}$ is the p-value. In general, equation (13) may yield a different result if it is specialized to node i or node j , even for undirected networks. Therefore, it is necessary to consider an additional p-value for the undirected link ij, by focusing on node j  rather than i, such that we compute $\gamma_{ji}$ in lieu of $\gamma _{ij}$. If at least one of the two p-values $\gamma_{ij}$ or $\gamma_{ji}$ is lower than a pre-defined threshold, the undirected link ij is included in the backbone network. If only one interval is returned by applying the BB method to the time series, the TDF becomes equivalent to the disparity filter [6].

Similar to equations (7) and (8), the temporal partition is used to estimate the network weights and a p-value is associated with each link of the network that appeared at least once during the overall network evolution.

Graphical representations of the ETFM and TDF are given in figure 1.

Zoom In Zoom Out Reset image size

In all of the three approaches under consideration, a statistical test is carried out for all the $N_{{\rm E}}$ links observed at least once in the evolving network. The EADM and ETFM use equation (8), while the TDF employs equation (13). Since multiple hypotheses are tested, a multiple hypothesis test correction is required [36]. Here, we choose the Bonferroni correction [37]. It computes the multivariate threshold equal to $\beta^{\prime} = \beta/N_E$, where $\beta$ is the univariate threshold, usually set equal to 0.01. This correction assures that no false positives will be included in the backbone network with probability $1-\beta$.

An alternative to the Bonferroni correction might be the false discovery rate (FDR) [38], which is a less restrictive option because it ensures that the fraction of false positive is less than $\beta$.

Here, we describe in detail our approach to the analysis of the freely available Primary School dataset [30], a similar analysis is carried out for the Workplace dataset [30] in appendix C. Our approach is inspired by previous efforts [5, 19]. In the original dataset, person to person interactions are recorded every 20 seconds; however, in reality, interactions might last longer than this pre-defined temporal resolution. In order to remove redundancies in the collected data and confounds associated with a particular resolution [5, 19], we study two temporal resolutions of 5 and 15 min, and remove multiple connections at the same temporal resolution. We remove the time interval between the last connection of a day and the first one of the following day.

In order to explore the role of network size, we study different temporal networks from the Primary School dataset and detect a backbone network for each of them. Specifically, we focus on the temporal interactions occurring in each classroom (10 in total), the body of the teachers, and the entire school. A data summary is provided in table 3.

We present a generative mechanism for temporal networks with known backbone network and arbitrary distribution of reducible and irreducible links. The mechanism extends the one introduced in [19], where temporal networks with heterogeneous activity distribution and homogeneous backbone are generated.

Artificial temporal networks are generated from the superposition of reducible and irreducible links. Reducible links are created according to equation (2) and evolve over the whole observation window composed by T time steps, partitioned into I intervals. Nodes have interval-dependent (piece-wise constant) activities a_i(t), drawn from the activity distribution $F(a)$. Between two consecutive intervals, $t_{1}\in [t_{{\rm in}}(\Delta-1), t_{{\rm in}}(\Delta-1)+\tau(\Delta-1)-1]$ and $t_{2} \in [t_{{\rm in}}(\Delta), t_{{\rm in}}(\Delta)+\tau(\Delta)-1]$, the activity values vary according to

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle a_i (t_2) = a_i (t_1)\,p + y(1-p), \label{autocorrelation} \nonumber \end{align} \tag{ 14 }$$

where p  is an autocorrelation parameter and y  a random number extracted from $F(a)$. Among all the links observed at least once, a fraction $\newcommand{\e}{{\rm e}} \epsilon$ of them is arbitrarily assigned to the backbone network. The preponderance of a link between nodes i and j  is $\lambda_{ij}$, such that if $\lambda_{ij}=0$, the link appears according to the product of activity values, as in equation (2), while increasing $\lambda_{ij}$ makes the backbone network easier to discover. The values of $\lambda_{ij}$ are extracted from the distribution $G(\lambda)$. More details about the generative algorithm can be found in appendix A1.

In the main text, we consider the case of a heterogeneous activity distribution, $F(a) \sim a^{-2.1}$ and $a \in \left[a_{{\rm min}}, 1 \right]$, and homogeneous backbone network, $G(\lambda) \sim \delta \left( \lambda - \hat{\lambda} \right)$, that is, $\lambda_{ij} = \hat{\lambda}$ for all link in the backbone network, where $\delta \left(\cdot \right)$ is the Dirac delta distribution. In appendix A, we examine three more cases: (i) heterogeneous activity distribution and heterogeneous backbone, (ii) homogeneous activity distribution and homogeneous backbone, and (iii) homogeneous activity distribution and heterogeneous backbone.

All approaches determine the interval partition using the BB method, which requires a computational time of $\mathcal{O} (I_{{\rm max}}^2)$. Here, $I_{{\rm max}}$ represents the number of times in which the total number of temporal links in the entire network at time t, as computed in equation (1), is different from what observed at t  +  1, $\Omega(t) \neq \Omega(t+1)$ for $t = 1, \dots, T-1$, and $\mathcal{O}$ is the Landau symbol. Similarly, the statistical filters in equations (8) and (13), share a similar computational cost that scales as $\mathcal{O}(N_E)$, where N_E is the number of links observed at least once in the temporal evolution.

The estimation of model parameters is different across the EADM, ETFM, and TDF. In the EADM, activities are estimated through equation (3), which scales linearly with the number of intervals, I, and the number of links created in each interval. The complexity of this approach is $\mathcal{O}\left( c N I\right)$, where $c \ll N$ for sparse networks and $c \sim N$ for dense networks. A similar reasoning applies for the estimation of the TDF's parameters in equations (10) and (11), yielding a complexity of $\mathcal{O}\left( c N I\right)$.

In the ETFM, activity values are optimized in a maximum likelihood sense, which requires to recursively solve equation (9). Hence, the ETFM computational cost depends on three factors: the number I of intervals, the number of nodes in the $\Delta$th interval, $n (\Delta)$, and the number m of recursions. The computational cost grows linearly with the number of intervals I, since it has to be applied independently to each interval, and with m, which is the number of iterations for the maximum likelihood to converge. On the other hand, it is quadratic in $n\left(\Delta \right)$, because of equation (9). Overall, the ETFM complexity hits $\mathcal{O}\left( m I N^2 \right)$ in the worst case scenario, while in the best case scenario, when only one interval is present, it is $\mathcal{O}\left( m N^2 \right)$, like in the temporal fitness model [5].

By comparing the EADM and TDF complexities, $\mathcal{O}\left( c N I\right)$, with the ETFM complexity, $\mathcal{O}\left( m N^2 I \right)$, we observe that the bottleneck is the size of the network. For large networks, the EADM and TDF are much faster procedures than the ETFM.

Our study involves the mathematical analysis of the model accuracy, which is verified through numerical simulations using the artificial networks described in section 3.2 and appendix A.1. In the main text, we focus on the case of heterogeneous activity distribution and homogeneous backbone network; in appendix A.2 we explore the case of heterogeneous backbone and in appendix A.3 the case of homogeneous activities.

The TDF statistical filter in equation (13) uses quantities that are computed directly from the time series, without relying on any expected value, which is otherwise needed for the EADM and ETFM. Therefore, the following analysis can be carried out only for the EADM and ETFM, since it involves comparison between expected and observed quantities. We focus on both microscopic and macroscopic quantities, including the observed node strength, $s_{i}^{{\rm ts}}$, compared to its expected value, E$\left[s_{i}^{{\rm ts}}\right]$; and the observed average strength, $\newcommand{\av}[1]{\langle #1 \rangle} \av{s^{{\rm ts}}}$, compared with its expected value, E$\newcommand{\av}[1]{\langle #1 \rangle} \left[\av{s^{{\rm ts}}}\right]$.

3.4.1. Mathematical analysis

The analysis of the ETFM is trivial, since, by definition, the maximum likelihood in equation (9) returns optimal activity values, $a_i^{*}(t)$ for $i = 1, \dots, N$, for an optimal representation of observed values. Hence, we expect that the ETFM provides the most accurate estimation of the backbone network. We focus on both global and local quantities, which we report here, and successively compare to the results of the EADM. In the ETFM, the expected individual strength of node i is computed by summing over the entire time-window and over all possible connections that node i may have

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm E} \left[\overline{s}_i\right] = \sum_{j = 1; j \neq i}^{N}\sum_{t=1}^{T} a_i^*\left(t \right) a_j^*\left(t \right). \label{Expected_individual_strength_link_ETFM} \nonumber \end{align} \tag{ 15 }$$

In equation (15), we use the product of activities to be consistent with the probability that two nodes randomly connect, given in equation (2). The expected average strength is the simple average of equation (15) among all possible nodes in the network and reads

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\av}[1]{\langle #1 \rangle} \displaystyle {\rm E} \left[\av{\overline{s}}\right] = \frac{1}{N} \sum_{i, j = 1}^{N}\sum_{t=1}^{T} a_i^*\left(t \right) a_j^*\left(t \right). \label{Expected_average_strength_links_total_ETFM} \nonumber \end{align} \tag{ 16 }$$

The analysis of the EADM is more challenging. The node strength is a key quantity to compute the individual activities, in equation (3), to estimate the link weights, in equation (7), and to determine whether links are explained by our null model or they belong to the backbone network, in equation (8). From equation (7), we compute the expected individual strength for node i in the whole observation window by summing over all the possible connections that node i can make, excluding self-loops that are not allowed in the model. This reads

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm E}\left[\overline{s}_i\right] = \sum_{j=1; j\neq i}^{N} \sum_{\Delta=1}^{I} \frac{s_{i}^{\mathrm{ts}} \left(\Delta \right) s_{j}^{\mathrm{ts}} \left(\Delta \right)}{2 W^{\mathrm{ts}} (\Delta)}. \nonumber \end{align} \tag{ 17 }$$

By changing the order of the two summands and using the definition of the total number of links in the $\Delta$th interval, $W^{\mathrm{ts}} (\Delta)$ in equation (4), we obtain

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm E}\left[\overline{s}_i\right] = \sum_{\Delta=1}^{I} s_{i}^{\mathrm{ts}} \left(\Delta \right) \frac{\sum_{j=1; j\neq i}^{N} s_{j}^{\mathrm{ts}} \left(\Delta \right)}{\sum_{k=1}^{N}s_{k}^{\mathrm{ts}} \left(\Delta \right)}. \label{derivation_individual_strength} \nonumber \end{align} \tag{ 18 }$$

By summing and subtracting $s_{i}^{\mathrm{ts}}\left(\Delta \right)$ from the numerator, we get

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm E}\left[\overline{s}_i\right] = \sum_{\Delta=1}^{I} s_{i}^{\mathrm{ts}} \left(\Delta \right) \left[ 1 - \frac{s_{i}^{\mathrm{ts}} \left(\Delta \right)}{\sum_{k=1}^{N}s_{k}^{\mathrm{ts}} \left(\Delta \right)} \right], \nonumber \end{align} \tag{ 19 }$$

which can be rewritten as

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm E}\left[\overline{s}_i\right] = \overline{s}_{i}^{\mathrm{ts}} - \sum_{\Delta=1}^{I} \frac{\left[ s_{i}^{\mathrm{ts}} \left(\Delta \right)\right]^2}{\sum_{k=1}^{N}s_{k}^{\mathrm{ts}} \left(\Delta \right)}, \label{derivation_individual_strength_final} \nonumber \end{align} \tag{ 20 }$$

where ${\rm E}\left[\overline{s}_i\right]$ and $\overline{s}_{i}^{\mathrm{ts}}$ represent the expected and observed individual strengths, respectively. We observe that the EADM underestimates the observed strength, $\overline{s}_{i}^{\mathrm{ts}}$, by a quantity that only depends on the self-loops. The contribution of self-loops is inversely proportional to the size of the network and scales as 1/N. This result generalizes the proof in [39], based on the static configuration model, to temporal networks.

As a consequence, macroscopic quantities, such as the expected average strength, should become more accurate in the EADM as the size of the network increases. By averaging equation (20) for all nodes in the network we obtain

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\av}[1]{\langle #1 \rangle} \displaystyle {\rm E}\left[\av{\overline{s}}\right] = \av{\overline{s}^{\mathrm{ts}}} - \frac{1}{N} \sum_{i = 1}^{N} \sum_{\Delta=1}^{I} \frac{\left[ s_{i}^{\mathrm{ts}} \left(\Delta \right)\right]^2}{\sum_{k=1}^{N}s_{k}^{\mathrm{ts}} \left(\Delta \right)}, \label{derivation_average_strength_final} \nonumber \end{align} \tag{ 21 }$$

which scales as 1/N. In other words, since the EADM error comes from self-loops only, the observed quantities, $\overline{s}_{i}^{\mathrm{ts}}$ and $\newcommand{\av}[1]{\langle #1 \rangle} \av{\overline{s}^{\mathrm{ts}}}$, become equivalent to expected quantities if self-loops are included in both equation (20) and equation (21). We indicate these adjusted quantities as

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\av}[1]{\langle #1 \rangle} \displaystyle {\rm E}^{{\rm sl}}\left[\overline{s}_i\right] = \overline{s}_{i}^{\mathrm{ts}}, \qquad {\rm E}^{{\rm sl}}\left[\av{\overline{s}}\right] = \av{\overline{s}^{\mathrm{ts}}}, \label{derivation_individual_strength_final_selfloops} \nonumber \end{align} \tag{ 22 }$$

where the superscript 'sl' indicates that these sums include self-loops into equations (20) and (21).

In order to properly assess the error of the EADM, we consider two metrics: the relative error and the normalized root mean squared error. The relative error determines whether our estimators are unbiased, while the normalized root mean squared error is needed to ensure that the variance of our estimators is bounded. The theoretical relative error and normalized root mean squared error of the EADM are obtained by properly combining equations (20)–(22)

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\av}[1]{\langle #1 \rangle} \displaystyle {\rm RE} &= \Bigg | 1 - \frac{{\rm E}[\av{\overline{s}}]}{{\rm E}^{{\rm sl}}\left[\av{\overline{s}}\right]}\Bigg |, \nonumber \\ {\rm NRMSE} &= \sqrt{\frac{\sum_{i=1}^{N} \left[{\rm E}^{{\rm sl}}\left[\overline{s}_i\right] - {\rm E}\left[\overline{s}_i\right] \right]^2}{N {\rm E}^{{\rm sl}}\left[\overline{s}_i\right]^2 }}. \label{RE_NRMSE_Metrics_theory} \nonumber \end{align} \tag{ 23 }$$

3.4.2. Numerics

The mathematical analysis above suggests that the ETFM error is minimized, while the error of the EADM should decay as the inverse of the size of the network, 1/N, and coincide with predictions from equation (23).

The numerical relative error and normalized root mean squared error are computed as follows:

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\av}[1]{\langle #1 \rangle} \displaystyle {\rm RE} &= \Bigg | 1 - \frac{{\rm E}[\av{\overline{s}}]}{\av{\overline{s}^{\mathrm{ts}}}}\Bigg |, \nonumber \\ {\rm NRMSE} &= \sqrt{\frac{\sum_{i=1}^{N} \left[ \overline{s}_{i}^{\mathrm{ts}} - {\rm E}\left[\overline{s}_i\right] \right]^2}{N \av{\overline{s}^{{\rm ts}}}^2}}, \label{RE_NRMSE_Metrics_numerics} \nonumber \end{align} \tag{ 24 }$$

where we substitute the expected quantities, ${\rm E}^{{\rm sl}}\left[\overline{s}_i\right]$ and $\newcommand{\av}[1]{\langle #1 \rangle} {\rm E}^{{\rm sl}}\left[\av{\overline{s}}\right]$, in equation (23), with their observed values, $\overline{s}_{i}^{\mathrm{ts}}$ and $\newcommand{\av}[1]{\langle #1 \rangle} \av{\overline{s}^{\mathrm{ts}}}$. The remaining expected quantities in equation (24) can be either equations (15) and (16) for the ETFM numerics, or equations (20) and (21) for the EADM numerics.

In our numerics, shown in figure 2, we consider artificial networks having a homogeneous backbone with $\hat{\lambda} = 0.7$, as introduced in appendix A.1, and real systems, as presented in table 3. The cases of artificial networks having either a homogeneous backbone with $\hat{\lambda} = 0.02$ or heterogeneous backbone are explored in appendix A.2. We determine that, for both artificial and real systems, our theoretical arguments hold. Specifically, we find that the theoretical error of the EADM comes from self-loops only and it scales as the inverse of the network size. Further, we show that the ETFM improves the EADM estimation, lowering the relative and normalized root mean squared errors. However, the ETFM estimation is challenged by the excessive preponderance of backbone network, in terms of the normalized root mean squared error. This is due to the fact that the maximum likelihood approach of the ETFM in equation (9) estimates the activity values without considering the presence of the backbone network.

Zoom In Zoom Out Reset image size

Interestingly, we find that in both artificial and real systems, the relative EADM errors are about $1\%$ when networks reach one hundred of nodes. This amount of error is acceptable for many practical applications. On the contrary, when the artificial and real systems are smaller, the relative EADM error may reach up to $10\%$, challenging its usability for many practical purposes.

Going further in the comparison between the EADM, ETFM, and TDF, we examine the performance of the three approaches in detecting backbone networks as a function of the size of the network. We use the artificial network introduced in our prior work [19]. We analyze two different cases, resembling two realistic situations: one in which the backbone network is barely present, where we set $\hat{\lambda} = 0.02$, and another in which the backbone network appears almost at every time step, where we set $\hat{\lambda} = 0.7$. In this analysis, we set the univariate threshold $\beta$ equal to 0.01 [15, 19], and then correct it according to the Bonferroni correction as detailed in section 2.4, to obtain the $\beta^{\prime}$ used to filter out links explained by the null models.

The performance of the three approaches is determined through the analysis of the algorithms' precision and recall [40]. The former corresponds to the ratio between the number of true positives (all the links discovered that truly belong to the backbone network) divided by the number of all the detected links (true and false positives). The latter metric corresponds to the ratio between the true positives divided by the sum of true positives and false negatives (all the links in the irreducible backbone).

As shown in figures 3(a) and (c), when the backbone network is barely present, the TDF does not detect any link (recall is zero and precision is not defined). The ETFM outperforms the EADM, while it falls behind the EADM in terms of recall. In other words, the EADM detects more links than the ETFM and, some of them are false positive that belong to the known backbone network. When the size of the network reaches about one hundred nodes, the EADM and ETFM are equivalent. When the backbone network is present almost in every time step, the TDF has the highest precision among the three methodologies, but its recall goes rapidly to zero when the size of the network increases, as shown in figures 3(b) and (d). In this case, the EADM and ETFM perform similarly in terms of precision and recall, and they are accurate only when the size of the system reaches about one hundred nodes. If links in the backbone network appear in almost all time steps, they significantly modify the activity estimation in equations (3) and (9), which lowers the performance of the EADM and ETFM.

Zoom In Zoom Out Reset image size

The analysis of artificial networks suggests that the TDF does not detect false positive, while often missing major parts of the backbone network. Failing to detect most of the backbone network may be due to two main aspects: (i) the use of the Bonferroni correction [37], which increases the methodology's precision and lowers its recall; and (ii) the heterogeneous distribution of activity values, whereby in appendix A.3 we determine an improvement in the number of true positives when dealing with a homogeneous activity distribution. The ETFM offers adequate performance in many situations, scoring poorly only when links in the backbone network are present at almost every time step. The EADM becomes equivalent to the ETFM when the size of the network reaches about one hundred nodes. Since the EADM is faster than the ETFM, it should be preferred for the study of large networks.

Detecting the backbone in real systems yields more challenges than the study of artificial networks. The main limitation is that the backbone network is not known a-priori and performance can only be assessed through comparison. A possible way to circumvent such a limitation is to observe whether or not results from real systems are coherent with findings on artificial networks.

According to our results on artificial networks, the TDF has the most restrictive null hypothesis, which leads to the least number of links detected in the backbone network. The ETFM finds smaller backbone networks than the EADM when the networks under examination have only tens of nodes, while they tend to become equivalent for larger systems. To confirm this claim in real systems, we compare the set of irreducible links detected by the three methodologies, using the EADM as reference. We compare the sets of links discovered by the TDF, $L_{{\rm TDF}}$, and by the ETFM, $L_{{\rm ETFM}}$, with that of the EADM, $L_{{\rm EADM}}$. The dimension of a set is indicated with $|\cdot|$. We use two metrics: the ratio of the number of links $|L_{{x}}|/|L_{{\rm EADM}}|$ and the Overlap index [41], defined as

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm Overlap}(L_{{\rm EADM}}, L_{{x}}) = \frac{|L_{{\rm EADM}}\cup L_{{x}}|}{\min \left(|L_{{\rm EADM}}|, |L_{{x}}|\right)}, \label{overlap_coefficient} \nonumber \end{align} \tag{ 25 }$$

where x  =  {ETFM, TDF}.

The ratio $|L_{{x}}|/|L_{{\rm EADM}}|$ is useful to quantify whether the EADM detects more links than the ETFM and TDF. The Overlap coefficient in equation (25) measures the fraction of shared links between the two methodologies, thereby helping ascertain whether the ETFM and TDF find a subset of the links detected by the EADM. In order to properly compare the EADM with the ETFM, we consider a series of values for the univariate threshold $\beta$ and indicate with a vertical black line the multivariate threshold $\beta^{\prime}$, properly modified according to the Bonferroni correction.

In figure 4, we show that the TDF detects less links than the ETFM, which, in turn, finds less links than the EADM, as expected. The fact that the TDF detects the least amount of links is due to its more restrictive null hypothesis, which ensures that no false positives are identified, but it misses many links that belong to the backbone network. ETFM and EADM results are affected by the network size; but when the entire school (formed by a few hundreds of nodes) is analyzed, the two methodologies become equivalent. This result is in line with the analysis of artificial networks.

Zoom In Zoom Out Reset image size

In figure 5, we show that, for most of the real datasets studied herein, the Overlap coefficient is close to one. This result implies that the ETFM and TDF share the same core of the backbone networks with the EADM. The few cases in which the Overlap coefficient is lower than one pertain to the comparison between the EADM and TDF, due to the difference in their null hypotheses.

Zoom In Zoom Out Reset image size

By combining the results of figures 4 and 5 we draw two main conclusions. First, the TDF has the most restrictive null hypothesis and detects the smallest backbone network. Second, the ETFM finds a subset of the links detected by the EADM only when a classroom (composed of only tens of nodes) is studied, while it identifies the same backbone network when the entire school (composed of only hundreds of nodes) is analyzed. Since the EADM is faster than the ETFM, it should be used to discover backbone networks in larger systems.

In table 4, we synoptically present the take-home message of the comparisons conducted throughout this paper. While, the EADM should be used for large networks and ETFM for small networks, the TDF can be applied to any network. The EADM and ETFM can be successful in identifying many irreducible links, but this may come at the cost of some of the reducible links being inaccurately assigned to the backbone. The TDF allows to filter out almost all the reducible links, but it tends to miss most of the irreducible links.

Table 4. Range of validity of each methodology (top row) and their main advantage and disadvantage (bottom row).

		Evolving activity driven network	Evolving temporal fitness model	Temporal disparity filter
Network size	Small		$\checkmark$	$\checkmark$
	Large	$\checkmark$		$\checkmark$
Advantage (Disadvantage)	Detection of many irreducible links (Some reducible links inaccurately ascribed to the backbone)	$\checkmark$	$\checkmark$
	No reducible links is inaccurately identified as part of the backbone (Many of the irreducible links are not detected)			$\checkmark$

We present here an extension of the generative algorithm proposed in our previous work [19]. Specifically, we introduce a mechanism to create a temporal network with known backbone network and arbitrary distribution of reducible and irreducible links. The distribution of reducible links is regulated by the activity distribution $F(a)$, while the distribution of irreducible links is controlled by the preponderance of the backbone network, $G(\lambda)$. The case of heterogeneous activity distribution $F(a) \sim a^{-2.1}$, with $a \in \left[a_{{\rm min}}, 1\right]$, and homogeneous backbone network $G(\lambda) \sim \delta \left(\lambda - \hat{\lambda} \right)$ is already described in our previous work [19].

The procedure is as follows.

• (i)  
  We generate a temporal network unfolding over an observation window of length T, partitioned into I consecutive intervals. We manually set the initial time of the first interval at the beginning of the time series, $t_{\mathrm{in}}(1)=1$, and randomly draw without replacement the I  −  1 initial time of the remaining intervals in $\{2,...,T\}$, which we sort as $t_{\mathrm{in}}(2) < t_{\mathrm{in}}(3) < \dots < t_{\mathrm{in}}(I)$. The generic interval $\Delta$ has length $\tau(\Delta)$, and the average length of the intervals is $\newcommand{\av}[1]{\langle #1 \rangle} \av{\tau(\Delta)} = T/I$.
• (ii)  
  Each node in the network has a time-varying, piece-wise constant, individual activity, a_i(t), which is extracted according to the following procedure.

  • For the first interval, $\Delta=1$, we extract N activities, one for each node in the network, from the activity distribution $F(a)$. These values are held constant in the interval.
  • When $2 \leqslant \Delta \leqslant I$, we may observe correlations between the activities in the present interval and the previous one, that is, between $[t_{{\rm in}}(\Delta-1), t_{{\rm in}}(\Delta-1)+\tau(\Delta-1)-1]$ and $[t_{{\rm in}}(\Delta), t_{{\rm in}}(\Delta)+\tau(\Delta)-1]$, respectively. Activities vary according to $a_i (t_2) = a_i (t_1) \rho + y(1-\rho)$, where y  is a random number extracted from $F(a)$, and $\rho$ is an autocorrelation parameter.
• (iii)  
  In the whole observation window $[1, T]$, we generate a temporal network where both reducible and irreducible links are present.

  • Reducible links are created according to equation (2).
  • Once reducible links are formed, we appoint a fraction $\newcommand{\e}{{\rm e}} \epsilon$ of them that appeared at least once in the overall temporal evolution as the irreducible links. For each of these irreducible links ij of the backbone network, we record the time instants where the adjacency matrix is zero and with probability $\lambda_{ij}$, we create a temporal link in that time instant, that is, we switch A_ij to 1. The parameter $\lambda_{ij}$, extracted from $G(\lambda)$, measures the preponderance of the link during the whole observation window, such that larger values of $\lambda_{ij}$ favor the association between the link and the backbone network.

As in the main text, we consider the case of heterogeneous activity distribution $F(a) \sim a^{-2.1}$ with $\newcommand{\av}[1]{\langle #1 \rangle} a_{{\rm min}} =[\sqrt{\av{\tau(\Delta)}}]^{-1}$. The backbone networks considered in figure A1 are three: (i) a homogeneous backbone with a low value of $\lambda$, $G(\lambda) \sim \delta \left(\lambda - 0.02\right)$ in panels (a) and (d); (ii) a homogeneous backbone with a high value of $\lambda$, $G(\lambda) \sim \delta \left(\lambda - 0.70\right)$ in panels (b) and (e); and (iii) a heterogeneous backbone $G(\lambda) \sim \lambda^{-2.3}$ and $\lambda \in \left[0.02, 1\right]$ in panels (c) and (f). We find that the ETFM provides better estimations than the EADM, whose error scales as the inverse of the size of network. Further, the ETFM is challenged by the excessive preponderance of the backbone network, whereby $\hat{\lambda} = 0.70$ yields a normalized root mean squared error that is comparable to the one of the EADM.

Zoom In Zoom Out Reset image size

We corroborate the results in the main text regarding precision and recall of the EADM, ETFM, and TDF, by analyzing the case of a heterogeneous backbone network with $G(\lambda) \sim \lambda^{-2.3}$ and $\lambda \in \left[0.02, 1\right]$, in figure A2. For small systems, the highest precision is given by the TDF, then by the ETFM, and finally by the EADM; with respect to recall, we find the opposite scenario. For large systems, all methodologies yield the same precision; the recalls of EADM and ETFM are similar, and they are both much higher than the TDF.

Zoom In Zoom Out Reset image size

To shed some light into the reasons for the small recall in the TDF, we consider the case a homogeneous activity distribution, $F(a) \sim \delta \left(a - \sqrt{0.001}\right)$. Activities are time invariant as we consider a single interval, I  =  1, with length equal to the whole observation window, that is, $\tau(1) = T = 5000$. The backbone networks considered in figure A3 are three: (i) a homogeneous backbone with a low value of $\lambda$, $G(\lambda) \sim \delta \left(\lambda - 0.02\right)$ in panels (a) and (d); (ii) a homogeneous backbone with a high value of $\lambda$, $G(\lambda) \sim \delta \left(\lambda - 0.70\right)$ in panels (b) and (e); and (iii) a heterogeneous backbone $G(\lambda) \sim \lambda^{-2.3}$ with $\lambda \in \left[0.02, 1\right]$ in panels (c) and (f). In all the cases, both precision and recall shown close to one, suggesting that the low recall shown in figures 3 and A2 may be due to heterogeneity in the activity distribution. Another reason for the low recall observed in figures 3 and A2 may be the use of the Bonferroni correction [37], which increases the precision of the methodology and lowers its recall.

Zoom In Zoom Out Reset image size

In figure B1, we report the missing results of figure 4 in the main text concerning the fraction of links detected by the ETFM or TDF over the EADM, $|L_{{x}}|/|L_{{\rm EADM}}|$.

Zoom In Zoom Out Reset image size

In figure B2, we report the missing results of figure 5 in the main text concerning the Overlap index between either the ETFM or TDF and the EADM, Overlap ($L_{{\rm EADM}}$, L_x).

Zoom In Zoom Out Reset image size