The Emergence of Persistent Centers in Growing Networks

25 concepts9 papers1 proposal

Imagine an evolving network—a social platform, the World Wide Web, or a spreading rumor. As new nodes and connections continuously arrive, the overall topology of the network shifts. If you track the "most important" or "most central" node in this system, what happens over time? Does the crown of centrality pass infinitely from node to node as the network expands, or does it eventually freeze onto a single, permanent leader?

This question defines the study of centrality persistence. Across various network models, researchers have discovered that growing networks frequently undergo structural freezing, where a single node or a tiny core establishes an unbreakable hold on centrality. Understanding why and when this stabilization occurs requires looking at the balance between local growth choices and global geometric constraints.

The Phase Transition of Degree Hubs

To understand why a network center stabilizes, we can first look at local connectivity, or degree centrality. In classic "rich-get-richer" models (linear preferential attachment), early nodes enjoy a head start, but it remains a dynamic race. What happens when we alter the strength of this feedback loop?

In Random networks with sublinear preferential attachment: Degree evolutions, Steffen Dereich et al. demonstrated a sharp phase transition in networks where popularity growth is sublinear. If the attachment preference of new nodes grows faster than the square root of a target node's degree ($\sqrt{d}$), a single persistent hub emerges and maintains the maximum degree for the remainder of the network's infinite growth. If the preference is weaker than $\sqrt{d}$, leadership changes hands infinitely often. The intuition here is a matter of variance versus growth rate: when the feedback mechanism is strong enough, the absolute gap between the top leader and its closest challenger widens faster than random fluctuations can bridge, locking the leader in place.

Attachment Preference > O(√d)  --->  Gap widens faster than noise  ---> Persistent Hub
Attachment Preference < O(√d)  --->  Noise overcomes the gap       ---> Infinite Fluctuations

A similar locking mechanism can be triggered by introducing choice. In The power of choice combined with preferential attachement, Yury Malyshkin analyzed a model where a new vertex samples a small number of random nodes and connects exclusively to the one with the highest degree. This simple injection of choice amplifies the rich-get-richer effect to a near-linear or strictly linear scale. The author proved that this optimization ensures a single node captures a fixed proportion of all future connections, rendering the probability of any other node overtaking it mathematically negligible.

Geometric Centers and Subtree Freezing

Centrality is not just about counting direct connections (degree); it is also about global position. In applications like network forensics—such as finding the patient zero of an epidemic or the source of a rumor—researchers track distance-based centers like the Jordan center (the node that minimizes the maximum distance to any other node) or the centroid (the node that minimizes the size of the largest neighboring subtree).

If the geometric center of a network shifts continuously as the graph grows, locating a source becomes a "moving target" problem. However, in Persistence of the Jordan center in Random Growing Trees, Sarath Pattathil et al. proved that in many common stochastic growth models, the Jordan center eventually stops moving entirely.

Why does a geometric center freeze? The mechanism relies on the balance of subtree growth. For a center to shift from its current node to a neighboring node, the subtree sitting behind that neighbor must grow large enough to pull the geometric middle toward itself. The authors showed that as random trees expand, the neighboring subtrees surrounding the core eventually reach a bounded relative size and stop expanding in all but one dominant direction. Because these local subtrees fail to maintain the growth rate of the global network, the mathematical criteria required to relocate the center can never be satisfied again, pinning the center to a single node forever.

[Subtree A] (Growth slows)
    \
     (Current Center) --- [Dominant Subtree] (Absorbs growth)
    /
[Subtree B] (Growth slows)

*Intuition: Subtrees A and B lose the capacity to pull the center toward them, freezing the center in place.*

Po-Ling Loh et al. expanded this principle to other metrics in Persistence of centrality in random growing trees, proving that the centroid measure exhibits the same permanent stabilization across various random tree models, confirming that global structural importance naturally crystallizes over time.

Terminal vs. Persistent Centrality

When analyzing this stabilization, researchers make a vital mathematical distinction between two types of long-term behavior:

  • Terminal Centrality: A node is terminally central if, as the network size approaches infinity, it eventually becomes more central than any other fixed node in the graph.
  • Persistent Centrality: A node is persistently central if there exists a specific, finite time step after which it remains the absolute center for all subsequent time steps.

In Analysis of Centrality in Sublinear Preferential Attachment Trees via the Crump-Mode-Jagers Branching Process, Po-Ling Loh et al. utilized continuous-time branching processes to show that sublinear preferential attachment trees are guaranteed to develop a unique terminal centroid. However, the authors noted that proving persistent centrality is a significantly steeper challenge. While terminal centrality guarantees that a node wins the asymptotic race against any single competitor, persistence requires proving that no new, late-arriving node will ever experience a temporary burst of growth large enough to steal the crown at any discrete step in the future.

Structural Stability in the Real World

This theoretical freezing explains why large, real-world networks maintain highly predictable, stable cores despite chaotic local changes.

For instance, B. Kahng et al. demonstrated in Robustness of the in-degree exponent for the World-Wide Web that when the introduction of new nodes dominates the creation of internal links, a network's connectivity distribution reaches a stable state that resists external parameter fluctuations.

This global resilience means that natural network growth behaves less like random noise and more like a structured trajectory. In Modeling and Measuring Graph Similarity: The Case for Centrality Distance, Matthieu Roy et al. introduced "centrality distance" to track how structural roles shift during graph evolution. They found that authentic network growth inherently minimizes changes in global centrality metrics. The network preserves its structural hierarchy as it scales.

This architectural stability can be exploited strategically. In From the Periphery to the Core: Information Brokerage in an Evolving Network, Bo Yan et al. studied how a newcomer node can efficiently navigate toward an optimal central position. Because the minimum eccentricity core of an evolving network remains highly stable over time, algorithms can target a reliable, unchanging topological center rather than chasing a rapidly shifting target.

Finally, this phenomenon explains the persistence of elite nodes in competitive environments. In Beyond preferential attachment: falling of stars and survival of superstars, Shahar Somin et al. examined rank dynamics rather than absolute connection counts. They discovered that while absolute popularity can fluctuate wildly, top-ranked nodes fall into stable, non-monotonic rank zones. These "superstars" are insulated from structural decay because the global dynamics of the network lock their relative positions in place, ensuring that the top of the hierarchy remains frozen even as the base of the network churns continuously.

Key Foundational Work

Random networks with sublinear preferential attachment: Degree evolutions (2008) — contributed 2 concept elements to this direction.
Robustness of the in-degree exponent for the World-Wide Web (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_terminal_vs_persistent_centrality_0494a59e,
  title = {terminal vs. persistent centrality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/terminal-vs-persistent-centrality/rdr_0494a59e7b6d4f2aaaa427d32e7af3b2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_terminal_vs_persistent_centrality_0494a59e_v1,
  title = {terminal vs. persistent centrality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/terminal-vs-persistent-centrality/rdr_0494a59e7b6d4f2aaaa427d32e7af3b2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake