Vulnerability of robust preferential attachment networks

Maren Eckhoff (University of Bath)
Peter Mörters (University of Bath)


Scale-free networks with small power law exponent are known to be robust, meaning that their qualitative topological structure cannot be altered by random removal of even a large proportion of nodes. By contrast, it has been argued in the science literature that such networks are highly vulnerable to a targeted attack, and removing a small number of key nodes in the network will dramatically change the topological structure. Here we analyse a class of preferential attachment networks in the robust regime and prove four main results supporting this claim: After removal of an arbitrarily small proportion $\varepsilon>0$ of the oldest nodes (1) the asymptotic degree distribution has exponential instead of power law tails; (2) the largest degree in the network drops from being of the order of a power of the network size $n$ to being just logarithmic in $n$; (3) the typical distances in the network increase from order $\log\log n$ to order $\log n$; and (4) the network becomes vulnerable to random removal of nodes. Importantly, all our results explicitly quantify the dependence on the proportion $\varepsilon$ of removed vertices. For example, we show that the critical proportion of nodes that have to be retained for survival of the giant component undergoes a steep increase as $\varepsilon$ moves away from zero, and a comparison of this result with similar ones for other networks reveals the existence of two different universality classes of robust network models. The key technique in our proofs is a local approximation of the network by a branching random walk with two killing boundaries, and an understanding of the particle genealogies in this process, which enters into estimates for the spectral radius of an associated operator.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-47

Publication Date: July 5, 2014

DOI: 10.1214/EJP.v19-2974


  • Albert, Réka; Albert, István; Nakarado, Gary L. Structural vulnerability of the North American power grid. Phys. Rev. E 69 (2004), 025103.
  • Albert, Réka; Jeong, Hawoong; Barabási, Albert-László. Error and attack tolerance of complex networks. Nature 406 (2000), 378--382.
  • Barabási, Albert-László; Albert, Réka. Emergence of Scaling in Random Networks. Science 286 (1999), no. 5439, 509--512. MR2091634
  • Bhamidi, Shankar; Hofstad, Remco van der; Hooghiemstra, Gerard. Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks. Adv. in Appl. Probab. 42 (2010), no. 3, 706--738. MR2779556
  • Biggins, John D.; Kyprianou, Andreas E. Measure change in multitype branching. Adv. in Appl. Probab. 36 (2004), no. 2, 544--581. MR2058149
  • Bollobás, Béla; Janson, Svante; Riordan, Oliver. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 (2007), no. 1, 3--122. MR2337396
  • Bollobás, Béla; Riordan, Oliver. Robustness and vulnerability of scale-free random graphs. Internet Math. 1 (2003), no. 1, 1--35. MR2076725
  • Callaway, Duncan S.; Newman, Mark E. J.; Strogatz, Steven H.; Watts, Duncan J. Network Robustness and Fragility: Percolation on Random Graphs. Phys. Rev. Lett. 85 (2000), no. 25, 5468--5471.
  • Chung, Fan; Lu, Linyuan. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 (2002), no. 25, 15879--15882. MR1944974
  • Chung, Fan; Lu, Linyuan. Complex graphs and networks. Regional Conference Series in Mathematics, vol. 107, Co-publication of the AMS and CBMS, 2006. MR2248695
  • Cohen, Reuven; Erez, Keren; ben-Avraham, Daniel; Havlin, Shlomo. Breakdown of the Internet under Intentional Attack. Phys. Rev. Lett. 86 (2001), 3682--3685.
  • Cohen, Reuven; Erez, Keren; ben-Avraham, Daniel; Havlin, Shlomo. Reply. Phys. Rev. Lett. 87 (2001), 219802.
  • Dereich, Steffen; Mönch, Christian; Mörters, Peter. Typical distances in ultrasmall random networks. Adv. in Appl. Probab. 44 (2012), no. 2, 583--601. MR2977409
  • Dereich, Steffen; Mörters, Peter. Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Probab. 14 (2009), no. 43, 1222--1267. MR2511283
  • Dereich, Steffen; Mörters, Peter. Random networks with sublinear preferential attachment: the giant component. Ann. Probab. 41 (2013), no. 1, 329--384. MR3059201
  • Dommers, Sander; van der Hofstad, Remco; Hooghiemstra, Gerard. Diameters in preferential attachment models. J. Stat. Phys. 139 (2010), no. 1, 72--107. MR2602984
  • Dorogovtsev, Sergey N.; Mendes, José F. F. Comment on ''Breakdown of the Internet under Intentional Attack''. Phys. Rev. Lett. 87 (2001), 219801.
  • Esker, Henri van den; Hofstad, Remco van der; Hooghiemstra, Gerard; Znamenski, Dmitri. Distances in random graphs with infinite mean degrees. Extremes 8 (2005), no. 3, 111--141 (2006). MR2275914
  • Feller, William. An introduction to probability theory and its applications. Vol. II. John Wiley & Sons, Inc., New York-London-Sydney 1971. MR0270403
  • Harris, Simon C.; Hesse, Marion; Kyprianou, Andreas E. Branching Brownian motion in a strip: survival near criticality. 2012. Preprint available at arXiv:1212.1444 [math.PR]
  • Harris, Theodore E. The theory of branching processes. Die Grundlehren der Mathematischen Wissenschaften, Bd. 119 Springer-Verlag, Berlin. 1963. MR0163361
  • Heuser, Harro G. Functional analysis. John Wiley & Sons, Chichester. 1982. MR0640429
  • Hofstad, Remco van der. Random graphs and complex networks, Draft book, available online at, 2013.
  • Holme, Petter; Kim, Beom Jun; Yoon, Chang No; Han, Seung Kee. Attack vulnerability of complex networks. Phys. Rev. E 65 (2002), 056109.
  • Janson, Svante. On percolation in random graphs with given vertex degrees. Electron. J. Probab. 14 (2009), no. 5, 87--118. MR2471661
  • Janson, Svante; Luczak, Malwina J. A new approach to the giant component problem. Random Structures Algorithms 34 (2009), no. 2, 197--216. MR2490288
  • Kato, Tosio. Perturbation theory for linear operators. Reprint of the 1980 edition. Classics in Mathematics. Springer-Verlag, Berlin, 1995. MR1335452
  • Miller, Peter D. Applied asymptotic analysis. Graduate Studies in Mathematics, 75. American Mathematical Society, Providence, RI, 2006. MR2238098
  • Mishkovski, Igor; Biey, Mario; Kocarev, Ljupco. Vulnerability of complex networks. Commun. Nonlinear Sci. Numer. Simul. 16 (2011), no. 1, 341--349. MR2679185
  • Molloy, Michael; Reed, Bruce. A critical point for random graphs with a given degree sequence. Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, "Random Graphs '93'' (Poznań, 1993). Random Structures Algorithms 6 (1995), no. 2-3, 161--179. MR1370952
  • Mönch; Christian. Distances in preferential attachment networks, Ph.D. thesis, University of Bath, 2013.
  • Pinsky, Ross G. Positive harmonic functions and diffusion. Cambridge Studies in Advanced Mathematics, 45. Cambridge University Press, Cambridge, 1995. MR1326606

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.