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.

Figure 1

Interlacing of histories. (a) We count the number of histories for the tree rooted on the focal node, shown in white. (b) There are $(6!/1!2!3!)=60$ ways to interlace the nodes of the three subtrees, and (c) $1\times 1\times 2=2$ distinct orderings of these nodes for each of the interlacings. The total number of possible histories for the subtree rooted on the white node is therefore equal to $2\times 60=120$.

Figure 2

Examples of inference problems solved by our methods. (a) Arrival time of nodes in networks of 100 nodes grown with the uniform attachment rule, where incoming nodes attach to an extant node chosen uniformly at random. The black symbols show the posterior mean of the arrival times $⟨{\tau }_i⟩$ calculated for a single network, and the error bars denote the 50% credible interval (CI) for each ${\tau }_i$. Both sets of quantities are calculated exactly with Eqs. (1)–(9). Hence, randomness in the network growth process rather than the estimation procedure explain the fluctuations. They disappear once we average over networks, as shown by the solid line (3000 networks). As a comparison, these posterior mean estimators achieve an average correlation of 0.75 with the true history, while estimators based on the degree centrality achieve 0.65. (b) Evolution of the excess degree of a single preferential attachment network whose structure is known before $t=20$ and after $t=80$ but not in between. The shaded region shows the pointwise 95% CI on an interpolation of the excess degree between these two observations, while the orange line shows the posterior mean. (c) Posterior distributions of $\gamma$ for networks generated with the generalized preferential attachment model and an attachment kernel $k^{\gamma }$ [27]. Each posterior distribution $P(\gamma |G)$ is computed from 100 samples, and corresponds to a network of $n=1000$ nodes with kernel exponent $\gamma =0,1/3,2/3,1$.