The Buckley-Osthus model and the block preferential attachment model: statistical analysis and application

Wenpin Tang, Xin Guo, Fengmin Tang

Introduction

Most real-world networks exhibit two distinct structural features: community structure (nodes cluster into groups with different behaviors) and power-law degree distributions (a few "hubs" have many connections, while most nodes have very few).

Classic network models typically capture only one of these phenomena. Stochastic Blockmodels (SBM) are excellent at modeling communities but produce unrealistic Poisson degree distributions. Conversely, Preferential Attachment Models (PAM) successfully produce power-law distributions—often summarized as "the rich get richer"—but usually assume a homogeneous population without distinct communities.

While hybrid models exist to capture both features, they often lack rigorous statistical guarantees. This paper bridges that gap by providing a mathematical foundation for two evolving network models: the Buckley-Osthus model and the Block Preferential Attachment Model (BPAM). The authors prove that Maximum Likelihood Estimates (MLE) for these models are consistent and asymptotically normal, allowing researchers to reliably estimate parameters from real-world data.

Models and Theoretical Guarantees

The authors focus their statistical analysis on two specific models:

  1. Buckley-Osthus Model: A generalized PAM where an initial "attractiveness" parameter $a$ allows for a tunable power-law exponent.
  2. Block Preferential Attachment Model (BPAM): A novel model where nodes belong to $K$ distinct communities. The probability of a new node connecting to an existing one depends on both the existing node's degree (popularity) and the specific interaction strength ($\gamma$) between their respective communities.

Key Technical Contribution: The authors prove the consistency of the MLE for both models. This means that as the network grows larger, the estimated parameters converge almost surely to their true values ($\hat{a} \to a_0$ for Buckley-Osthus, and $(\hat{\pi}, \hat{\gamma}) \to (\pi^0, \gamma^0)$ for BPAM).

For the Buckley-Osthus model, they go further to prove asymptotic normality, providing a pathway for hypothesis testing and confidence intervals. Because these models are "order-dependent"—meaning the history and sequence of the network's evolution matter—their likelihood functions do not belong to the standard exponential family of distributions. Consequently, the proofs require sophisticated tools from probability theory, such as martingales and the Azuma-Hoeffding inequality.

Simulation Studies

To corroborate their theoretical findings, the authors generated synthetic networks of varying sizes ($n = 100, 200, 500, \text{ and } 1000$). The goal was to verify that the MLE calculations converge to the ground-truth parameters as the sample size increases.

MLE consistency for the Buckley-Osthus model across different ground-truth values of initial attractiveness.

As shown in the simulations for the Buckley-Osthus model, the variance of the estimated parameter $\hat{a}$ decreases significantly as the network size grows, tightly centering around the true values ($a_0 = 0.5, 1.0, 2.0$).

MLE consistency for the BPAM interaction parameter gamma_22.

Similar convergence is observed for the BPAM. The standard deviation of the estimates for community interaction parameters, such as $\gamma_{22}$, shrinks predictably as $n$ increases, confirming the theoretical consistency of the MLE approach for these complex models.

Application: The Evolution of the Bitcoin Network

To demonstrate the practical utility of the BPAM, the authors applied it to a real-world dataset: the Bitcoin transaction network. Analyzing over 30 million transactions up to December 2013, they treated users as nodes and transactions as edges. Users were categorized into two communities: "super nodes" (the top 5% most active users, likely representing miners or exchanges) and "regular nodes."

By applying the BPAM, the authors observed a distinct structural shift in the network's evolution:

  • Stabilizing Power-Law: The power-law exponent for the Bitcoin network was found to stabilize around 4.4 for larger network slices ($n \ge 20,000$).
  • Network Maturity: In the network's early days, "super nodes" dominated interactions. However, as the network matured, the interaction parameter $\gamma_{22}$ (representing regular-to-regular user connections) grew significantly. This reflects the increasing participation of individual users and signals a move toward a more distributed, peer-to-peer ecosystem.

Limitations and Open Problems

While the paper provides strong theoretical foundations, the authors note several limitations and directions for future work:

  • Observed vs. Latent Communities: The proof for BPAM consistency assumes that community memberships are known a priori. In many real-world scenarios, these labels are hidden (latent).
  • Computational Complexity: Calculating the marginal likelihood when community labels are unknown is computationally intractable for large networks.

The authors conclude by highlighting three major open problems for the field:

  1. Developing efficient algorithms to recover latent community memberships in the BPAM (community detection).
  2. Proving whether MLE remains consistent when community labels are unknown.
  3. Finding computationally efficient approximations for the marginal likelihood to scale these models to massive, unlabeled networks.

Summary updated

Abstract

This paper is concerned with statistical estimation of two preferential attachment models: the Buckley-Osthus model and the block 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.
BibTeX
@inproceedings{tang2020buckley,
  author = {Wenpin Tang and Xin Guo and Fengmin Tang},
  title = {{The Buckley-Osthus model and the block preferential attachment model: statistical analysis and application}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=CBhCaxNcIo},
}
Figure