Resilience Notions for Scale-free Networks

Abstract

Much of traditional graph theoretic analysis of networks had focused on regular or near-regular network models such as random Erdos-Renyi models, where the degree distribution is either the same for every node or highly concentrated about the mean. As such, much beautiful theoretical machinery exists to analyze various properties including analysis of network resilience via eigenvalues of the adjacency matrix representing the network. However, it has been recently observed that real world networks tend to be scale-free, which usually implies a high variance and power-law degree distribution. This poses a problem in applying existing theoretical machinery to some problems, particularly that of the resilience of networks to node attacks. In this work we examine networks in which the greatest discrepancy arises in attempting to apply previous resilience notions, and we tailor a new mathematical notion of resilience that works for scale-free networks in the presence of node attacks.