Loading [MathJax]/extensions/MathZoom.js
Forest Distance Closeness Centrality in Disconnected Graphs | IEEE Conference Publication | IEEE Xplore

Forest Distance Closeness Centrality in Disconnected Graphs


Abstract:

Ranking the relative importance of nodes is a fundamental issue in network science, especially in the analysis of social and information networks. A variety of importance...Show More

Abstract:

Ranking the relative importance of nodes is a fundamental issue in network science, especially in the analysis of social and information networks. A variety of importance metrics and related algorithms have been proposed. However, these previous measures either do not apply to disconnected networks or have some weakness when applied to disconnected networks. In this paper, we use forest distance to assess the importance of nodes in a graph, whether connected or disconnected. For a node in a graph, its forest distance is defined as the sum of forest distances from the node to all other nodes in the graph. To illustrate the discriminating power of forest distance, we first compute the exact forest distances for all nodes in the path graph, and show that the order of node importance given by forest distances is in complete agreement with our intuition. We then show that forest distance centrality has a better discriminating power than alternate metrics such as betweenness, harmonic centrality, eigenvector centrality, and PageRank. Also, we present a theoretically guaranteed estimation algorithm, which approximates the forest distances for all nodes in a graph in nearly linear time with respect to the number of edges. Finally, we perform extensive experiments on real-world networks, which show that our approximation algorithm is both efficient and accurate for large networks.
Date of Conference: 08-11 November 2019
Date Added to IEEE Xplore: 30 January 2020
ISBN Information:

ISSN Information:

Conference Location: Beijing, China
Related Articles are not available for this document.

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.

References

References is not available for this document.