  Closeness is a widely-studied centrality measure. Since it requires all
pairwise distances, computing closeness for all nodes is infeasible for large
real-world networks. However, for many applications, it is only necessary to
find the k most central nodes and not all closeness values. Prior work has
shown that computing the top-k nodes with highest closeness can be done much
faster than computing closeness for all nodes in real-world networks. However,
for networks that evolve over time, no dynamic top-k closeness algorithm exists
that improves on static recomputation. In this paper, we present several
techniques that allow us to efficiently compute the k nodes with highest
(harmonic) closeness after an edge insertion or an edge deletion. Our
algorithms use information obtained during earlier computations to omit
unnecessary work. However, they do not require asymptotically more memory than
the static algorithms (i. e., linear in the number of nodes). We propose
separate algorithms for complex networks (which exhibit the small-world
property) and networks with large diameter such as street networks, and we
compare them against static recomputation on a variety of real-world networks.
On many instances, our dynamic algorithms are two orders of magnitude faster
than recomputation; on some large graphs, we even reach average speedups
between $10^3$ and $10^4$.
