Introduction
In the study of growing networks, the "rich-get-richer" phenomenon—formally known as preferential attachment—is a cornerstone concept. While linear models like the Barabási-Albert model are well-understood, many real-world systems, including Wikipedia edit histories and citation networks, exhibit sublinear preferential attachment. In these cases, the probability of a new node attaching to an existing one grows at a fractional rate relative to its degree. This paper investigates whether a unique "center" emerges in such networks and if this centrality can be leveraged to identify the network's original root node.
The Sublinear Model and Methodology
Unlike linear models that can be analyzed using discrete-time tools like Pólya urns, sublinear models require a more sophisticated approach. The authors employ Crump-Mode-Jagers (CMJ) branching processes to embed the tree's growth into continuous time. In this framework, each node acts as an individual that "gives birth" to new nodes at rates defined by an attraction function $f$. By utilizing the Malthusian parameter—representing the exponential growth rate of the population—the authors apply convergence theorems to analyze subtree sizes as the network grows toward infinity.
Key Insights: Defining Centrality
A central challenge in this research is defining a robust measure of "balancedness" for a node. The authors define $\psi_T(u)$ as the size of the largest subtree connected to node $u$. A "centroid" is then defined as the node that minimizes this value, representing the most balanced point in the graph.
This continuous embedding allows the authors to treat the discrete jumps of node additions as a smooth process, using the ratio of independent random variables to represent subtree proportions in the limit. This mathematical shift is what enables the analysis of sublinear functions where traditional methods fail.
Main Results
1. Existence of a Unique Terminal Centroid
The paper proves that in sublinear preferential attachment trees, a unique terminal centroid exists with probability 1. This means that as the network grows, one specific node eventually becomes more central than any other fixed node.
2. Root Inference
A significant practical implication of this work is the ability to find the "root" (the first node) of a massive, anonymous network. The authors demonstrate that for a specific subclass of sublinear trees (where $f(i) = (i+1)^\alpha$), one can construct a finite-sized confidence set. For any desired confidence level, there exists a fixed number $K$ such that the root node is guaranteed to be among the $K$ most central nodes, regardless of the total network size.
Limitations and Future Work
While the paper establishes terminal centrality, it does not yet prove persistent centrality—the state where a node becomes the centroid at a finite time and never loses that status. In sublinear models, the centroid could theoretically shift between a few nodes indefinitely. Furthermore, the root-inference results are currently limited to specific power-law attraction functions; generalizing these findings to all non-decreasing sublinear functions remains an open mathematical challenge.
Summary updated