Vulnerability of robust preferential attachment networks

DOI10.1214/EJP.V19-2974MaRDI QIDQ743481zbMATH OpenFDO

Authors Maren Eckhoff, Peter Mörters

Publication date 24 September 2014

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3454

zbMATH Keywords

power lawrobustnessmultitype branching processdiameterpercolationpreferential attachmentscale-free networkvulnerabilitykilled branching random walksmall worldmaximal degreenetwork distanceBarabási-Albert model

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Applications of branching processes (60J85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15)

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 epsilon>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 epsilon 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 epsilon 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.

Recommendations

• Robustness of spatial preferential attachment networks
• Robustness of scale-free spatial networks
• Robustness and Vulnerability of Scale-Free Random Graphs
• Robustness of Preferential Attachment Under Deletion of Edges
• Robustness of power-law networks: its assessment and optimization

Cited in

(14)

• When is a scale-free graph ultra-small?
• Robustness of scale-free spatial networks
• Vulnerability of complex networks under three-level-tree attacks
• Robustness and Vulnerability of Scale-Free Random Graphs
• Distance evolutions in growing preferential attachment graphs
• Security of scale-free networks
• Thresholds in the resilience of modular social networks to invasion by defectors
• Vulnerability of weighted networks
• Tomography and stability of complex networks
• Robustness of spatial preferential attachment networks
• Connectivity of random graphs after centrality-based vertex removal
• Exploiting the robustness on power-law networks
• Robustness of power-law networks: its assessment and optimization
• Lyapunov-based anomaly detection in preferential attachment networks

This page was built for publication: Vulnerability of robust preferential attachment networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743481)