Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure

Krzysztof Choromański, Michał Matuszak, Jacek MiȩkiszJournal of Statistical Physics 2013 · DOI

Abstract

We extend the classical Barabási-Albert preferential attachment procedure to graphs with internal vertex structure given by weights of vertices. In our model, weight dynamics depends on the current vertex degree distribution and the preferential attachment procedure takes into account both weights and degrees of vertices. We prove that such a coupled dynamics leads to scale-free graphs with exponents depending on parameters of the weight dynamics.

Introduction

The classical Barabási-Albert (BA) model is a cornerstone of network science, explaining the "rich-get-richer" phenomenon that leads to a power-law degree distribution $P(k) \sim k^{-3}$. However, real-world systems—such as social networks or citation indices—often feature nodes whose "fitness" or intrinsic value is not static but evolves through interaction with the system.

While previous extensions of the BA model introduced fitness parameters, these were typically static assignments at a node's birth. This research addresses the gap of coupled dynamics, exploring how a network evolves when graph topology and the internal states (weights) of vertices influence each other simultaneously.

Methodology

The authors propose a discrete-time dynamical model characterized by two alternating substeps:

  1. Graph Growth (Preferential Attachment): A new vertex is added with an initial weight $w_1$. It connects to an existing vertex $i$ with a probability proportional to the product of that vertex's current degree ($k_i$) and its current weight ($w_i$). If no vertex is selected, the new vertex connects to itself.
  2. Weight Mutation: An existing vertex is chosen with probability proportional to its degree. Its weight is then reassigned to $w_1$ or $w_2$ based on a probability distribution (where $w_1 + w_2 = 1$).

To analyze this system, the authors moved beyond standard one-dimensional recurrence relations, employing a two-dimensional system of linear equations to track the expected number of vertices for each weight-degree combination. The asymptotic behavior of the degree distribution was rigorously derived using the Stolz theorem and inductive proofs. Analytical findings were validated using stochastic simulations of synthetic networks with up to $10^9$ vertices.

Key Results

The central contribution of this work is the analytical derivation of the power-law exponent $\beta$ as a function of the weight parameter $w_1$:

$$\beta(w_1) = \frac{2w_1^2 - 2w_1 + 3}{2w_1^2 - 2w_1 + 1}$$

As shown in Figure 1, the model demonstrates several critical properties:

  • Classical Limit: When $w_1 = 1$ (effectively a single-weight state), the model recovers the standard Barabási-Albert result of $\beta = 3$.
  • Maximum Steepness: The exponent reaches a maximum of $\beta = 5$ at the point of maximum internal state diversity, $w_1 = 0.5$.
  • Symmetry: The exponent $\beta$ is symmetric around $w_1 = 0.5$, suggesting that the balance of internal states, rather than their specific values, drives the final topology.
Analytical and simulated values of the power-law exponent $\beta$ as a function of weight $w_1$.

The authors rigorously proved that for any $w_1 \in (0, 1]$, the resulting graph remains scale-free. Notably, simulations highlighted finite-size effects; while theory predicts $\beta=5$ for $w_1=0.5$, simulations at $10^9$ nodes reached $\beta \approx 4.92$, with an estimated $10^{12}$ nodes required to reach the true asymptotic limit.

Discussion and Conclusion

This model demonstrates that dynamic fitness creates a feedback loop that allows networks to reach scale-free states unattainable by the standard BA model. Despite the complexity of evolving weights, the system remains analytically tractable, providing a closed-form solution for a coupled-dynamics growth model.

Future work could generalize this 2D recurrence method to models with continuous weight distributions or more complex internal dynamics. Such extensions could improve our understanding of co-evolutionary processes in fields like evolutionary game theory, where node strategies and network structure evolve in tandem.

Summary updated

Abstract

We extend the classical Barabási-Albert preferential attachment procedure to graphs with internal vertex structure given by weights of vertices. In our model, weight dynamics depends on the current vertex degree distribution and the preferential attachment procedure takes into account both weights and degrees of vertices. We prove that such a coupled dynamics leads to scale-free graphs with exponents depending on parameters of the weight dynamics.
BibTeX
@article{choromanski2013scale,
  author = {Krzysztof Choromański and Michał Matuszak and Jacek Miȩkisz},
  title = {{Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure}},
  journal = {Journal of Statistical Physics},
  year = {2013},
  doi = {10.1007/s10955-013-0749-1},
}
Figure