Phase Transition in the Recoverability of Network History

Network growth processes can be understood as generative models of the structure and history of complex networks. This point of view naturally leads to the problem of network archaeology: reconstructing all the past states of a network from its structure—a difficult permutation inference problem. In this paper, we introduce a Bayesian formulation of network archaeology, with a generalization of preferential attachment as our generative mechanism. We develop a sequential Monte Carlo algorithm to evaluate the posterior averages of this model, as well as an efficient heuristic that uncovers a history well correlated with the true one, in polynomial time. We use these methods to identify and characterize a phase transition in the quality of the reconstructed history, when they are applied to artificial networks generated by the model itself. Despite the existence of a no-recovery phase, we find that nontrivial inference is possible in a large portion of the parameter space as well as on empirical data.

Popular Summary

Over the past few decades, physics has extended its reach to complex objects of inquiry that are best represented as networks, such as power grids or webs of social interactions. These networks are fundamentally dynamical objects: They have a past, present, and future. While it is known that such descriptions can lead to accurate predictions, we often only have access to snapshots taken at specific points in time. An important question to answer, then, is whether we can use the present state of networks to determine their history. We argue that we often can, and we show how to do it. Most importantly, we find that when a rich-get-richer dynamic governs the evolution of networks, temporal reconstruction can become impossible if the driving mechanism is too strong.

We adopt a statistical approach and use a generative model to ascribe probabilities to the possible past states of network snapshots. Explicitly computing these probabilities is challenging, so we develop state-of-the-art sampling techniques tailored to the model. When we use this model to construct artificial networks with known histories, we find that the number of symmetries determines its recoverability: Beyond a certain number, the network undergoes a phase transition where history cannot be retrieved. Luckily, we also find that many real networks fall in the recoverable phase, something we can exploit to infer the history of statically observed networks.

While we provide compelling qualitative and numerical evidence for the existence of a phase transition, we have yet to pinpoint the exact location of this transition, something we leave for future work. Another essential open challenge is making our inference methods more scalable: The state-of-the-art method we use does not scale to networks of more than a few thousand nodes.

Figure 1

Reconstructing the history of a growing network. (a) Artificial network generated by our generalization of the preferential attachment model (with parameters $\gamma =-1.1$, $b=0.9$, $T=50$; see text). Since the network is artificial, its true history—i.e., the time of arrival of its edges in time—is known. The width and color of edges encode this history; older edges are drawn with thick, dark strokes, while younger edges are drawn using thin, light strokes. The age of the nodes is encoded in their radius. Our goal is to infer this history as precisely as possible, using the (unlabeled) network structure as our only input. (b) Accurate reconstruction obtained with $10^5$ samples of the posterior distribution over possible histories.

Figure 2

Network zoo. Examples of networks generated by the process with $b=1$ (top row) and $b=0.75$ (bottom row), and $\gamma \in \{-10,-1,0,1,10\}$ (from left to right). The width and color of edges encode this history; older edges are drawn with thick, dark strokes, while younger edges are drawn using thin, light strokes. The age of the nodes is encoded in their radius.

Figure 3

Effect of the rich-get-richer phenomenon on recovery. We analyze artificial networks of $T=50$ edges, generated with our generalization of the preferential attachment and the parameters $\gamma \in [-10,10]$, (a) $b=1$ (trees), and (b) $b=0.75$ (loopy networks). We plot the average correlation attained by the Monte Carlo approximation of the minimum mean-squared error (MMSE) estimators and two efficient methods based on network properties (a degree-based method and the onion decomposition [58]). A loose upper bound that accounts for network symmetry is also shown [see Eq. (17)] as well as a measure of our uncertainty of the MMSE estimators (right axis) [see Eq. (8)]. Each point is obtained by averaging the results over $m$ different network instances, where ($b=1$) $m=40$ and ($b=0.75$) $m=250$. We use the true parameters ($\gamma$, $b$) and $n$ Monte Carlo samples to approximate the MMSE estimators, where $n={10}^5$ ($b=1$) and $n=5\times {10}^6$ ($b=0.75$).

Figure 4

Finite-size scaling analysis for the results of Fig. 3. The average correlation attained by OD is shown against the size $T$ of networks generated using (a) $b=1$ and (b) $b=0.75$, for $\gamma \in \{1.00,1.10,1.25,1.50,1.75,2.00,2.25\}$ (from top to bottom). Two scaling curves are highlighted and annotated in each figure: the curve associated with the largest value of $\gamma$ that does not decline with $T$ (blue), and the first curve that varies with $T$ after that (orange). (c) Scaling of the symmetry bound for the same values of $\gamma$ in the case of trees (left) and dense graphs (right). The scaling is not computed for large values of $T$ due to computational costs. Note that there are many known structural transitions between the highlighted curves [41], which are not shown for the sake of clarity.

Figure 5

