Will the Leader Stay the Leader? Finite-Time Persistence Forecasts for Growing Networks from Sparse Timestamps

In a growing network, such as a citation graph, a trading platform or a transaction ledger, one node usually holds the top spot in connections or structural position. Mathematicians have shown that in some growth models this leadership eventually freezes on one node forever, and in others it changes hands infinitely often. These results say nothing about when freezing happens. They also cannot tell whether a particular real network, observed once with only a handful of known arrival dates, has already frozen. We propose a small probabilistic time-series model that answers this practical question. It explicitly tracks a few leading nodes by identity and summarizes all other nodes by average flows between degree classes. It is fit to a single snapshot plus sparse timestamps, and it outputs a calibrated probability that today's leader is still the leader at a future time. It also outputs a posterior over the past moment when leadership locked in.

The opportunity comes from a mismatch among four bodies of work. Persistence theorems are asymptotic and identity-based. Rate equations, which are differential equations for how many nodes have each degree, are finite-time but anonymous. Dynamic Bayesian networks, which are latent-state models unrolled over time slices, handle sparse, noisy observation but break down when the set of variables grows. Sparse temporal supervision shows that a few known arrival orders can rescue history reconstruction from a static snapshot. Each of these has the piece the others lack. The point of joining them is a single deliverable: a finite-time, finite-data forecast of leadership persistence.

Core Claim

Persistence of centrality is governed by a contest between how fast the leader's lead grows and how much random fluctuation the challengers' growth has. Dereich and Mörters show this for degree under sublinear preferential attachment, where new nodes attach to existing nodes with probability rising as degree to a power $\alpha$ below 1. A single persistent hub emerges almost surely when $\alpha > 1/2$, and leadership changes forever when $\alpha < 1/2$. That contest involves only a few nodes, the leader and its nearest challengers. The rest of the network enters only through the total "attractiveness" that divides up each new edge. This suggests a hybrid state.

The few contenders are tracked exactly. Their degree $D_i(t)$ grows on average as

$$\frac{d\,\mathbb{E}[D_i]}{dt} = m\,\frac{f(D_i)}{Z(t)}, \qquad Z(t) = \sum_k f(k)\,N_k(t),$$

where $m$ is the number of edges each newcomer brings, $f$ is the attachment kernel, and $N_k(t)$ is the expected number of nodes of degree $k$. $N_k(t)$ comes from the transient rate-equation solutions of Fotouhi and Rabbat, which handle arbitrary starting graphs. The contenders' discrete arrivals then make up the low-dimensional hidden state of a dynamic Bayesian network. Its time slices sit at the observed timestamps rather than on a uniform grid.

Our claim is that joint inference over three quantities is what makes finite-time persistence forecasts accurate and calibrated. Those quantities are the kernel, the contenders' unknown ages, and the leader–challenger gap. Plugging an asymptotic phase-transition verdict into a fitted kernel does not achieve this, and neither does simulating forward from a snapshot-only fit.

Research Program

The hybrid state is chosen to remove three named failure modes from the prior work.

The first is anonymity in rate equations. Fotouhi and Rabbat can say how the degree distribution forgets a star-shaped starting graph, but not whether the star's hub stays on top. Our identity-resolved contenders answer exactly that.

The second is that dynamic Bayesian networks fail on expanding graphs because the number of variables per slice grows. We avoid this by tracking only the top $K$ nodes. That is justified by Jog and Loh, who prove that the top-$K$ "inner circle" by centroid freezes in random trees. If the tracked set eventually stops changing, a fixed $K$ is not an arbitrary truncation. We add a rule that lets a newcomer enter the tracked set when its estimated growth would make it a contender, and we measure how often it fires.

The third concerns approximate inference. Settimi, Smith and Gargoum show that Gaussian approximations of these updates degrade when counts are small. This is a constraint on our design rather than a method we reuse. The contenders' edge arrivals between slices are small, discrete counts, so we propagate them with particles under exact multinomial transitions. A Gaussian approximation is used only for the bulk $N_k(t)$, where counts are large.

The observations are of two kinds. The first is one full snapshot at the current time, giving degrees and, for trees or a chosen spanning tree, subtree sizes. The second is a sparse set of anchors: arrival timestamps for a small random fraction of nodes, or known pairwise arrival orders in the style of Turowski, Sreedharan and Szpankowski.

The unknowns are the kernel parameters, the contenders' arrival times, and their degree paths through the slices. Inference uses particle Markov chain Monte Carlo, an algorithm that alternates between sampling kernel parameters and running a particle filter over the hidden degree paths. The anchors do two jobs. They break the confound between "old" and "intrinsically attractive" that makes kernel estimation from one snapshot unreliable. They also pin the contenders' ages, which a snapshot alone leaves ambiguous because of graph symmetries, the ill-posedness result of Turowski et al.

From the posterior we read off two quantities. The forward quantity is the probability that the current leader holds the top spot over a horizon $h$. The backward quantity is the posterior on the freezing time $\tau$, the last time leadership changed.

