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:
- Type-1 nodes: Low-capability nodes that select only 1 neighbor.
- 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.
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))$$
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