A Sample-Based Algorithm for Approximately Testing $r$-Robustness of a Digraph

Abstract

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<\epsilon \le 1$, the proposed algorithm distinguishes $(r+\epsilon n)$-robust graphs from graphs which are not $r$-robust with probability $(1-\delta )$. Our algorithm runs in $\exp (O((\ln \frac{1}{\epsilon \delta })/{\epsilon }^2))\cdot m$ time. The running time is linear in the number of edges if $\epsilon$ is a constant.

8 pages, 3 figures