Estimating Graph Robustness through the Randic Index

Graph robustness-the ability of a graph to preserve its connectivity after the loss of nodes and edges-has been extensively studied to quantify how social, biological, physical, and technical systems withstand to external damages. In this paper, we prove that graph robustness can be quickly estimated through the Randic index, a parameter introduced in chemistry to study organic compounds. We prove that Erdos-Renyj (ER) graphs are a good specimen of robust graphs because they lack of a clear modular structure; we derive an analytical expression for the Randic index of ER graphs and use ER graphs as an effective term of comparison to decide about graph robustness. Experiments on real datasets from different domains (scientific collaboration networks, content-sharing systems, co-purchase networks from an e-commerce platform, and a road network) show that real-life large graphs are more robust than ER ones with the same number of nodes and edges. We also observe that if node degree distribution closely follows a power law, then few edges contribute for more than half of the Randic index, thus indicating that the selective removal of those edges has devastating impact on graph robustness. Finally, we describe sampling-based algorithms to efficiently but accurately approximate the Randic index.