Connectivity of inhomogeneous random K-out graphs

Abstract

We propose inhomogeneous random K-out graphs $\mathbb{H}(n;\mu ,K_n)$, where each of the $n$ nodes is assigned to one of $r$ classes independently with a probability distribution $\mu =\{{\mu }_1,\dots ,{\mu }_r\}$. In particular, each node is classified as class-$i$ with probability ${\mu }_i>0$, independently. Each class-$i$ node selects $K_{i,n}$ distinct nodes uniformly at random from among all other nodes. A pair of nodes are adjacent in $\mathbb{H}(n;\mu ,K_n)$ if at least one selects the other. Without loss of generality, we assume that $K_{1,n}\le K_{2,n}\le \dots \le K_{r,n}$. Earlier results on homogeneous random K-out graphs $\mathbb{H}(n;K_n)$, where all nodes select the same number $K$ of other nodes, reveal that $\mathbb{H}(n;K_n)$ is connected with high probability (whp) if $K_n\ge 2$ which implies that $\mathbb{H}(n;\mu ,K_n)$ is connected whp if $K_{1,n}\ge 2$. In this paper, we investigate the connectivity of inhomogeneous random K-out graphs $\mathbb{H}(n;\mu ,K_n)$ for the special case when $K_{1,n}=1$, i.e., when each class-$1$ node selects only one other node. We show that $\mathbb{H}\left(n;\mu ,K_n\right)$ is connected whp if $K_{r,n}$ is chosen such that ${\lim }_{n\to \infty }{K}_{r,n}=\infty$. However, any bounded choice of the sequence $K_{r,n}$ gives a positive probability of $\mathbb{H}\left(n;\mu ,K_n\right)$ being not connected. Simulation results are provided to validate our results in the finite node regime.

Journal Version. Submitted