Phase transition in the recoverability of network history

Abstract

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.

18 pages, 10 figures. Supplemental Material available online at https://journals.aps.org/prx/supplemental/10.1103/PhysRevX.9.041056/jgy2019_prx_SM.pdf

References in corpus (5)

• Power-law distributions in empirical data
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Typology of phase transitions in Bayesian inference problems
• Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks
• Random Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs

Cited by in corpus (4)

• Choosing among alternative histories of a tree
• Uncovering hidden dependency in weighted networks via information entropy
• Inference for growing trees
• Belief propagation for permutations, rankings, and partial orders