Title: Network archaeology: 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 importance sampling algorithm to evaluate the posterior
averages of this model, as well as an efficient heuristic that uncovers the
history of a network in linear 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 non-trivial
inference is possible in a large portion of the parameter space as well as on
empirical data.