We do this for degree in general graphs. For the centroid, the node whose removal leaves the smallest largest piece, we do it on trees, where the leader's and challengers' subtree sizes evolve like the Pólya urns used by Jog and Loh. The Jordan center results of Pattathil et al. serve as a further synthetic test, since freezing there is proven but untimed. The analytical by-product we aim for is a gap-versus-fluctuation approximation for the distribution of $\tau$ near $\alpha = 1/2$. Existing theory gives no finite-time bound in that region.

Baselines

The naive reference point is "the current leader persists." It always predicts persistence and ignores all data. On networks in a frozen regime it will look deceptively good, so we report every metric separately for networks where a leadership change actually happens within the horizon.

The second baseline is the asymptotic plug-in. We estimate $\alpha$ from the anchored nodes' degree growth and predict persistence if and only if $\alpha > 1/2$, following Dereich and Mörters. For trees the centroid is always predicted to persist, following Jog and Loh. This is the most direct use of existing theory.

The strongest competitor is snapshot-calibrated forward simulation. We fit the kernel by maximum likelihood on the same anchors, assume the contenders' ages from their degrees, and simulate growth forward from the current snapshot many times. This is the strongest baseline because it already uses the correct generative model and all the same data. It differs from our method only in not inferring contender ages and kernel jointly through the history.

For the retrospective task of recovering arrival order, the baseline is the Turowski et al. reverse-growth sampler, which uses sparse pairwise supervision. On the ArXiv citation network it reports pairwise ordering precision of about 0.8 with 10% supervision, against about 0.47 for sorting by degree (Recovery of Vertex Orderings). For forecasting leadership persistence itself, no reported result was found on Lacuna for any method.

Fairness rules apply to all of these. Every method sees the same snapshot and the same anchor set at each supervision fraction. Every method gets the same simulation or sampling budget, measured in particle-steps or forward trajectories. Kernel hyperparameters are tuned on the same held-out synthetic graphs.

Two ablations isolate the key ingredient. The first is our model with ages fixed at point estimates, so there is no joint age inference. The second uses a pure mean-field normalizer with no identity-resolved contenders. Beating forward simulation means a lower Brier score and lower calibration error on the "leadership changed" subset at matched budget, with non-overlapping bootstrap intervals. On ordering, beating the baseline means exceeding roughly 0.8 precision at 10% supervision on ArXiv for the contender nodes.

Why not just…?

Why not just estimate $\alpha$ and apply the phase-transition theorem? The theorem says leadership "eventually" freezes. Near $\alpha = 1/2$, eventually can be far longer than any real observation window. Even in the persistent regime it says nothing about whether a lead change is likely in the next year. The plug-in baseline is in the experiments precisely to measure this. We expect it to be competitive far from 1/2 and poorly calibrated near it. If it is not, the finite-time machinery is unnecessary, and we will report that.

Why not just simulate forward from the snapshot with a fitted kernel? This is the real threat. Our argument is that snapshot-only fits confuse age with attractiveness, and that forward simulation with misassigned ages misjudges the gap's future growth. The age-fixed ablation tests this directly. If joint inference adds nothing at realistic supervision fractions (0.1–10%), the contribution shrinks to the retrospective $\tau$ posterior, which forward simulation cannot provide at all.

Why not just use the empirical rank zones? Somin et al. classify nodes as "superstars" or "stars" from an inverse-U curve of rank deterioration. Their analysis is degree-only, and they note it lacks closed-form bounds. It gives a zone label rather than a node-specific probability or a freezing time. We use their Amazon, Ethereum and eToro networks so that a zone-based classifier can be compared on the same forecasts.

Why not train a temporal graph neural network to predict the leader? Leadership changes are rare events, and one network gives essentially one training trajectory. A learned model has little to fit and offers no account of why a lead is safe. We treat it as a secondary comparison only on Somin's weekly data, where many snapshots exist.

Proposed Experiments

The synthetic experiments come first, because they have ground truth for $\tau$. We grow sublinear preferential attachment graphs with $\alpha$ swept across 1/2, uniform and preferential attachment trees, and graphs grown on star and double-star seeds as in Fotouhi and Rabbat. We reveal 0.1%, 1% and 10% of arrival times. We score the forward persistence probability with Brier score and calibration error, and the $\tau$ posterior with interval coverage and absolute error. The decisive check is whether our model stays calibrated in the band $0.4 < \alpha < 0.6$, where we expect the plug-in to fail. A second check is whether the centroid's predicted $\tau$ is systematically earlier than degree's on uniform trees, as Jog and Loh's stability result implies. If neither holds, the claim is wrong.

The real-network experiments use networks with full timestamps that we can hide. These are the ArXiv citation network and Simple English Wikipedia from Turowski et al., and the Amazon, Ethereum and eToro networks from Somin et al. We truncate each network at a past time $T_0$, keep a sparse anchor fraction, predict leadership persistence to later times, and check against the revealed history. The retrospective test compares the inferred $\tau$ with the actual last lead change before $T_0$. On ArXiv we also report pairwise ordering precision for the contenders, against the reported 0.8 / 0.47 figures.

The final decisive check is a graceful-failure test on networks where the theory's assumptions break. These are graphs with dense cycles, and the Ethereum and eToro networks, where nodes stop being active (as in vertex-deactivation models). There we expect calibration to degrade, and we will report by how much rather than claim robustness.