Phase transition in the recoverability of network history
arXiv:1803.09191 · doi:10.1103/PhysRevX.9.041056
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.
arXiv comment18 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 (21)
- Emergence of scaling in random networks
- Power-law distributions in empirical data
- Network robustness and fragility: Percolation on random graphs
- Topology of evolving networks: local events and universality
- Connectivity of Growing Random Networks
- Bose-Einstein condensation in complex networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Measuring preferential attachment for evolving networks
- Statistical properties of sampled networks
- Evolution of reference networks with aging
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- Degree Distributions of Growing Networks
- Network Archaeology: Uncovering Ancient Networks from Present-day Interactions
- Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
- Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
- Typology of phase transitions in Bayesian inference problems
- Statistical validation of high-dimensional models of growing networks
- 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
- Structural preferential attachment: Stochastic process for the growth of scale-free, modular and self-similar systems
- Complex networks as an emerging property of hierarchical preferential attachment