Assessing Graph Robustness through Modified Zagreb Index

Abstract

Graph robustness or network robustness is the ability that a graph or a network preserves its connectivity or other properties after the loss of vertices and edges, which has been a central problem in the research of complex networks. In this paper, we introduce the Modified Zagreb index and Modified Zagreb index centrality as novel measures to study graph robustness. We theoretically find some relationships between these novel measures and some other graph measures. Then, we use Modified Zagreb index centrality to analyze the robustness of BA scale-free networks, ER random graphs and WS small world networks under deliberate or random vertex attacks. We also study the correlations between this new measure and some other existed measures. Finally, we use Modified Zagreb index centrality to study the robustness of two real world networks. All these results demonstrate the efficiency of Modified Zagreb index centrality for assessing the graph robustness.

Keywords

• modified Zagreb index
• modified Zagreb index centrality
• graph robustness
• complex network