| Abstract |
Random K-out graphs, denoted \(\mathbb{H}(n;K)\), are generated by each of the \(n\) nodes drawing \(K\) out-edges towards \(K\) distinct nodes selected uniformly at random, and then ignoring the orientation of the arcs. Recently, random K-out graphs have been used in applications as diverse as random (pairwise) key predistribution in ad-hoc networks, anonymous message routing in crypto-currency networks, and differentially-private federated averaging. In many applications, connectivity of the random K-out graph when some of its nodes are {\em dishonest}, have {\em failed}, or have been {\em captured} is of practical interest. We provide a comprehensive set of results on the connectivity and giant component size of \(\mathbb{H}(n;K_n,\gamma_n)\), i.e., random K-out graph when \(\gamma_n\) of its nodes, selected uniformly at random, are deleted. First, we derive conditions for \(K_n\) and \(n\) that ensure, with high probability (whp), the connectivity of the remaining graph when the number of deleted nodes is \(\gamma_n=\Omega(n)\) and \(\gamma_n=o(n)\), respectively. Next, we derive conditions for \(\mathbb{H}(n;K_n,\gamma_n)\) to have a {\em giant component}, i.e., a connected subgraph with \(\Omega(n)\) nodes, whp. This is also done for different scalings of \(\gamma_n\) and {\em upper} bounds are provided for the number of nodes {\em outside} the giant component. Simulation results are presented to validate the usefulness of the results in the finite node regime.
|
