Abstract
This paper is concerned with statistical estimation of two preferential attachment models: the Buckley-Osthus model and the hierarchical preferential attachment model. We prove that the maximum likelihood estimates for both models are consistent. We perform simulation studies to corroborate our theoretical findings. We also apply both models to study the evolution of a real-world network. A list of open problems are presented.
Introduction
Most real-world networks—from the Internet to social media—exhibit two key features: heterogeneity (nodes belong to different communities) and a power-law degree distribution (a few "super-nodes" have many connections, while most have few). Existing models often fail to capture both simultaneously. The classic Erdős-Rényi model is too homogeneous, while the Stochastic Block Model (SBM) handles communities well but produces unrealistic degree distributions. Conversely, Preferential Attachment Models (PAM), like the Barabási-Albert model, capture the "rich-get-richer" growth but ignore community structures.
Furthermore, while these models are popular for simulations, their statistical properties are poorly understood. Specifically, proving that Maximum Likelihood Estimation (MLE) is consistent is difficult because these models are non-exchangeable: the order in which nodes arrive matters, and the likelihood function does not belong to the standard exponential family of distributions.
Methodology
The authors focus on two models:
- Buckley-Osthus (BO) Model: A one-parameter PAM that allows for self-loops and generalizes the standard linear PAM.
- Block Preferential Attachment Model (BPAM): A novel hybrid that adds community structure to the PAM. In BPAM, a new node joins a community with probability $\pi_j$ and connects to existing nodes based on both their current degree and a community-to-community interaction matrix $\gamma$.
To prove MLE consistency, the authors utilized martingale theory and concentration inequalities (specifically the Azuma-Hoeffding inequality) to show that the "path-dependent" likelihood functions converge to their true values as the network grows.
Empirical Evaluation
The theoretical findings were validated using synthetic data and an application to the Bitcoin transaction network.
Simulation Studies
The authors generated simulated networks with sizes $n \in \{100, 200, 500, 1000\}$ to verify that their estimators converged to the true parameters as the sample size increased.
As shown in the figure above, the spread of the MLE values for the Buckley-Osthus parameter $a_0$ tightens around the true parameter value (the blue line) as $n$ increases, confirming theoretical consistency. Similar convergence is observed for the BPAM community and interaction parameters.
Bitcoin Transaction Network
The models were applied to a dataset of over 30 million Bitcoin transactions (up to Dec 2013). The power-law exponent for the Bitcoin network was found to stabilize around 4.4 for $n \ge 20,000$. The BPAM parameters captured a "regime change" in the network's evolution, showing how the role of professional miners vs. individual users changed over time. Early on, transactions were dominated by super-nodes. As the network matured, the interaction parameters shifted, reflecting a more decentralized participation where regular users interacted more frequently with each other.
Discussion
A key insight is that in BPAM, "history" matters. Unlike many static graph models, the BPAM is dynamic. The probability of a connection depends on the state of the network at the exact moment a node arrives. This makes the denominator of the likelihood function node-order dependent—a significant mathematical hurdle. Consistency is non-trivial because the likelihood doesn't fit the "exponential family" mold; the authors had to prove that the proportion of nodes with a certain degree converges almost surely to a fixed probability distribution.
Limitations and Future Work
The current proof for BPAM consistency assumes community memberships are observed. In many real-world cases, these are "latent" (hidden). Calculating the MLE for the marginal likelihood (where memberships are unknown) is currently computationally intractable. Future work includes developing efficient algorithms to recover community memberships in a BPAM framework and exploring variational inference to improve scalability for massive datasets.
Summary updated