Connectivity in Intersecting Random Graphs

This direction is merged into another direction: connectivity phase transition, random graph intersection modeling, k-connectivity resilience. Its last version stays readable and citable here.

Version 1 of 133 papers49 conceptsfrozen 2026-10-04

In a decentralized network, a communication link between two nodes rarely depends on a single factor. For a sensor to talk to a neighbor, it must be physically close enough to transmit a signal, the wireless channel must be free of interference, and—in secure systems—both nodes must share the correct cryptographic keys.

Traditional network analysis often treats these constraints in isolation, using Erdős-Rényi graphs for random connections or Random Geometric Graphs for spatial proximity. However, a significant body of research led by Armand M. Makowski, Virgil D. Gligor, and Osman Yagan demonstrates that the true behavior of these networks emerges only when we model them as the intersection of multiple random graphs.

The Logic of Dual Constraints

The core intuition is that a functional edge exists if and only if multiple independent conditions are satisfied simultaneously. In the context of Wireless Sensor Networks (WSNs), this is often framed as the intersection of a Random Key Graph (representing security) and a Physical Link Graph (representing the environment).

As Armand M. Makowski explains in Modeling the Pairwise Key Predistribution Scheme in the Presence of Unreliable Links, if the probability of two nodes sharing a key is $p_{key}$ and the probability of a reliable physical channel is $p_{channel}$, the overall probability of a secure link is the product $p_{key} \times p_{channel}$. While this seems simple, the structural consequences are profound: the physical layer "thins" the logical layer, shifting the critical thresholds required for the entire network to function.

Zero-One Laws and Phase Transitions

One of the most striking features of these composite models is the existence of "zero-one laws." These are mathematical tipping points where a tiny change in a parameter—like the number of keys stored on a sensor—causes the network to transition instantly from being completely disconnected to being almost certainly connected.

Rashad Eletreby and Osman Yagan have extended these laws to heterogeneous networks where nodes have different resource levels. In $k$-connectivity of inhomogeneous random key graphs with unreliable links, they provide the "recipe" for scaling these networks. They show that to maintain connectivity as a network grows, the number of keys per node must scale logarithmically with the total number of nodes, adjusted for the unreliability of the physical links.

Resilience through k-Connectivity

For a network to be truly robust, it must stay connected even when some nodes fail or are compromised. This is known as $k$-connectivity—the ability of a graph to remain connected after the removal of any $k-1$ nodes.

Jun Zhao and Virgil D. Gligor established in Exact Analysis of k-Connectivity in Secure Sensor Networks with Unreliable Links that in these intersecting models, the property of $k$-connectivity is asymptotically equivalent to the property of every node simply having at least $k$ neighbors. This simplifies the engineering challenge: if you can guarantee a minimum degree for each node through your key distribution and power settings, you automatically gain global network resilience.

Expanding the Intersection Framework

The power of the intersecting graph approach is its versatility. It is not limited to cryptographic keys and radio waves:

By treating connectivity as the intersection of independent constraint layers, this research direction provides a rigorous way to predict the behavior of complex, decentralized systems where "being connected" is a multi-faceted requirement.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_connectivity_in_intersecting_random_grap_4722bb1d,
  title = {Connectivity in Intersecting Random Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/connectivity-in-intersecting-random-graphs/rdr_4722bb1dc9854280a095fc8d448e849f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_connectivity_in_intersecting_random_grap_4722bb1d_v1,
  title = {Connectivity in Intersecting Random Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/connectivity-in-intersecting-random-graphs/rdr_4722bb1dc9854280a095fc8d448e849f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}