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$:
- 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.
- 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.
- 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.
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.
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