Network Archaeology via Epidemic Processes: The Case of Growing Trees

We ask to what extent is the state of an epidemic process on a dynamic network informative about the network's past evolution. To answer this question, we formulate it as a hypothesis testing problem, wherein one must distinguish between two alternative timelines leading to the same graph. For the case in which both timelines are growing trees, we give sufficient conditions under which two timelines are distinguishable with high probability. We then give an example application of the general results to a natural model of randomly growing trees. The analysis of our estimators relies on information-theoretic techniques to bound the correlation between random variables.