Local Clustering Coefficient in Generalized Preferential Attachment\n Models

Alexander N. Krot, Liudmila Prokhorenkova

TL;DR

This paper mathematically proves that for a broad class of generalized preferential attachment models, the local clustering coefficient $C(d)$—the probability that a node's neighbors are connected—always scales inversely with its degree ($d^{-1}$). This reveals a fundamental "rigidity" in these models, showing they cannot easily replicate the diverse clustering patterns observed in many real-world networks.

What Problem Does This Paper Address?

Real-world networks, from the structure of the Internet to social circles and protein interactions, often share three "stylized facts": they have a small diameter (the "six degrees of separation"), their degrees follow a power law (a few hubs have many connections), and they exhibit high clustering.

The "Preferential Attachment" (PA) mechanism—the idea that "the rich get richer" as new nodes join a network—is the standard tool for explaining power-law degree distributions. However, modeling clustering accurately has been more difficult. Specifically, researchers look at the local clustering coefficient $C(d)$, which measures how "cliquey" the neighbors of a node with degree $d$ are. In many real networks, this follows a power law $C(d) \sim d^{-\psi}$.

While previous work defined a broad "PA-class" of models that successfully capture degree distributions, it wasn't clear if these models were flexible enough to capture different values of the clustering exponent $\psi$. This paper sets out to prove exactly how $C(d)$ behaves across this entire class of models.

Methods

The authors employ a rigorous theoretical approach combined with numerical simulations:

  1. Theoretical Framework: They analyze the "T-subclass" of generalized PA models. This subclass is defined by a set of probabilistic constraints on how new edges are added and how triangles (the building blocks of clustering) are formed.
  2. Inductive Proofs: They use induction on both the number of vertices ($n$) and the degree ($d$) to calculate the expected number of triangles.
  3. Martingale Analysis: To move beyond simple averages, they use the Azuma-Hoeffding inequality. This allows them to prove "concentration"—showing that in a large network, the actual clustering coefficient of almost any node will be very close to the calculated theoretical average, rather than fluctuating wildly.
  4. Simulation: They verify their proofs using "polynomial graph models," a specific implementation of the PA-class, generating networks with 1 million nodes to compare experimental data against their theoretical predictions.

Datasets

The paper does not use real-world datasets. Instead, it relies on synthetic datasets generated through computer simulations of the random graph models described in the theory. They generated multiple polynomial graphs with $n = 10^6$ vertices, varying parameters like $A$ (which controls the degree distribution) and $D$ (which controls triangle formation).

Key Insights and Ideas

  • The "Universal" Exponent: The most significant finding is that for the entire T-subclass of models, the clustering exponent $\psi$ is fixed at 1. No matter how you tweak the parameters for attachment or triangle formation, $C(d)$ will always behave like $1/d$.
  • Model Inflexibility: This is a bit of a "negative" result for the field, but a very important one. It suggests that standard preferential attachment models are "not flexible enough." If you encounter a real-world network where clustering decays as $d^{-0.5}$ or $d^{-2}$, a standard PA model simply cannot represent it accurately.
  • Weak vs. Strong Transitivity: The authors link their results to the concept of transitivity. They show that depending on the ratio of triangle formation to edge attachment ($2D$ vs $Am$), a model can fall into a "weak" or "strong" transitivity class, which fundamentally changes how information or diseases might spread (percolate) through the network.

Key Results

  • Asymptotic Behavior: The authors proved that as the degree $d$ becomes large, the local clustering coefficient behaves as: $$C(d) \sim \frac{2D}{mA} \cdot d^{-1}$$ where $D, m,$ and $A$ are model parameters.

  • High Concentration: They proved that the number of triangles on vertices of degree $d$ is highly concentrated around the expectation, making the $d^{-1}$ scaling a robust property of the model.

  • Empirical Match: Simulations for various values of $A$ (0.25, 0.5, 0.7) showed an almost perfect overlap between the theoretical $d^{-1}$ curve and the experimental data.

Limitations and Future Work

  • The $A < 3/4$ Boundary: The mathematical proofs for concentration are only "informative" when the parameter $A$ is less than 0.75. When $A$ is higher (meaning the degree distribution has a very heavy tail), the error terms in the math become significant. While simulations suggest the $d^{-1}$ behavior might still hold, the current proof doesn't strictly cover it.
  • Need for New Models: Since this paper proves PA models are stuck with a clustering exponent of -1, the authors suggest that future research needs to find new ways to generalize these models—perhaps by adding more complex constraints—to allow for a tunable clustering exponent that can match the diversity of the real world.

Summary updated

Abstract

In this paper, we analyze the local clustering coefficient of preferential\nattachment models. A general approach to preferential attachment was introduced\nin earlier, where a wide class of models (PA-class) was defined in terms of\nconstraints that are sufficient for the study of the degree distribution and\nthe clustering coefficient. It was previously shown that the degree\ndistribution in all models of the PA-class follows a power law. Also, the\nglobal clustering coefficient was analyzed and a lower bound for the average\nlocal clustering coefficient was obtained. We expand the results by analyzing\nthe local clustering coefficient for the PA-class of models. Namely, we analyze\nthe behavior of C(d) which is the average local clustering for the vertices of\ndegree d.\n
BibTeX
@inproceedings{krot2015local,
  author = {Alexander N. Krot and Liudmila Prokhorenkova},
  title = {{Local Clustering Coefficient in Generalized Preferential Attachment\textbackslash\{\}n Models}},
  booktitle = {Internet Math},
  year = {2015},
  url = {https://openreview.net/forum?id=1qxGhj5jne},
}

Loading related content...

Figure