Local Clustering Coefficient in Generalized Preferential Attachment Models

Alexander M. Krot, Liudmila Ostroumova Prokhorenkova

TL;DR

This paper analyzes the local clustering coefficient in a broad class of preferential attachment network models. The authors derive a precise formula for how this coefficient scales with vertex degree, showing it generally decreases as $d^{-1}$, and provide empirical evidence supporting their theoretical findings. This work offers a deeper understanding of the structural properties of complex networks generated by these popular models.

What Problem Does This Paper Address?

Real-world networks, from social connections to biological systems, often exhibit specific structural properties like small diameters, power-law degree distributions, and high clustering. While the power-law degree distribution has been extensively studied, the behavior of the clustering coefficient, particularly the local clustering coefficient for vertices of a given degree, is less understood for generalized models. This paper aims to fill this gap by providing a theoretical framework and empirical validation for the local clustering coefficient in a flexible class of preferential attachment models (the PA-class and its T-subclass). Understanding this coefficient is crucial for accurately modeling and predicting the behavior of complex networks.

Methods

The authors build upon a generalized framework for preferential attachment models (PA-class) introduced in prior work. They focus on the T-subclass, which includes an additional condition related to triangle formation. Their core methodology involves:

  • Theoretical Analysis: They derive asymptotic formulas for the expected number of triangles ($ET_n(d)$) and the number of vertices of a given degree ($N_n(d)$) for vertices of degree $d$.
  • Concentration Inequalities: They employ Azuma-Hoeffding inequality to show that the number of triangles is highly concentrated around its expectation.
  • Derivation of C(d): By combining the results for $ET_n(d)$ and $N_n(d)$, they derive the asymptotic behavior of the average local clustering coefficient for vertices of degree $d$, denoted as $C(d)$.
  • Approximation of C₂(n): They propose and empirically verify an approximation for the average local clustering coefficient across the entire network, $C_2(n)$.
  • Empirical Validation: They generate synthetic networks based on the PA-class models and compare the theoretical predictions for $C(d)$ and $C_2(n)$ with experimental results.

Datasets

Not discussed in the paper. The authors generate synthetic networks based on the described PA-class models for their experiments.

Key Insights and Ideas

  • Universal $d^{-1}$ Scaling: A key finding is that for a broad class of preferential attachment models (the T-subclass), the average local clustering coefficient for vertices of degree $d$ asymptotically scales as $C(d) \sim d^{-1}$. This suggests a fundamental structural property that is not easily tunable by varying model parameters like $A$, $D$, and $m$.
  • Limitations of Modeling: The $d^{-1}$ scaling implies that these models might not be flexible enough to capture networks where the local clustering coefficient follows a different power-law exponent (i.e., $C(d) \sim d^{-\zeta}$ with $\zeta \neq 1$).
  • Approximation for Global Clustering: The paper provides an approximation for the average local clustering coefficient $C_2(n)$, which is shown to be empirically accurate for certain parameter ranges ($A < 0.75$).
  • Parameter Dependence: The behavior of $C(d)$ and $C_2(n)$ is shown to be dependent on model parameters, particularly $A$ and $D$, with the restriction $A < 1$ being crucial for theoretical guarantees.

Key Results

  • Theorem 6: For the T-subclass of PA models, the average local clustering coefficient for vertices of degree $d$ asymptotically behaves as $C(d) \sim \frac{2D}{m} d^{-1}$ for $2A \le 1$. For $2A > 1$, the behavior is more complex but still shows a power-law decay.
  • Empirical Validation: Figures 1 and 2 demonstrate that the theoretical predictions for $C(d)$ and $C_2(n)$ align well with experimental results for parameter values where theoretical proofs exist ($A \le 0.75$).
  • Approximation for $C_2(n)$: The paper derives an analytical expression for the expectation of $C_2(n)$ and shows it is a good approximation for the average local clustering coefficient in generated networks.

Limitations and Future Work

  • Parameter Restriction: The theoretical analysis for $C(d)$ is primarily valid for $A < 1$. The authors note that for $A > 1$, error terms can become significant, and obtaining accurate approximations might require additional constraints or more refined techniques.
  • Technical Gaps: The paper mentions that the restriction $A < 1$ for Theorem 5 might be technical, suggesting that more precise error term estimations could potentially extend the results.
  • Flexibility of Models: The fixed $d^{-1}$ scaling for $C(d)$ suggests limitations in modeling networks with diverse local clustering behaviors.
  • Future Work: The authors suggest that further investigation into the behavior of $C(d)$ for $A > 1$ is needed. They also hint at a connection between their findings and the concepts of weak and strong transitivity in networks, which could be a direction for future research.

Summary updated

Abstract

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