Vulnerability of robust preferential attachment networks
| Dublin Core | PKP Metadata Items | Metadata for this Document | |
| 1. | Title | Title of document | Vulnerability of robust preferential attachment networks |
| 2. | Creator | Author's name, affiliation, country | Maren Eckhoff; University of Bath; United Kingdom |
| 2. | Creator | Author's name, affiliation, country | Peter Mörters; University of Bath; United Kingdom |
| 3. | Subject | Discipline(s) | |
| 3. | Subject | Keyword(s) | 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 |
| 3. | Subject | Subject classification | 05C80; 60J85; 60K35; 90B15 |
| 4. | Description | 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 $\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. |
| 5. | Publisher | Organizing agency, location | |
| 6. | Contributor | Sponsor(s) | |
| 7. | Date | (YYYY-MM-DD) | 2014-07-05 |
| 8. | Type | Status & genre | Peer-reviewed Article |
| 8. | Type | Type | |
| 9. | Format | File format | |
| 10. | Identifier | Uniform Resource Identifier | http://ejp.ejpecp.org/article/view/2974 |
| 10. | Identifier | Digital Object Identifier | 10.1214/EJP.v19-2974 |
| 11. | Source | Journal/conference title; vol., no. (year) | Electronic Journal of Probability; Vol 19 |
| 12. | Language | English=en | en |
| 14. | Coverage | Geo-spatial location, chronological period, research sample (gender, age, etc.) | |
| 15. | Rights | Copyright and permissions | The Electronic Journal of Probability applies the Creative Commons Attribution License (CCAL) to all articles we publish in this journal. Under the CCAL, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles published in EJP, so long as the original authors and source are credited. This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available. Summary of the Creative Commons Attribution License You are free
|