A zero-one law for the existence of triangles in random key graphs

Osman Yağan, Armand M. MakowskiarXiv 2009 · DOI · arXiv

Abstract

Random key graphs are random graphs induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. For this class of random graphs we show the existence of a zero-one law for the appearance of triangles, and identify the corresponding critical scaling. This is done by applying the method of first and second moments to the number of triangles in the graph.

Introduction

In the design of secure Wireless Sensor Networks (WSNs), the random key predistribution scheme proposed by Eschenauer and Gligor has become a foundational model. In this setup, each of the $n$ sensor nodes is assigned a set of $K$ cryptographic keys selected uniformly at random from a large pool of $P$ keys. Two nodes can establish a secure communication link if they share at least one key. This mechanism induces a "random key graph" (also known as a uniform random intersection graph).

While extensive research has characterized the conditions required for global connectivity—ensuring the network can function as a whole—local structural properties have remained less understood. This paper investigates the existence of triangles (cliques of size three) within these graphs. Triangles are the most basic unit of network clustering and provide critical insights into the local resilience and redundancy of the communication fabric.

The Random Key Graph Model

The random key graph $G(n, K, P)$ is defined by the parameters $n$ (number of nodes), $K$ (keys per node), and $P$ (total key pool size). The probability that any two nodes share at least one key, denoted as $\alpha$, defines the edge probability.

A common practice in the literature has been the "transfer technique," where researchers approximate the behavior of random key graphs using the simpler Erdős-Rényi (ER) model $G(n, p)$, setting $p = \alpha$. This paper rigorously tests whether this approximation holds for local properties like triangle existence, revealing significant discrepancies between the two models.

Methodology: The First and Second Moment Methods

To establish the zero-one law, the authors employ the method of moments on the random variable $X_n$, representing the number of triangles in a graph of $n$ nodes:

  1. The Zero-Law (First Moment Method): By calculating the expected value $E[X_n]$, the authors show that if the parameters scale such that $E[X_n] \to 0$ as $n \to \infty$, the probability of the graph containing even a single triangle vanishes.
  2. The One-Law (Second Moment Method): This phase is more mathematically intensive. The authors demonstrate that if $E[X_n] \to \infty$, the variance of $X_n$ is sufficiently controlled such that the probability of finding at least one triangle approaches 1.

The analysis focuses on the asymptotic regime where $n$ grows to infinity, identifying a specific scaling function $\tau(\theta)$ that governs this phase transition.

Key Results and the Critical Scaling

The central contribution of the paper is the identification of the critical scaling for triangle existence. The transition is determined by the quantity $n^3 \tau(\theta_n)$, where $\tau$ is a function of the key pool parameters. Specifically, the probability of sharing a key among three nodes involves a term $\tau(\theta) \approx \frac{K^3}{P^2} + (\frac{K^2}{P})^3$.

Theorem 3.1 & 3.2: The Zero-One Law

  • The Zero-Law: If $n^3 \tau(\theta_n) \to 0$, then $\lim_{n \to \infty} P[\text{Graph contains a triangle}] = 0$.
  • The One-Law: If $n^3 \tau(\theta_n) \to \infty$, then $\lim_{n \to \infty} P[\text{Graph contains a triangle}] = 1$.

Discrepancy with Erdős-Rényi Graphs

A pivotal insight of this research is that random key graphs exhibit much higher clustering than ER graphs with the same edge probability. In the ER model, edges are independent coin flips. In the random key model, edges are dependent on shared resources. If Node A shares a specific key with Node B, and Node B shares that same key with Node C, then Node A and Node C are guaranteed to be connected. This "shared resource" logic creates a natural bias toward triangle formation. Consequently, for realistic WSN parameters, the expected number of triangles in a random key graph can be orders of magnitude higher than in an equivalent ER graph.

Discussion and Limitations

This study provides a rigorous mathematical foundation for understanding local structures in intersection-based graphs. However, it operates under the "full visibility" assumption, where any two nodes can connect regardless of physical distance. In actual WSN deployments, physical radio range limits connectivity.

Future research is needed to integrate this key-sharing model with random geometric graphs to account for spatial constraints. Additionally, while this paper solves the problem for triangles, extending these zero-one laws to larger cliques or more complex subgraphs remains an open challenge due to the increasingly complex dependencies between overlapping key sets as the number of nodes increases.

Summary updated

Abstract

Random key graphs are random graphs induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. For this class of random graphs we show the existence of a zero-one law for the appearance of triangles, and identify the corresponding critical scaling. This is done by applying the method of first and second moments to the number of triangles in the graph.
BibTeX
@misc{yagan2009zero,
  author = {Osman Yağan and Armand M. Makowski},
  title = {{A zero-one law for the existence of triangles in random key graphs}},
  year = {2009},
  eprint = {0910.0499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0910.0499},
  howpublished = {arXiv},
}
Figure