Analyzing R-Robustness of Random K-Out Graphs for the Design of Robust Networks

We consider a graph property known as $r$-robustness, a robustness metric that plays a key role in analyzing consensus dynamics. It was previously shown that in the presence of adversarial nodes, consensus can be reached in an $r$-robust network for sufficiently large $r$. Further, $r$-robustness is a stronger property than $r$-connectivity, hence it is also useful in many applications where robustness of networks to disruptions such as adversarial attacks or node failures is of practical interest. In this paper, we study $r$-robustness of random K-out graphs, which 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. Significantly improving an earlier result, we provide a set of conditions for $K$ and $n$ that ensure, with high probability (whp), the $r$-robustness of the random K-out graph. Simulation results are used to verify the results. To demonstrate the viability of our results in practical applications, we compare our results with the results from Erdös-Rényi and the Barabási-Albert random graph models.

我们考虑一种被称为\(r\)-鲁棒性的图性质，这是一种在分析一致性动态中起关键作用的鲁棒性度量。先前已表明，在存在对抗节点的情况下，对于足够大的\(r\)，在\(r\)-鲁棒网络中可以达成一致性。此外，\(r\)-鲁棒性是一种比\(r\)-连通性更强的性质，因此在许多网络对诸如对抗攻击或节点故障等干扰的鲁棒性具有实际重要性的应用中也很有用。在本文中，我们研究随机\(K\)-出图的\(r\)-鲁棒性，随机\(K\)-出图已在许多应用中使用，包括无线传感器网络中的随机（成对）密钥预分配、加密货币网络中的匿名消息路由以及差分隐私联邦平均。我们显著改进了一个早期结果，为\(K\)和\(n\)提供了一组条件，这些条件以高概率（whp）确保随机\(K\)-出图的\(r\)-鲁棒性。我们使用模拟结果来验证这些结果。为了证明我们的结果在实际应用中的可行性，我们将我们的结果与厄多斯 - 仁伊（Erdös - Rényi）和巴拉巴西 - 阿尔伯特（Barabási - Albert）随机图模型的结果进行了比较。