# Technical Program

## Paper Detail

 Paper ID G.1.5 Paper Title k-Connectivity in Random Graphs induced by Pairwise Key Predistribution Schemes Authors Mansi Sood, Osman Yagan, Carnegie Mellon University Pittsburgh, United States Session G.1: Graph Analytics Presentation Lecture Track Graphs, Games, Sparsity, and Signal Processing Manuscript Click here to download the manuscript Virtual Presentation Click here to watch in the Virtual Symposium Abstract Random key predistribution schemes serve as a viable solution for facilitating secure communication in Wireless Sensor Networks (WSNs). We analyze \emph{reliable} connectivity of a {\em heterogeneous} WSN under the random pairwise key predistribution scheme of Chan et al. According to this scheme, each of the $n$ sensor nodes is classified as type-1 (respectively, type-2) with probability $\mu$ (respectively, $1-\mu)$ where $0<\mu<1$. Each type-1 (respectively, type-2) node is {\em paired} with 1 (respectively, $K_n$) other node selected uniformly at random; each {\em pair} is then assigned a unique pairwise key so that they can securely communicate with each other. A main question in the design of secure and heterogeneous WSNs is how should the parameters $n$, $\mu$, and $K_n$ be selected such that resulting network exhibits certain desirable properties with high probability. Of particular interest is the {\em strength} of connectivity often studied in terms of $k$-connectivity; i.e., with $k=1, 2, \ldots$, the property that the network remains connected despite the removal of any $k-1$ nodes or links.In this paper, we answer this question by analyzing the {\em inhomogeneous random K-out graph} model naturally induced under the heterogeneous pairwise scheme. It was recently established that this graph is 1-connected asymptotically almost surely (a.a.s.) if and only if $K_n=\omega(1)$. Here, we show that for $k=2, 3, \ldots$, we need to set $K_n = \frac{1}{1-\mu}(\log n +(k-2)\log\log n + \omega(1))$ for the network to be $k$-connected a.a.s. The result is given in the form of a zero-one law indicating that the network is a.a.s. {\em not} $k$-connected when $K_n = \frac{1}{1-\mu}(\log n +(k-2)\log\log n - \omega(1))$. We present simulation results to demonstrate the usefulness of the results in the finite node regime.