Temporal evolution of the degree distribution of alters in growing networks

Babak Fotouhi, Michael G. RabbatNetw. Sci 2018 · OpenReview

Abstract

The degree distribution of the neighbors of nodes in a network is a theoretically important tool that is invoked in diverse studies in network science, such as epidemics, network resilience, network search and observability, network synchronization, random walks, opinion dynamics, and other dynamical systems on networks. Many real networks grow, and their properties pertaining to the said phenomena evolve. There is a paucity of theoretical research on how the evolution of these properties depend upon time and upon the structure of the initial network. This paper addresses this problem by providing the first theoretical study of the temporal evolution of the nearest-neighbor degree distribution for arbitrary networks (with any size) in arbitrary times. The posited results enable the analysis of the structural properties of growing networks in the short-time and intermediary time regimes, which are typically ignored in favor of the steady state. We corroborate the solutions via Monte Carlo simulations on various topologies. As a byproduct of the obtained solutions, we also demonstrate that the existing result in the literature on the asymptotic behavior of the Pearson coefficient of growing networks under the preferential attachment mechanism is incorrect, and we present the correct solution.

Introduction

In the study of complex networks, understanding the local connectivity of nodes is paramount. A fundamental question often asked is: "What is the degree distribution of my neighbors?" This is formally known as the Nearest-Neighbor Degree Distribution (NNDD). It serves as a critical metric for modeling dynamic processes such as viral spread, information flow, and the robustness of infrastructure like power grids.

A network diagram illustrating nodes with varying degrees and their connections to neighbors.

Historically, network science has focused on the "steady state"—the asymptotic limit where a network has grown infinitely large. However, most real-world networks, from citation databases to emerging social platforms, are finite and constantly evolving. This research fills a significant gap by providing a theoretical framework to track NNDD over time, starting from any arbitrary initial configuration.

Methodology

The authors model network growth using the Preferential Attachment mechanism, where new nodes are more likely to connect to existing nodes that already possess high degrees. To capture the temporal dynamics, the study employs:

  1. Master Equations: Defining the expected change in the number of nodes of degree $k$ ($N_k$) and the number of links between nodes of degrees $k$ and $\ell$ ($N_{k,\ell}$) at each discrete time step.
  2. Generating Functions: Transforming these difference equations into partial differential equations (PDEs) to facilitate analytical solutions.
  3. Method of Characteristics: Solving the PDEs to derive exact expressions for the NNDD at any time $t$.

The theoretical models were validated through extensive Monte Carlo simulations (averaging 2,000 trials) across diverse initial topologies, including 10-regular rings, complete graphs, and small-world networks.

Key Insights and Results

The Importance of Initial Conditions

Unlike steady-state models, this framework explicitly incorporates the starting structure of the network. The research demonstrates that in the short and intermediary terms, the "memory" of the initial graph significantly dictates the connectivity patterns of neighbors.

Correcting the Pearson Coefficient

A pivotal finding of this work is the correction of a long-standing error regarding network assortativity. The Pearson correlation coefficient ($r$) measures whether hubs tend to connect to other hubs (assortative) or to low-degree nodes (disassortative). The authors prove that for preferential attachment networks, $r$ approaches zero as $\frac{\log^2 N}{\sqrt{N}}$ as the number of nodes $N$ increases. This corrects a widely cited result by Newman (2002), which suggested a denominator of $N$. Simulations confirmed the $\sqrt{N}$ scaling with an $R^2$ of 0.998.

Empirical Validation

The model's predictive power was tested using the ArXiv high-energy physics phenomenology (HEP-PH) citation dataset (1993–2003). The analytical solutions maintained a median relative error of less than 10% even after the addition of 1,000 new nodes, proving its applicability to real-world growing systems.

Conclusion

By moving beyond the steady-state assumption, this paper provides a robust tool for forecasting the structural evolution of growing networks. Future work may explore more complex arrival processes, such as Poisson distributions, and alternative growth mechanisms like "shifted-linear" preferential attachment to further generalize these findings.

Summary updated

Abstract

The degree distribution of the neighbors of nodes in a network is a theoretically important tool that is invoked in diverse studies in network science, such as epidemics, network resilience, network search and observability, network synchronization, random walks, opinion dynamics, and other dynamical systems on networks. Many real networks grow, and their properties pertaining to the said phenomena evolve. There is a paucity of theoretical research on how the evolution of these properties depend upon time and upon the structure of the initial network. This paper addresses this problem by providing the first theoretical study of the temporal evolution of the nearest-neighbor degree distribution for arbitrary networks (with any size) in arbitrary times. The posited results enable the analysis of the structural properties of growing networks in the short-time and intermediary time regimes, which are typically ignored in favor of the steady state. We corroborate the solutions via Monte Carlo simulations on various topologies. As a byproduct of the obtained solutions, we also demonstrate that the existing result in the literature on the asymptotic behavior of the Pearson coefficient of growing networks under the preferential attachment mechanism is incorrect, and we present the correct solution.
BibTeX
@inproceedings{fotouhi2018temporal,
  author = {Babak Fotouhi and Michael G. Rabbat},
  title = {{Temporal evolution of the degree distribution of alters in growing networks}},
  booktitle = {Netw. Sci},
  year = {2018},
  url = {https://openreview.net/forum?id=MbNxfMSQK0},
}
Figure