The Effect of Random Edge Removal on Network Degree Sequence.

Area of Science:

• Network Science
• Graph Theory
• Statistical Physics

Background:

• Real-world networks (WWW, social, biological) often exhibit specific degree structures like power-law.
• Understanding how network properties change under random failures is crucial for modeling processes like information spreading and system robustness.
• Previous work explored edge removal effects, but a generalized approach for various degree sequences was lacking.

Purpose of the Study:

• To analyze the impact of independent, probabilistic edge failures on the degree structure of networks.
• To develop a classification of degree sequences that simplifies predicting post-failure network properties.
• To derive asymptotic results and concentration bounds for the expected degree sequence after edge removal.

Main Methods:

• Analysis of edge failure effects on degree sequences of power-law and exponential networks.
• Derivation of asymptotic results for general degree sequences, inspired by power-law network behavior.
• Development of a classification scheme for degree sequences based on their response to edge removal.

Main Results:

• Identified a classification of degree sequences that dictates their behavior under random edge removal.
• Established simple, predictive rules for the expected degree sequence of networks after probabilistic edge failures.
• Provided concentration bounds to quantify the deviation from the expected degree sequence.

Conclusions:

• The proposed classification and rules offer a generalized framework for understanding network degree structure evolution under random edge failures.
• The findings are applicable to various network types and provide insights into network robustness and dynamics.
• This work improves upon existing models by offering a more comprehensive and predictive approach to random edge removal in networks.