EVOLVING SCALE-FREE NETWORK MODEL WITH TUNABLE CLUSTERING

Bing Wang, Huanwen Tang, Zhongzhi Zhang, Zhilong XiuInternational Journal of Modern Physics B 2005 · DOI · arXiv

Abstract

The Barabási–Albert (BA) model is extended to include the concept of local world and the microscopic event of adding edges. With probability $p$, we add a new node with $m$ edges which preferentially link to the nodes presented in the network; with probability $1-p$, we add $m$ edges among the present nodes. A node is preferentially selected by its degree to add an edge randomly among its neighbors. Using the continuum theory and the rate equation method, we get the analytical expressions of the power-law degree distribution with exponent $\gamma=3$ and the clustering coefficient $c(k) \sim k^{-1} + c$. The analytical expressions are in good agreement with the numerical calculations.

Introduction

In the late 1990s, the Barabási–Albert (BA) model revolutionized network science by explaining the emergence of "scale-free" networks—systems like the Internet where a few "hubs" have many connections while most nodes have few. However, the BA model has a significant limitation when applied to social networks: it produces very low "clustering." In real social networks, if Person A knows Person B and Person C, there is a high probability that B and C also know each other (forming a triangle). This paper, published in the International Journal of Modern Physics B, addresses this gap by introducing a mechanism that captures this defining feature of human society: the tendency for our friends to know each other.

Methodology

The authors propose a two-part evolving algorithm governed by a probability parameter, $p$:

  1. Local World Selection: When a new node enters the network, it doesn't "see" the entire system. Instead, it picks a random subset of $M$ nodes (a "local community") to potentially connect with.
  2. Probabilistic Events:
    • With probability $p$ (Node Addition): A new node is added with $m$ edges. These edges are attached to nodes within its "local world" based on preferential attachment.
  3. With probability $1-p$ (Edge Addition): No new node is added. Instead, $m$ new edges are created between existing nodes. A node is selected based on its popularity, and it then "introduces" two of its neighbors to each other, creating a triangle.

The researchers used continuum theory and the rate equation method to derive analytical expressions for the network's properties, which they then verified through numerical simulations (typically $N = 10,000$ nodes).

Key Results and Insights

The model successfully maintains the scale-free nature of the BA model while allowing for tunable clustering. The parameter $p$ acts as a "tuning knob"; decreasing $p$ increases the frequency of internal edge creation (triad formation), boosting the clustering coefficient without destroying the power-law degree distribution.

Figure 1: Numerical simulation (stars) vs. analytical prediction (line) for the power-law degree distribution p(k) on a log-log scale.

As shown in Figure 1, the analytical result $p(k) \sim 2m^2 / k^3$ was confirmed, showing the model successfully retains the BA model's universal scaling with an exponent of $\gamma = 3$.

Furthermore, the model predicts that the clustering coefficient $c(k)$ follows a $k^{-1}$ relationship. This means that highly connected "hubs" are actually less clustered than small, tight-knit groups—a phenomenon frequently observed in empirical social data.

Figure 6: Clustering coefficient c(k) as a function of degree k, showing the decay predicted by the analytical model.

As seen in Figure 6, the simulation data perfectly tracks the analytical predictions for clustering. This proves that the "local world" and "edge addition" mechanisms are mathematically sound and predictable.

Conclusion

While this model represents a significant step forward, it has limitations. The "local world" is currently selected at random, whereas real-world communities are often structured by geography or interests. Additionally, the model only accounts for growth and does not yet incorporate node deletion. Nevertheless, it provides a robust framework for understanding how local interactions and global popularity combine to shape the architecture of our social world.

Summary updated

Abstract

The Barabási–Albert (BA) model is extended to include the concept of local world and the microscopic event of adding edges. With probability p, we add a new node with m edges which preferentially link to the nodes presented in the network; with probability 1-p, we add m edges among the present nodes. A node is preferentially selected by its degree to add an edge randomly among its neighbors. Using the continuum theory and the rate equation method we get the analytical expressions of the power-law degree distribution with exponent γ=3 and the clustering coefficient c(k)~k -1 +c. The analytical expressions are in good agreement with the numerical calculations.
BibTeX
@article{wang2005evolving,
  author = {Bing Wang and Huanwen Tang and Zhongzhi Zhang and Zhilong Xiu},
  title = {{EVOLVING SCALE-FREE NETWORK MODEL WITH TUNABLE CLUSTERING}},
  journal = {International Journal of Modern Physics B},
  year = {2005},
  doi = {10.1142/s0217979205032437},
}
Figure