Abstract
In this article, we study the clustering properties of the spatial preferential attachment (SPA) model. This model naturally combines geometry and preferential attachment using the notion of spheres of influence. While previous research has shown that graphs generated by the SPA model are similar to real-world networks in many aspects, their clustering properties were not fully analyzed. We study the behavior of $C(d)$, the average local clustering coefficient for vertices of degree $d$. We prove that in the SPA model, $C(d)$ decreases as $1/d$, matching empirical observations in real-world networks. Furthermore, we prove that the individual local clustering coefficient of a vertex $v$ of degree $d$ behaves as $1/d$ for sufficiently large $d$. The obtained results further confirm the suitability of the SPA model for fitting various real-world complex networks.
Introduction
In the study of complex networks—ranging from social media platforms like Facebook to biological protein-interaction webs—two structural properties typically stand out. First, "preferential attachment" (the "rich get richer" effect) suggests that popular nodes attract more new connections. Second, "geometry" implies that nodes close to each other in a physical or conceptual space are more likely to link. The Spatial Preferential Attachment (SPA) model was developed to synthesize these two drivers. While it successfully produces realistic power-law degree distributions, its ability to model "cliquishness" or clustering remained a subject of theoretical investigation.
The Spatial Preferential Attachment (SPA) Model
The SPA model places vertices in a multi-dimensional unit cube. Each vertex $v$ is assigned a "sphere of influence" whose volume grows as the vertex gains more incoming links. When a new vertex enters the system, it connects to an existing vertex $v$ with probability $p$ if it falls within $v$'s current sphere of influence.
This geometric approach ensures that nodes are more likely to connect to neighbors that are "close" in the underlying space, naturally leading to the formation of communities and high local clustering, as seen in the visualization above.
Methodology and Mathematical Framework
To rigorously prove the $1/d$ scaling behavior, the authors employed several advanced probabilistic techniques:
- Neighbor Partitioning: A node's neighbors are split into "old" (early, high-variance connections) and "young" (later, more stable connections) sets. This allows for the management of the "chaotic" early growth phase of a node.
- Concentration Inequalities: Using Chernoff bounds and the supermartingale method, the researchers demonstrated that as the network size $n$ approaches infinity, the actual clustering values remain tightly concentrated around their theoretical expectations.
- Differential Equations: The evolution of node degrees over time was tracked using differential equations, providing a deterministic framework for the expected growth of the network.
Key Insights: The $1/d$ Scaling Law
The primary contribution of this work is the formal proof that the average local clustering coefficient $C(d)$ behaves as $\Theta(1/d)$. This is a significant finding because in pure preferential attachment models (such as the Barabási-Albert model), clustering often vanishes as the network grows. By incorporating geometry, the SPA model maintains a realistic level of local clustering.
Crucially, the authors showed that this $1/d$ behavior is not merely an average across the entire graph but holds for individual vertices once they reach a "mature" state (typically when they have acquired roughly $\log n$ neighbors). At this point, the future growth and clustering behavior of the node become highly predictable.
Results and Discussion
The theoretical proofs were validated through extensive simulations of SPA graphs with up to $1,000,000$ vertices. The resulting log-log plots showed a near-perfect straight line with a slope of -1, confirming the $1/d$ scaling across six orders of magnitude. The results were robust across various link probabilities ($p$) and model constants.
While the paper establishes the $1/d$ rate of decay, it leaves the calculation of the precise constant $C$ (where $C(d) \approx C/d$) for future work. Additionally, while many real-world networks follow the $1/d$ law, some exhibit different exponents. Future iterations of the SPA model might modify the "sphere of influence" growth rules to allow for more flexible scaling exponents, further enhancing its utility for fitting diverse complex systems.
Conclusion
By proving that the SPA model naturally produces the $1/d$ clustering signature found in real-world data, this research solidifies the model's position as a premier tool for network simulation. The integration of geometry and preferential attachment provides a mathematically sound mirror of the complex social and physical forces that shape our interconnected world.
Summary updated