Title: Current Flow Group Closeness Centrality for Complex Networks,
Abstract: Current flow closeness centrality (CFCC) has a better discriminating ability
than the ordinary closeness centrality based on shortest paths. In this paper,
we extend this notion to a group of vertices in a weighted graph, and then
study the problem of finding a subset $S$ of $k$ vertices to maximize its CFCC
$C(S)$, both theoretically and experimentally. We show that the problem is
NP-hard, but propose two greedy algorithms for minimizing the reciprocal of
$C(S)$ with provable guarantees using the monotoncity and supermodularity. The
first is a deterministic algorithm with an approximation factor
$(1-\frac{k}{k-1}\cdot\frac{1}{e})$ and cubic running time; while the second is
a randomized algorithm with a
$(1-\frac{k}{k-1}\cdot\frac{1}{e}-\epsilon)$-approximation and nearly-linear
running time for any $\epsilon > 0$. Extensive experiments on model and real
networks demonstrate that our algorithms are effective and efficient, with the
second algorithm being scalable to massive networks with more than a million
vertices.