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 \geq2$, 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
Most classical random graph models assume homogeneity, where every node behaves identically. However, real-world networks—such as Wireless Sensor Networks (WSNs) or the Bitcoin Lightning Network—are inherently heterogeneous. For instance, in the Lightning Network as of late 2018, out of 2,273 nodes, 2,266 belonged to a single giant component, despite a highly skewed distribution of node capacities. This paper addresses the "strength" of connectivity in such systems, specifically focusing on $k$-connectivity: the ability of a network to remain connected even after the removal of $k-1$ nodes or links.
The Inhomogeneous Random K-out Graph Model
The inhomogeneous random K-out graph models heterogeneity by dividing $n$ nodes into two types:
- Type-1: Low-capability nodes that choose only 1 neighbor.
- Type-2: High-capability nodes that choose $K_n$ neighbors.
The graph is formed by ignoring the orientation of these initial choices. This construction is illustrated in Figure 2, where nodes select their neighbors to form the final undirected graph. This model is particularly relevant for analyzing networks secured by pairwise key predistribution schemes, where connection budgets are constrained by memory or power.
Connectivity Analysis and Zero-One Laws
The authors establish a sharp zero-one law for $k$-connectivity. They prove that for the network to be $k$-connected asymptotically almost surely (a.a.s.), the number of choices for Type-2 nodes, $K_n$, must scale as: $$K_n = \frac{1}{1-\mu}(\log n +(k-2)\log\log n + \omega(1))$$ for all $k=2, 3, \ldots$.
A key insight is the "connectivity gap": while 1-connectivity only requires $K_n = \omega(1)$, 2-connectivity (robustness to a single failure) requires $K_n$ to scale with $\log n$. This indicates that achieving robustness in heterogeneous networks is significantly more demanding than simple connectivity. Furthermore, the authors prove that the bottleneck for $k$-connectivity is the node with the minimum degree; the threshold for the entire network being $k$-connected is identical to the threshold for every node having at least $k$ neighbors.
Robustness and the Giant Component
Even when the strict requirements for full $k$-connectivity are not met, the network is not necessarily fragmented. The authors prove that if $K_n \geq 2$, the graph will have a "giant component" containing $n - O(1)$ nodes with high probability. This means only a constant number of nodes are left "stranded" regardless of the network's total size. The probability of having more than $M$ nodes outside this giant component decays exponentially as $O(1) \exp\{-M(1-\mu)(K_n-1)\}$. This result explains why many real-world networks remain functional even if they are not strictly $k$-connected.
Numerical Validation
To verify the theoretical asymptotic results, the authors conducted Monte Carlo experiments with up to $n=5000$ nodes and 100,000 independent realizations. Figure 6 shows the probability of $k$-connectivity as a function of $K_n$ for various fractions of Type-1 nodes ($\mu$). The results demonstrate a sharp transition (S-curve) that aligns with the derived zero-one laws.
The bottom-right plot in Figure 6 illustrates the trade-off between the fraction of "weak" nodes ($\mu$) and the connection budget of "strong" nodes ($K_n$) required to achieve a target reliability (e.g., 99% probability of $k$-connectivity). As $\mu$ increases, $K_n$ must increase significantly to maintain the same level of connectivity.
Conclusion
This work provides a rigorous framework for understanding the connectivity and robustness of heterogeneous networks. By establishing sharp thresholds for $k$-connectivity and proving the existence of a giant component under minimal conditions, the authors offer valuable tools for network designers. Future work includes extending the analysis to more than two node types and exploring applications in Payment Channel Networks (PCNs) where edge costs and transaction capacities are major constraints.
Summary updated