Network archaeology: 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 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.
