Joint Vertex Degrees in an Inhomogeneous Random Graph Model

Kaisheng Lin, Gesine ReinertarXiv 2009 · DOI · arXiv

Abstract

In a random graph, counts for the number of vertices with given degrees will typically be dependent. We show via a multivariate normal and a Poisson process approximation that, for graphs which have independent edges, with a possibly inhomogeneous distribution, only when the degrees are large can we reasonably approximate the joint counts as independent. The proofs are based on Stein's method and the Stein-Chen method with a new size-biased coupling for such inhomogeneous random graphs, and hence bounds on distributional distance are obtained. Finally, we illustrate that apparent (pseudo-) power-law type behaviour can arise in such inhomogeneous networks despite not actually following a power-law degree distribution.

Introduction

In the study of complex networks, the degree distribution—the frequency of vertices with a specific number of connections—is often treated as a primary diagnostic tool. A common assumption in network analysis is that the number of vertices with degree $k$ is independent of the number of vertices with degree $j$. However, this assumption is mathematically fragile. In any finite graph, the existence of an edge between two nodes necessarily constrains the potential connections available to others.

This paper by K. Lin and G. Reinert provides a rigorous mathematical framework to address these dependencies. By focusing on inhomogeneous random graphs—where edge probabilities vary between specific pairs of nodes—the authors demonstrate that vertex degree counts are inherently dependent, only approaching independence in the extreme tails of the distribution.

The Problem: The Myth of Independence

Most mathematical models of networks simplify the degree distribution by assuming independence between counts. In reality, because a graph has a fixed number of vertices and edges, these counts are coupled. If one vertex acts as a high-degree hub, it "consumes" potential edges, affecting the probability of other vertices achieving specific degrees. This correlation is particularly pronounced between adjacent degrees ($k$ and $k+1$).

The authors investigate this phenomenon in inhomogeneous random graphs, a class of models where the probability of an edge $p_{ij}$ between vertices $i$ and $j$ is not constant. This captures the reality of many systems where nodes have different "attractiveness" or latent traits, moving beyond the simpler Erdős-Rényi models.

Methodology: Stein’s Method and Size-Biased Coupling

To quantify the distance between the actual distribution of degree counts and idealized distributions (like the Normal or Poisson), the authors employ Stein’s Method and the Stein-Chen Method. These techniques allow for the derivation of explicit error bounds, providing a measure of how accurate an approximation is for a graph of size $n$.

The technical cornerstone of the paper is a new size-biased coupling construction specifically designed for inhomogeneous random graphs. Coupling involves constructing two different random variables on the same probability space to compare them directly. This specific construction allows the authors to handle the inhomogeneity of the edges, leading to two primary approximation regimes:

  1. Multivariate Normal Approximation: Used for "typical" degrees (those near the mean), where the joint distribution of counts is modeled using a normal distribution with a specific covariance matrix.
  2. Poisson Process Approximation: Used for "large" degrees (the rare hubs), where the dependencies weaken enough that the counts begin to behave as independent Poisson variables.

Experimental Models

The theoretical results were tested against four simulated graph models (M1–M4) representing different types of inhomogeneity:

  • M1: A standard Bernoulli (Erdős-Rényi) graph at the critical threshold.
  • M2: A modified Newman-Moore-Watts small-world model.
  • M3: A model where edge probability depends on the indices of the vertices ($p_{ij} \propto \min(i, j)$).
  • M4: A Rasch-type model, frequently used in psychometrics to model latent traits.

Key Insights

The Power Law Mirage

Perhaps the most significant finding for applied network science is the emergence of "pseudo-power-law" behavior. Many researchers identify "scale-free" networks by plotting the cumulative degree distribution on a log-log scale and looking for a straight line. The authors show that inhomogeneous models with independent edges—which do not follow a power law by definition—can produce log-log plots that appear remarkably linear. This suggests that visual heuristics for identifying power laws can be highly misleading, as the observed linearity may simply be an artifact of the underlying inhomogeneity rather than a true scale-free architecture.

Asymptotic Independence

The research clarifies that independence is an emergent property. While low-to-mid degree counts are highly correlated, these correlations decay as one moves toward the high-degree "hubs." This justifies the use of Poisson approximations for the tails of the distribution, even when a Normal approximation is required for the bulk of the data.

Rigorous Error Bounds

Theorems 3.1 and 3.6 in the paper provide formal bounds for these approximations. The error typically decreases at a rate of $n^{-1/2}$ as the number of vertices $n$ increases. This provides researchers with a mathematical "safety margin" when applying these approximations to finite datasets, moving beyond the qualitative "it looks like a normal distribution" approach.

Limitations and Future Directions

While the paper advances the understanding of joint degree distributions, several avenues for future work remain:

  • Smoothness of Test Functions: The current bounds are optimized for "smooth" functions. Extending these to the non-smooth functions often used in discrete counting remains a challenge.
  • Edge Dependence: The model assumes edges are independent. In many real-world social networks, edges exhibit "transitivity" (the friend-of-a-friend effect). Incorporating these higher-order dependencies would be a significant next step.
  • Graph Density: The tightness of the bounds in extremely sparse or extremely dense regimes requires further refinement to ensure accuracy across all types of inhomogeneous networks.

Conclusion

Lin and Reinert’s work serves as a vital bridge between theoretical probability and practical network analysis. By proving that degree dependencies only vanish in the extreme tails and demonstrating how easily "power laws" can be mimicked by simple inhomogeneous processes, the paper advocates for a more rigorous, bound-based approach to network characterization.

Summary updated

Abstract

In a random graph, counts for the number of vertices with given degrees will typically be dependent. We show via a multivariate normal and a Poisson process approximation that, for graphs which have independent edges, with a possibly inhomogeneous distribution, only when the degrees are large can we reasonably approximate the joint counts as independent. The proofs are based on Stein's method and the Stein-Chen method with a new size-biased coupling for such inhomogeneous random graphs, and hence bounds on distributional distance are obtained. Finally we illustrate that apparent (pseudo-) power-law type behaviour can arise in such inhomogeneous networks despite not actually following a power-law degree distribution.
BibTeX
@misc{lin2009joint,
  author = {Kaisheng Lin and Gesine Reinert},
  title = {{Joint Vertex Degrees in an Inhomogeneous Random Graph Model}},
  year = {2009},
  eprint = {0912.4812},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0912.4812},
}
Figure