I want to highlight the recent publication of “Phase transition in the recoverability of network history” in the open-access journal Physical Review X. In this paper, we look at how to infer the past state of a statically observed growing network; we also uncover a phase transition for the quality of the recovered history, governed by the strength of a rich-get-richer mechanism. When the degree distribution becomes too skewed, we find evidence that past state reconstruction becomes impossible.

The project has been a long time in the making; the Dynamica Lab started working on this project back in 2016 at a retreat (see a picture of the retreat after the break!). The product of our work first appeared as a preprint in 2018, and has significantly changed since: follow the link to take a look at what it became! Enormous thanks should go to the anonymous reviewers for their input that helped shape the manuscript. Details about where to find code, slides, and supplementary information are listed in my publication page.

PS: We already followed up on this work, together with Georce T. Cantwell at the University of Michigan, and Guillaume St-Onge at the Dynamica Labs. In the “sequel,” we derive an efficient and exact recovery algorithm for the past state of growing trees. By limiting ourselves to this special class of networks, we obtain a significant efficiency improvement on the algorithm used in the PRX paper, which relied on a state-of-the-art but costly sequential Monte-Carlo sampling method. Our manuscript is currently on the arXiv as a preprint.

(Part of) the team at our 2016 retreat.