On the Strength of Connectivity of Inhomogeneous Random K-out Graphs

Mansi Sood, Osman Yağan

Abstract

Random graphs are an important tool for modelling and analyzing the underlying properties of complex real-world networks. In this paper, we study a class of random graphs known as the inhomogeneous random K-out graphs which were recently introduced to analyze heterogeneous sensor networks secured by the pairwise scheme. In this model, first, each of the $n$ nodes is classified as type-1 (respectively, type-2) with probability $0<\mu<1$ (respectively, $1-\mu)$ independently from each other. Next, each type-1 (respectively, type-2) node draws 1 arc towards a node (respectively, $K_n$ arcs towards $K_n$ distinct nodes) selected uniformly at random, and then the orientation of the arcs is ignored. From the literature on homogeneous K-out graphs wherein all nodes select $K_n$ neighbors (i.e., $\mu=0$), it is known that when $K_n \geq 2$, the graph is $K_n$-connected asymptotically almost surely (a.a.s.) as $n$ gets large. In the inhomogeneous case (i.e., $\mu>0$), it was recently established that achieving even 1-connectivity a.a.s. requires $K_n=\omega(1)$. Here, we provide a comprehensive set of results to complement these existing results. First, we establish a sharp zero-one law for $k$-connectivity, showing that for the network to be $k$-connected a.a.s., we need to set $K_n = \frac{1}{1-\mu}(\log n +(k-2)\log\log n + \omega(1))$ for all $k=2, 3, \ldots$. Despite such large scaling of $K_n$ being required for $k$-connectivity, we show that the trivial condition of $K_n \geq 2$ for all $n$ is sufficient to ensure that inhomogeneous K-out graph has a connected component of size $n-O(1)$ whp.

Introduction

In network science, random graphs serve as fundamental models for complex systems ranging from social networks to wireless sensor networks (WSNs). A standard model is the K-out graph, where each node selects exactly $K$ neighbors at random. However, real-world networks are rarely uniform; they often consist of a few high-capacity base stations and many resource-constrained sensors. This paper investigates the inhomogeneous random K-out graph, a model designed to capture such disparities in node capabilities.

The Inhomogeneous K-out Model

The model distinguishes between two types of nodes:

  1. Type-1 nodes: Low-capability nodes that select only 1 neighbor.
  2. Type-2 nodes: Higher-capability nodes that select $K_n$ neighbors.

Each node is assigned a type independently with probability $\mu$ for Type-1 and $1-\mu$ for Type-2. After nodes make their selections, the directed arcs are treated as undirected edges to form the final graph.

Illustration of the construction of an inhomogeneous random K-out graph, where nodes pick different numbers of neighbors.

Robustness and the "Logarithmic Gap"

A critical property of any network is its robustness, often measured by $k$-connectivity—the ability of the network to remain connected despite the failure of any $k-1$ nodes or links. In homogeneous K-out graphs ($\mu=0$), $K_n \ge 2$ is sufficient for $K_n$-connectivity.

In the inhomogeneous case ($\mu > 0$), the authors discover a "logarithmic gap." While simple 1-connectivity is relatively easy to achieve ($K_n = \omega(1)$), ensuring 2-connectivity or higher requires $K_n$ to scale logarithmically with the total number of nodes $n$. Specifically, the Type-1 nodes act as a bottleneck, forcing Type-2 nodes to significantly increase their connection degree to maintain overall network robustness.

Key Results: Zero-One Laws and the Giant Component

The authors establish a sharp zero-one law for $k$-connectivity. For the network to be $k$-connected asymptotically almost surely (a.a.s.), the required scaling for $K_n$ is: $$K_n = \frac{1}{1-\mu}(\log n + (k-2)\log \log n + \omega(1))$$

Empirical results showing the probability of k-connectivity and the maximum k achieved as a function of Kn and mu.

Despite the high requirement for full $k$-connectivity, the paper proves a remarkably positive result regarding the network's "giant component." If $K_n \ge 2$, the probability that more than $M$ nodes are outside the giant component decays exponentially with $M$. Specifically, the largest component contains $n - O(1)$ nodes with high probability. This theoretical finding aligns with observations in real-world networks like the Bitcoin Lightning Network, where nearly all nodes belong to one giant component.

Conclusion and Future Directions

This work provides a "lookup table" for network designers: given a proportion of low-power nodes $\mu$, one can determine the necessary $K_n$ for a target level of fault tolerance. Future research may extend this model to include a continuous spectrum of node types or further investigate the specific case where $K_n=1$ for all nodes, which remains an open question in terms of component size distribution.

Summary updated

Abstract

Random graphs are an important tool for modelling and analyzing the underlying properties of complex real-world networks. In this paper, we study a class of random graphs known as the inhomogeneous random K-out graphs which were recently introduced to analyze heterogeneous sensor networks secured by the pairwise scheme. In this model, first, each of the $n$ nodes is classified as type-1 (respectively, type-2) with probability $0&lt;μ&lt;1$ (respectively, $1-μ)$ independently from each other. Next, each type-1 (respectively, type-2) node draws 1 arc towards a node (respectively, $K_n$ arcs towards $K_n$ distinct nodes) selected uniformly at random, and then the orientation of the arcs is ignored. From the literature on homogeneous K-out graphs wherein all nodes select $K_n$ neighbors (i.e., $μ=0$), it is known that when $K_n \geq2$, the graph is $K_n$-connected asymptotically almost surely (a.a.s.) as $n$ gets large. In the inhomogeneous case (i.e., $μ&gt;0$), it was recently established that achieving even 1-connectivity a.a.s. requires $K_n=ω(1)$. Here, we provide a comprehensive set of results to complement these existing results. First, we establish a sharp zero-one law for $k$-connectivity, showing that for the network to be $k$-connected a.a.s., we need to set $K_n = \frac{1}{1-μ}(\log n +(k-2)\log\log n + ω(1))$ for all $k=2, 3, \ldots$. Despite such large scaling of $K_n$ being required for $k$-connectivity, we show that the trivial condition of $K_n \geq 2$ for all $n$ is sufficient to ensure that inhomogeneous K-out graph has a connected component of size $n-O(1)$ whp.
BibTeX
@misc{sood2019strength,
  author = {Mansi Sood and Osman Yağan},
  title = {{On the Strength of Connectivity of Inhomogeneous Random K-out Graphs}},
  year = {2019},
  eprint = {1911.05147},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.05147},
}
Figure