| Title | Robustness of Random K-out Graphs |
| Publication Type | Conference Paper |
| Year of Publication | 2021 |
| Authors | Elumar, Eray Can, Yagan, Osman |
| Conference Name | 2021 60th IEEE Conference on Decision and Control (CDC) |
| Date Published | dec |
| Keywords | Collaborative Work, Conferences, consensus dynamics, control theory, Human Behavior, human factors, Measurement, pubcrawl, random graphs, random K-out graphs, resilience, Resiliency, robust control, Robustness, Routing, Scalability, security, Wireless sensor networks |
| Abstract | 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. |
| DOI | 10.1109/CDC45484.2021.9683492 |
| Citation Key | elumar_robustness_2021 |
Robustness of Random K-out Graphs