Effective Node Resistance and its Implication on Network Robustness

Robustness against failures and attacks is an important property of large scale systems such as power grids, transportation systems, communication systems and computer networks. It has been known that the largest connected component size and the diameter are related to network robustness. Also, it has been known that the effective graph resistance is useful for estimating the robustness of the network. On the contrary, the node robustness quantifies the likelihood of the node to be connected with other nodes in the network under disturbances such as node/link failures has not been fully investigated. We can similarly define a per-node effective resistance for every node, which could be useful for understanding characteristics of every node rather than the entire graph as a whole. In this paper, we propose an effective node resistance that quantifies the characteristics of each node in the graph, and investigate how effectively effective node resistance can estimate the robustness of each node in the network against random node/link removal. Our finding includes that effective node resistance can estimate the robustness of each node in particular graphs.

I. Introduction

In recent years, graph spectral measures (e.g., the effective graph resistance, the algebraic connectivity and the spectral radius) have attracted attention as means for analyzing the characteristics of a communication network as well as estimating its internal properties. Among several spectral measures, it has been known that the effective graph resistance is effective for estimating the robustness of a communication network against random failures [1]. In addition to the effective graph resistance, the algebraic connectivity has been proposed as a measure for estimating network robustness [2], [3]. The algebraic connectivity is related to classical geometric graph metrics such as the node/link connectivity, and it can be regarded as an index quantifying the difficulty of the network partitioning [2].