How to cite item

Vulnerability of robust preferential attachment networks

   
@article{EJP2974,
	author = {Maren Eckhoff and Peter Mörters},
	title = {Vulnerability of robust preferential attachment networks},
	journal = {Electron. J. Probab.},
	fjournal = {Electronic Journal of Probability},
	volume = {19},
	year = {2014},
	keywords = {Power law, small world, scale-free network, preferential attachment, Barab\'asi-Albert model, percolation, maximal degree, diameter, network distance, robustness, vulnerability, multitype branching process, killed branching random walk},
	abstract = { 
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 $\varepsi
lon>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.
},
	pages = {no. 57, 1-47},
	issn = {1083-6489},
	doi = {10.1214/EJP.v19-2974},    
        url = {http://ejp.ejpecp.org/article/view/2974}}