I. Introduction
The issue of identifying crucial nodes in a graph has a rich history in machine learning and social network analysis [1], [2], [3]. It constitutes a foundation and an important tool for network science, especially for graph data mining, and has found a wide range of applications [4]. Various indices measuring the relative importance of nodes have been developed [5], such as closeness centrality [6], [7], eccentricity [8], betweenness [9]. Most of these metrics are based on the shortest paths, which have several shortcomings. First, they neglect the contributions of other paths, even the second shortest paths. Second, some of them do not apply to networks that are not connected, in spite of the fact that many realistic networks are disconnected, e.g., Mobile Ad hoc Networks [10] and protein-protein interaction networks [11]. For example, closeness centrality fails to discriminate nodes in disconnected networks, since their closeness are identical and equal to ∞. To overcome the first deficiency, some measures (e.g. current-flow closeness centrality) based on random walks [12] or electrical networks [13] were proposed, which are still subject to the second weakness.