The vertex attack tolerance of complex networks

Matta, John; Ercal, Gunes; Borwey, Jeffrey

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

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.

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

R. Albert, H. Jeong and A.-L. Barabasi, The internet’s achilles’ heel: Error and attack tolerance of complex networks. Nature 406 (2000) 200–. | DOI

D.L. Alderson, L. Li, W. Willinger and J.C. Doyle, Understanding internet topology: principles, models, and validation. IEEE/ACM Trans. Netw. 13 (2005) 1205–1218. | DOI

N. Alon, Eigenvalues and expanders. Combinat. 6 (1986) 83–96. | DOI | MR | Zbl

A.-L. Barabási and R. Albert, Emergence of scaling in random networks. Sci. 286 (1999) 509–512. | DOI | MR | Zbl

C.A. Barefoot, R. Entringer and H. Swart, Vulnerability in graphs-a comparative survey. J. Comb. Math. Comb. Comput. 1 (1987) 12–22. | MR | Zbl

D. Bauer, S.L. Hakimi and E. Schmeichel, Recognizing tough graphs is np-hard. Discrete Appl. Math. 28 (1990) 191–195. | DOI | MR | Zbl

U. Brandes, A faster algorithm for betweenness centrality. J. Math. Soc. 25 (2001) 163–177. | DOI | Zbl

H. Broersma, J. Fiala, P.A. Golovach and T. Kaiser, Daniël Paulusma and Andrzej Proskurowski. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. J. Graph Theory 79 (2015) 282–299. | DOI | MR | Zbl

F. Chung, Spectral Graph Theory. American Mathematical Society (1997). | MR | Zbl

V. Chvatal, Tough graphs and hamiltonian circuits. Discrete Math. 306 (2006) 910 – 917. | DOI | Zbl

L.F. Costa, F.A. Rodrigues, G. Travieso and P.R. Villas Boas, Characterization of complex networks: A survey of measurements. In Adv. Phys. 56 (2007) 167–242. | DOI

J.C. Doyle, D.L. Alderson, L. Li, S. Low, M. Roughan, S. Shalunov, R. Tanaka and W. Willinger, The robust yet fragile nature of the internet. Proc. of the National Academy of Sciences of the United States of America 102 (2005) 14497–14502. | DOI

P.G. Drange, M.S. Dregi and P. vant Hof, On the computational complexity of vertex integrity and component order connectivity. In Algorithms and Computation. Springer International Publishing (2014) 285–297. | MR

G. Ercal, On vertex attack tolerance of regular graphs. Preprint (2014). | arXiv

G. Ercal, A note on the computational complexity of unsmoothened vertex attack tolerance. Preprint (2016). | arXiv

G. Ercal and J. Matta, Resilience notions for scale-free networks. In Complex Adaptive Systems (2013) 510–515.

A. Fabrikant, E. Koutsoupias and Ch.H. Papadimitriou, Heuristically optimized trade-offs: A new paradigm for power laws in the internet. In ICALP (2002) 110–122. | MR | Zbl

U. Feige, M. Hajiaghayi and J. Lee, Improved Approximation Algorithms for Minimum-Weight Vertex Separators. In Proc. of the Thirty-seventh Annual ACM Symposium on Theory of Computing. ACM, New York (2005) 563–572. | MR | Zbl

U. Feige, Relations between average case complexity and approximation complexity. In Proc. of the Thiry-fourth Annual ACM Symposium on Theory of Computing. ACM (2002) 534–543. | MR | Zbl

U. Feige and Sh. Kogan, Hardness of approximation of the balanced complete bipartite subgraph problem. Technical Report MCS04-04 (2004).

J. Friedman, J. Kahn and E. Szemeredi, On the second eigenvalue of random regular graphs. In Proc. of the twenty-first annual ACM symposium on Theory of computing, STOC ’89. New York, NY, USA, ACM (1989) 587–598.

Z. Furedi and J. Komlos, The eigenvalues of random symmetric matrices. Combinatorica 1 (1981) 233–241. | DOI | MR | Zbl

A. Goerdt and A. Lanka, An approximation hardness result for bipartite clique (2004) 048.

H.A. Jung, On maximal circuits in finite graphs. Ann. Discrete Math. 3 (1978) 129–144. | DOI | MR | Zbl

S. Khot, Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36 (2006) 1025–1071. | DOI | MR | Zbl

A. Louis, P. Raghavendra and S. Vempala, The complexity of approximating vertex expansion. Preprint (2013). | arXiv | MR

S. Stueckle M. Cozzens, D.M. The tenacity of a graph. In Seventh International Conference on the Theory and Applications of Graphs, New York, NY, USA Wiley (1995) 1111–1122. | MR | Zbl

D.E. Mann, The Tenacity of Trees. Ph.D. thesis, Northeastern University, Boston, MA (1993).

J. Matta, Comparing the Effectiveness of Resilience Measures. Master’s thesis, Southern Illinois University, Edwardsville (2014).

J. Matta, J. Borwey and G. Ercal, Comparative resilience notions and vertex attack tolerance of scale-free networks. Preprint (2014). | arXiv

M. Newman, A.-L. Barabasi and D.J. Watts, The Structure and Dynamics of Networks. Princeton University Press (2006). | MR

I. Pak, Random cayley graphs with o(log[g]) generators are expanders. In Proc. of the 7th Annual European Symposium on Algorithms, ESA ’99, London, UK. Springer Verlag (1999) 521–526. | MR | Zbl

C.R. Palmer and J.G. Steffan, Generating network topologies that obey power laws. In Global Telecommunications Conference (2000). GLOBECOM ’00. IEEE, Vol. 1 (2000) 434–438.

J. Šíma and S.E. Schaeffer, On the np-completeness of some graph cluster measures. In SOFSEM: Theory and Practice of Comput. Sci. Springer (2006) 530–537. | Zbl

A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput. 82 (1989) 93–133. | DOI | MR | Zbl