New Approximation Algorithms for Forest Closeness Centrality -- for\n Individual Vertices and Vertex Groups

The emergence of massive graph data sets requires fast mining algorithms.\nCentrality measures to identify important vertices belong to the most popular\nanalysis methods in graph mining. A measure that is gaining attention is forest\ncloseness centrality; it is closely related to electrical measures using\ncurrent flow but can also handle disconnected graphs. Recently, [Jin et al.,\nICDM'19] proposed an algorithm to approximate this measure probabilistically.\nTheir algorithm processes small inputs quickly, but does not scale well beyond\nhundreds of thousands of vertices.\n In this paper, we first propose a different approximation algorithm; it is up\nto two orders of magnitude faster and more accurate in practice. Our method\nexploits the strong connection between uniform spanning trees and forest\ndistances by adapting and extending recent approximation algorithms for related\nsingle-vertex problems. This results in a nearly-linear time algorithm with an\nabsolute probabilistic error guarantee. In addition, we are the first to\nconsider the problem of finding an optimal group of vertices w.r.t. forest\ncloseness. We prove that this latter problem is NP-hard; to approximate it, we\nadapt a greedy algorithm by [Li et al., WWW'19], which is based on (partial)\nmatrix inversion. Moreover, our experiments show that on disconnected graphs,\ngroup forest closeness outperforms existing centrality measures in the context\nof semi-supervised vertex classification.\n