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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jean-Gabriel Young, Guillaume St-Onge, Edward Laurence, Charles Murphy, Laurent Hébert-Dufresne, Patrick Desrosiers
Formato:	article
Lenguaje:	EN
Publicado:	American Physical Society 2019
Materias:	Physics QC1-999
Acceso en línea:	https://doaj.org/article/e5414dc46d3c41ba8d66760c04432c18
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e5414dc46d3c41ba8d66760c04432c18
record_format	dspace
spelling	oai:doaj.org-article:e5414dc46d3c41ba8d66760c04432c182021-12-02T12:01:52ZPhase Transition in the Recoverability of Network History10.1103/PhysRevX.9.0410562160-3308https://doaj.org/article/e5414dc46d3c41ba8d66760c04432c182019-12-01T00:00:00Zhttp://doi.org/10.1103/PhysRevX.9.041056http://doi.org/10.1103/PhysRevX.9.041056https://doaj.org/toc/2160-3308Network 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.Jean-Gabriel YoungGuillaume St-OngeEdward LaurenceCharles MurphyLaurent Hébert-DufresnePatrick DesrosiersAmerican Physical SocietyarticlePhysicsQC1-999ENPhysical Review X, Vol 9, Iss 4, p 041056 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999
spellingShingle	Physics QC1-999 Jean-Gabriel Young Guillaume St-Onge Edward Laurence Charles Murphy Laurent Hébert-Dufresne Patrick Desrosiers Phase Transition in the Recoverability of Network History
description	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.
format	article
author	Jean-Gabriel Young Guillaume St-Onge Edward Laurence Charles Murphy Laurent Hébert-Dufresne Patrick Desrosiers
author_facet	Jean-Gabriel Young Guillaume St-Onge Edward Laurence Charles Murphy Laurent Hébert-Dufresne Patrick Desrosiers
author_sort	Jean-Gabriel Young
title	Phase Transition in the Recoverability of Network History
title_short	Phase Transition in the Recoverability of Network History
title_full	Phase Transition in the Recoverability of Network History
title_fullStr	Phase Transition in the Recoverability of Network History
title_full_unstemmed	Phase Transition in the Recoverability of Network History
title_sort	phase transition in the recoverability of network history
publisher	American Physical Society
publishDate	2019
url	https://doaj.org/article/e5414dc46d3c41ba8d66760c04432c18
work_keys_str_mv	AT jeangabrielyoung phasetransitionintherecoverabilityofnetworkhistory AT guillaumestonge phasetransitionintherecoverabilityofnetworkhistory AT edwardlaurence phasetransitionintherecoverabilityofnetworkhistory AT charlesmurphy phasetransitionintherecoverabilityofnetworkhistory AT laurenthebertdufresne phasetransitionintherecoverabilityofnetworkhistory AT patrickdesrosiers phasetransitionintherecoverabilityofnetworkhistory
_version_	1718394780733407232

Phase Transition in the Recoverability of Network History

Ejemplares similares