Biblio

We consider a graph property known as r-robustness of the random K-out graphs. Random K-out graphs, denoted as \$\textbackslashtextbackslashmathbbH(n;K)\$, are constructed as follows. Each of the n nodes select K distinct nodes uniformly at random, and then an edge is formed between these nodes. The orientation of the edges is ignored, resulting in an undirected graph. Random K-out graphs have been used in many applications including random (pairwise) key predistribution in wireless sensor networks, anonymous message routing in crypto-currency networks, and differentially-private federated averaging. r-robustness is an important metric in many applications where robustness of networks to disruptions is of practical interest, and r-robustness is especially useful in analyzing consensus dynamics. It was previously shown that consensus can be reached in an r-robust network for sufficiently large r even in the presence of some adversarial nodes. r-robustness is also useful for resilience against adversarial attacks or node failures since it is a stronger property than r-connectivity and thus can provide guarantees on the connectivity of the graph when up to r – 1 nodes in the graph are removed. In this paper, we provide a set of conditions for Kn and n that ensure, with high probability (whp), the r-robustness of the random K-out graph.

Random K-out graphs, denoted \$$\backslash$mathbbH(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 dishonest, have failed, or have been captured is of practical interest. We provide a comprehensive set of results on the connectivity and giant component size of \$$\backslash$mathbbH(n;K\_n,$\backslash$gamma\_n)\$, i.e., random K-out graph when \textsubscriptn of its nodes, selected uniformly at random, are deleted. First, we derive conditions for \textsubscriptn and \$n\$ that ensure, with high probability (whp), the connectivity of the remaining graph when the number of deleted nodes is \$$\backslash$gamma\_n=Ømega(n)\$ and \$$\backslash$gamma\_n=o(n)\$, respectively. Next, we derive conditions for \$$\backslash$mathbbH(n;K\_n, $\backslash$gamma\_n)\$ to have a giant component, i.e., a connected subgraph with \$Ømega(n)\$ nodes, whp. This is also done for different scalings of \textsubscriptn and upper bounds are provided for the number of nodes outside the giant component. Simulation results are presented to validate the usefulness of the results in the finite node regime.