Inference, Model Selection, and the Combinatorics of Growing Trees

One can often make inferences about a growing network from its current state alone. For example, it is generally possible to determine how a network changed over time or pick among plausible mechanisms explaining its growth. In practice, however, the extent to which such problems can be solved is limited by existing techniques, which are often inexact, inefficient, or both. In this Letter, we derive exact and efficient inference methods for growing trees and demonstrate them in a series of applications: network interpolation, history reconstruction, model fitting, and model selection.