论文标题
一种基于样本的算法，用于大约测试$ r $ $ - 挖掘的算法
A Sample-Based Algorithm for Approximately Testing $r$-Robustness of a Digraph
论文作者
论文摘要
网络鲁棒性的深入研究概念之一是$ r $ bobustness，它是由整数$ r $量化的网络拓扑属性。平均分子降低（MSR）算法及其变体需要达到弹性共识。但是，确定$ r $ - 塑料对于大型网络是棘手的。在本文中，我们提出了一种基于样本的算法，以大约测试带有$ n $ Vertices和$ m $边缘的Digraph的$ r $ bobustness。对于在最小值内进行中等假设的DIGRAPH和错误参数$ 0 <ε\ leq 1 $，建议的算法将$（r+εn）$区分出与不是$ r $ -Robust的图形的强大图形，而不是$ r $ -Robust，则具有概率$（1-δ）$。我们的算法在$ \ exp中运行（o（（（\ ln {\ frac {1} {εδ}}}）/ε^2））\ cdot m $ time。如果$ε$是一个常数，则运行时间是线性的。
One of the intensely studied concepts of network robustness is $r$-robustness, which is a network topology property quantified by an integer $r$. It is required by mean subsequence reduced (MSR) algorithms and their variants to achieve resilient consensus. However, determining $r$-robustness is intractable for large networks. In this paper, we propose a sample-based algorithm to approximately test $r$-robustness of a digraph with $n$ vertices and $m$ edges. For a digraph with a moderate assumption on the minimum in-degree, and an error parameter $0<ε\leq 1$, the proposed algorithm distinguishes $(r+εn)$-robust graphs from graphs which are not $r$-robust with probability $(1-δ)$. Our algorithm runs in $\exp(O((\ln{\frac{1}{εδ}})/ε^2))\cdot m$ time. The running time is linear in the number of edges if $ε$ is a constant.
