The vertex attack tolerance of complex networks

Matta, John¹ ; Ercal, Gunes¹ ; Borwey, Jeffrey¹

¹ Southern Illinois University, Edwardsville, Illinois, USA.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 1055-1076

Résumé

The purpose of this work is four-fold: (1) We propose a new measure of network resilience in the face of targeted node attacks, vertex attack tolerance, represented mathematically as $\tau \left(G\right)={min}_{S\subset V}\frac{\left|S\right|}{|V-S-C_{\max }(V-S)|+1}$, and prove that for $d$-regular graphs $\tau \left(G\right)=\Theta \left(\Phi \right(G\left)\right)$ where $\Phi \left(G\right)$ denotes conductance, yielding spectral bounds as corollaries. (2) We systematically compare $\tau \left(G\right)$ to known resilience notions, including integrity, tenacity, and toughness, and evidence the dominant applicability of $\tau$ for arbitrary degree graphs. (3) We explore the computability of $\tau$, first by establishing the hardness of approximating unsmoothened vertex attack tolerance $\widehat{\tau }\left(G\right)={min}_{S\subset V}\frac{\left|S\right|}{|V-S-C_{\max }(V-S)|}$ under various plausible computational complexity assumptions, and then by presenting empirical results on the performance of a betweenness centrality based heuristic algorithm applied not only to $\tau$ but several other hard resilience measures as well. (4) Applying our algorithm, we find that the random scale-free network model is more resilient than the Barabasi−Albert preferential attachment model, with respect to all resilience measures considered.

Détail

DOI : 10.1051/ro/2017008

Classification : 68R10, 90B15, 05C50, 68Q25
Keywords: Graph theory, resilience, Scale-Free networks, spectral Gap, approximation Hardness, Heuristic Algorithms