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

Mansi Sood; Osman Yağan

paper

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

arXiv:1911.05147

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 < μ < 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} \geq 2$ , the graph is $K_{n}$ -connected asymptotically almost surely (a.a.s.) as $n$ gets large. In the inhomogeneous case (i.e., $μ > 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 - μ} (lo g n + (k - 2) lo g lo g n + ω (1))$ for all $k = 2, 3, \dots$ . 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.

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

Abstract

References in corpus (5)