Finite-size scaling of the average information content. (a) Average information content $⟨S(G)⟩$ of tree networks ($b=1$), as a function of network size $T$, for exponents $\gamma \in \{\frac{5}{4},\dots ,\frac{11}{10},1\}$ of the nonlinear kernel. Color matches what is highlighted in Fig. 4. We know that these are upper and lower bounds on ${\gamma }_c$ due to the scaling analysis. The dotted line is the upper bound $\log (T)$ on the information content. (b) Information content not accounted for by the degree classes, i.e., $⟨S(G)-S_{\mathrm{deg}}(G)⟩$, where $S_{\mathrm{deg}}(G)$ is the Shannon entropy of the partition obtained by classifying edges according to their nodes’ degree (see text).

Figure 6

Root finding on artificial trees. We show the success rate of the root-finding algorithms, with sets $\mathcal{R}$ of sizes $K=5$ and $K=20$ on artificial networks of $T=50$ edges. The results of OD are shown with solid lines and symbols, while the sampling results are shown with symbols and error bars of 1 standard deviation. The horizontal solid lines show the accuracy of randomly constructed sets $\mathcal{R}$ (no information retrieval), while the horizontal dotted lines show the expected success rate in the limit $\gamma \to -\infty$, where a simple peeling technique is optimal. The sampled root sets are computed for $\gamma \in \{-1,-\frac{1}{2},0,\frac{1}{2},1\}$, using $n={10}^5$ samples.

Figure 7

Application to synthetic networks grown with a model that includes memory effects. (Top row) Single network instances with various values of the memory parameters $\alpha$ [43]. Edge thickness and node size encode age according to the ground truth (thicker and bigger equals older). Older nodes have a large probability of attracting new neighbors for the network shown on the left (memory parameter $\alpha =-2$), while newer nodes are advantaged in the other two cases ($\alpha =0.75$ and 2). The negative effect of memory on attachment probability is strongest for the network shown on the right, with $\alpha =2$. We find that these networks are best modeled with $\widehat{b}=1$ and, from left to right, $\widehat{\gamma }=1.76,0.00,-1.61$ for the growth model (see Appendix pp1 for details). The KS statistics $D^{*}$ on our estimates of $\gamma$ are $D^{*}=0.044$, 0.055, 0.052, and the significance levels are $P(D>D^{*})=0.47$, 0.45, 0.39, signaling a good fit (see Appendix pp1 for details). The uncertainty scores are $U(G)=0.24$, 0.39, and 0.22 [see Eq. (8)]. (Bottom row) Fraction of edge pairs correctly ordered by the estimators, when separated by at least $t_{\min }$ time steps according to the ground truth, for the single instances of the model shown in the top row. Ties are broken at random for the degree and OD estimators. MMSE estimators are calculated from $n=200000$ Monte Carlo samples, using the estimated parameters.

Figure 8

Application to the phylogenetic tree of strains of the Ebola virus. (Left diagram) Leaves ($n=1238$, in orange) represent strains of Ebola sequenced during the 2013–2016 West African outbreak [65], while the remainder of the nodes represent inferred common ancestors ($n=959$, in blue), and edges are most likely mutations [66]. Edge thicknesses indicate age according to the ground truth. We find that this network is best modeled with $\widehat{b}=1$ and $\widehat{\gamma }=-0.71$, associated with a KS statistic of $D^{*}=0.17$ and a significance level of $P(D>D^{*})=0.53$ under the random model, signaling a good fit (see Appendix pp1 for details). The uncertainty score of the MMSE estimators is equal to $U(G)=0.001$ [see Eq. (8)]. (Right diagram) Fraction of edge pairs correctly ordered by the estimators, when separated by at least $t_{\min }$ time steps according to the metadata. Ties are broken at random for the degree and OD estimators. MMSE estimators are calculated with the $n=25000$ Monte Carlo samples.

Figure 9

Consistency of the estimator of $\mathit{\gamma }$ in small networks. We show the average difference between the true value and estimated value of $\gamma$, for networks of $T=1000$ edges generated with parameters $\gamma \in [-1,1]$ and $b\in [0.25,1.00]$. This difference is averaged over 20 different network realizations at each point of the parameter space. We use $n=1000$ samples each time we evaluate the average KS statistic.

Figure 10

Sensitivity analysis of the parameter estimators. Average correlation with the ground truth (top six panels) and relative error on the true correlation (bottom six panels) of the histories estimated by running the inference with misspecified parameters. These results are produced on trees ($b=1$, top rows) and on loopy graph ($b=0.75$, bottom rows), at various levels of heterogeneity ($\gamma \in \{-1,0+1\}$ from left to right); see also inset text. The bold square shows the reference value (no perturbation), while the rest of the heat map shows results for absolute perturbations of magnitude ${\mathrm{\Delta }}_{\gamma },{\mathrm{\Delta }}_b\in \{-0.2,-0.1,0.1,0.2\}$. Estimates above $\widehat{b}=1$ are impossible and therefore not computed (shown as a hatched region). We use the sampling level most appropriate for each case and $n=100000$ samples, and we average the results over 35 network instances.