PAFit: An R Package for Modeling and Estimating Preferential Attachment and Node Fitness in Temporal Complex Networks

Thong Pham, Paul Sheridan, Hidetoshi ShimodairaarXiv 2017 · arXiv

Abstract

Understanding the growth mechanisms of complex networks—such as social networks, citation webs, and biological systems—is a fundamental challenge in network science. PAFit is an R package that provides a robust, non-parametric framework for estimating two primary growth drivers: preferential attachment (PA) (the "rich-get-richer" effect) and node fitness (intrinsic quality). Unlike traditional parametric methods that assume fixed functional forms, PAFit learns these functions directly from temporal data using a Minorization-Maximization (MM) algorithm. This paper details the package's architecture, its high-performance C++ backend, and its application to real-world collaboration networks.

Introduction

Most real-world networks are dynamic, evolving through the continuous addition of new nodes and edges. To model this growth, researchers typically rely on two mechanisms:

  1. Preferential Attachment (PA): The probability of a node receiving a new connection increases with its current degree.
  2. Node Fitness: Some nodes possess inherent characteristics that make them more attractive for connections, independent of their current popularity.

A significant limitation in existing literature is the reliance on parametric models, which force these mechanisms into predefined mathematical boxes (e.g., power laws). If the underlying network dynamics deviate from these assumptions, the resulting estimates are biased. Furthermore, few tools allow for the simultaneous estimation of both PA and fitness. PAFit addresses these gaps by offering a non-parametric approach that estimates the attachment function $A_k$ for every degree $k$ and the fitness $\eta_i$ for every node $i$ jointly.

The PAFit Framework

The core of the package is the General Temporal (GT) model. In this model, the probability that a node $i$ receives a new edge at time $t$ is proportional to the product of its current attachment function and its fitness:

$$\Pi_i(t) \propto A_{k_i(t)} \eta_i$$

where $k_i(t)$ is the degree of node $i$ at time $t$. This framework is flexible enough to encompass several well-known network models as special cases.

To estimate these parameters without parametric assumptions, PAFit employs a Minorization-Maximization (MM) algorithm to maximize the log-likelihood of the observed network growth. To prevent overfitting, the package incorporates regularization terms, with smoothing parameters automatically selected via cross-validation.

Implementation and Performance

PAFit is designed for both ease of use and high performance. The core computational engine is implemented in C++ using Rcpp, with support for multi-core processing via OpenMP. This allows the package to scale effectively to large networks.

The package includes functions for generating synthetic networks, estimating parameters from empirical data, and converting between common network object formats like igraph and networkDynamic.

Empirical Results and Insights

The authors validated PAFit using both simulated data and a real-world collaboration network of network scientists (2000–2007).

The Importance of Joint Estimation

A key insight from the study is the "danger of isolation." Estimating PA or fitness separately often leads to significant errors. For instance, ignoring node fitness can lead to an overestimation of the preferential attachment exponent because the model incorrectly attributes a node's success solely to its current degree rather than its inherent quality.

Case Study: Network Science Collaborations

When applied to the collaboration network of 1,498 scientists, PAFit revealed:

  • Near-Linear Attachment: The attachment function was found to be nearly linear, confirming that the "rich-get-richer" effect is a dominant force in scientific collaboration.
  • Identifying "Fit" Nodes: The non-parametric approach successfully identified high-fitness nodes. The top three scientists by intrinsic fitness were Albert-László Barabási, Mark Newman, and Hawoong Jeong, reflecting their foundational roles in the field.

Conclusion

PAFit provides a powerful tool for researchers to uncover the hidden rules of network evolution. By providing non-parametric, joint estimation of PA and fitness, it offers a more nuanced view of network growth than traditional methods. Future work will focus on extending the model to handle edge deletion, node departure, and time-varying fitness.

Summary updated

Abstract

Many real-world systems are profitably described as complex networks that grow over time. Preferential attachment and node fitness are two simple growth mechanisms that not only explain certain structural properties commonly observed in real-world systems, but are also tied to a number of applications in modeling and inference. While there are statistical packages for estimating various parametric forms of the preferential attachment function, there is no such package implementing non-parametric estimation procedures. The non-parametric approach to the estimation of the preferential attachment function allows for comparatively finer-grained investigations of the `rich-get-richer' phenomenon that could lead to novel insights in the search to explain certain nonstandard structural properties observed in real-world networks. This paper introduces the R package PAFit, which implements non-parametric procedures for estimating the preferential attachment function and node fitnesses in a growing network, as well as a number of functions for generating complex networks from these two mechanisms. The main computational part of the package is implemented in C++ with OpenMP to ensure scalability to large-scale networks. We first introduce the main functionalities of PAFit through simulated examples, and then use the package to analyze a collaboration network between scientists in the field of complex networks. The results indicate the joint presence of `rich-get-richer' and `fit-get-richer' phenomena in the collaboration network. The estimated attachment function is observed to be near-linear, which we interpret as meaning that the chance an author gets a new collaborator is proportional to their current number of collaborators. Furthermore, the estimated author fitnesses reveal a host of familiar faces from the complex networks community among the field's topmost fittest network scientists.
BibTeX
@misc{pham2017pafit,
  author = {Thong Pham and Paul Sheridan and Hidetoshi Shimodaira},
  title = {{PAFit: An R Package for Modeling and Estimating Preferential Attachment and Node Fitness in Temporal Complex Networks}},
  year = {2017},
  eprint = {1704.06017},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1704.06017},
}
Figure