Resilience of Power-Law Degree Distributions of Networks

• Activity Number: 410
• Type: Topic Contributed
• Date/Time: Tuesday, August 5, 2014 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Yafei Wei*+ and Satish Iyengar
• Companies: University of Pittsburgh and University of Pittsburgh
• Keywords: network resilience ; power law ; degree distribution

Abstract

Degree distribution of a network provides information to the structure of the network by which people can predict, design and control this network. Networks may receive attacks. Resilience of degree distribution to the attack is important, since it determines the robustness of quantities and decisions derived from the degree distribution. Degree distribution is found to be power law in a lot of reality network examples. In this article, we study the resilience of degree distribution from networks with power-law degree distribution. We simulate such networks and design experiments to remove vertices from them to see (1) if the resulting network degrees would still follow the power-law distribution (2) if the best fitting power-law parameters will remain unchanged. We experiment with several removal strategies and make comparisons among them. Also, within each strategy, we discuss the conditions under which the degree distribution is resilient to vertex removals, including the maximal removal proportion and the minimal required sample size.