  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.
