Robustness of preferential-attachment graphs
Open Access
- 13 June 2023
- journal article
- research article
- Published by Springer Nature in Applied Network Science
- Vol. 8 (1) , 1-19
Abstract
The widely used characterization of scale-free networks as “robust-yet-fragile” originates primarily from experiments on instances generated by preferential attachment. According to this characterization, scale-free networks are more robust against random failures but more fragile against targeted attacks when compared to random networks of the same size. Here, we consider a more appropriate baseline by requiring that the random networks match not only the size but also the inherent minimum degree of preferential-attachment networks they are compared with. Under this more equitable condition, we can (1) prove that random networks are almost surely robust against any vertex removal strategy and (2) show through extensive experiments that scale-free networks generated by preferential attachment are not particularly robust against random failures. Finally, we (3) add experiments demonstrating that preferentially attaching to well-connected vertices does not enhance robustness at all.Keywords
Funding Information
- Swiss Federal Institute of Technology Zurich
This publication has 24 references indexed in Scilit:
- Mitigation of malicious attacks on networksProceedings of the National Academy of Sciences, 2011
- Fast algorithms for determining (generalized) core groups in social networksAdvances in Data Analysis and Classification, 2010
- Asymptotic normality of the k-core in random graphsThe Annals of Applied Probability, 2008
- The “robust yet fragile” nature of the InternetProceedings of the National Academy of Sciences, 2005
- Attack vulnerability of complex networksPhysical Review E, 2002
- Error and attack tolerance of complex networksNature, 2000
- Graph structure in the WebComputer Networks, 2000
- The Size of the Giant Component of a Random Graph with a Given Degree SequenceCombinatorics, Probability and Computing, 1998
- Silhouettes: A graphical aid to the interpretation and validation of cluster analysisJournal of Computational and Applied Mathematics, 1987
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980