Estimating Graph Robustness Through the Randic Index.

Area of Science:

• Network Science
• Graph Theory
• Computational Science

Background:

• Graph robustness quantifies system resilience to node/edge loss in social, biological, and technical networks.
• Existing methods for assessing robustness can be computationally intensive.

Purpose of the Study:

• To demonstrate that graph robustness can be efficiently estimated using the Randic index.
• To compare the robustness of real-world networks against theoretical models like Erdos-Renyi (ER) graphs.
• To identify network properties that influence robustness and develop efficient approximation algorithms.

Main Methods:

• Analytical derivation of the Randic index for ER graphs.
• Empirical experiments on diverse real-world network datasets.
• Development of sampling-based algorithms for Randic index approximation.

Main Results:

• The Randic index provides a quick estimation of graph robustness.
• Real-world large graphs exhibit greater robustness than ER graphs with similar parameters.
• Networks with power-law degree distributions show high sensitivity to the removal of a few critical edges.

Conclusions:

• The Randic index is a valuable tool for assessing graph robustness.
• Real-world network structures offer inherent resilience, but critical nodes/edges exist.
• Efficient sampling methods can accurately approximate the Randic index for large networks.