All Dates/Times are Australian Eastern Standard Time (AEST)

# Technical Program

## Paper Detail

 Paper ID D6-S2-T3.1 Paper Title On the Connectivity and Giant Component Size of Random K-out Graphs Under Randomly Deleted Nodes Authors Eray Can Elumar, Mansi Sood, Osman Yagan, Carnegie Mellon University, United States Session D6-S2-T3: Sub-Hypergraph Models Chaired Session: Monday, 19 July, 22:20 - 22:40 Engagement Session: Monday, 19 July, 22:40 - 23:00 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.