Phase transition in the recoverability of network history
| Autor: | Young, Jean-Gabriel, St-Onge, Guillaume, Laurence, Edward, Murphy, Charles, Hébert-Dufresne, Laurent, Desrosiers, Patrick |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Phys. Rev. X 9, 041056 (2019) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1103/PhysRevX.9.041056 |
| Popis: | 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. Comment: 18 pages, 10 figures. Supplemental Material available online at https://journals.aps.org/prx/supplemental/10.1103/PhysRevX.9.041056/jgy2019_prx_SM.pdf |
| Databáze: | arXiv |
| Externí odkaz: |
|