Robustness of power-law networks: its assessment and optimization

Many practical complex networks, such as the Internet, WWW and social networks, are discovered to follow power-law distribution in their degree sequences, i.e., the number of nodes with degree $$i$$ i in these networks is proportional to $$i^{-\beta }$$ i - β for some exponential factor $$\beta > 0$$ β > 0 . However, these networks also expose their vulnerabilities to a great number of threats such as adversarial attacks on the Internet, cyber-crimes on the WWW or malware propagations on social networks. Although power-law networks have been found robust under random attacks and vulnerable to intentional attacks via experimental observations, how to better understand their vulnerabilities from a theoretical point of view still remains open. In this paper, we study the vulnerability of power-law networks under random attacks and adversarial attacks using the in-depth probabilistic analysis on the theory of random power-law graph models. Our results indicate that power-law networks are able to tolerate random failures if their exponential factor $$\beta $$ β is $$ 2.5$$ β > 2.5 the network robustness is unpredictable since it depends on the specific attacking strategy.