Computing Top-k Closeness Centrality
in Fully-dynamic Graphs

arXiv:1710.01143v1 [cs.DS] 3 Oct 2017

Patrick Bisenius, Elisabetta Bergamini, Eugenio Angriman, Henning Meyerhenke∗

Abstract
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 103 and 104 .

∗
This work is partially supported by German Research Foundation (DFG) grant ME 3619/3-1 within the Priority
Programme 1736 Algorithms for Big Data.

1

1 INTRODUCTION

October 4, 2017, 0:52

1

Introduction

Context and Motivation. Centrality is a widely used concept in network analysis in order to rank
the nodes of a graph by their structural importance. (Edge centrality measures exist as well, but are
not considered here.) Many centrality definitions include the length of shortest paths, their fraction
or their number, the importance of a node in random walk processes, and many more [18, Chap. 7].
Different applications may require different centrality measures and none is universal; thus, dozens of
different measures have been spotted in the literature [6].
In this work, we focus on one of the most widely used measures, closeness centrality. It is defined
as the inverse of the average shortest-path distance. Example applications listed in previous work [2]
include facility location, marketing strategies, and the identification of key infrastructure nodes as well
as disease propagation control and crime prevention.
Computing the closeness centrality of a node in an unweighted graph requires a complete breadthfirst search (BFS) — or a complete run of Dijkstra’s algorithm for weighted graphs. Moreover, it
requires solving the all-pairs-shortest-path problem to compute the closeness centrality of each node
in the graph. The computational effort for this is often impractical for very large real-world networks.
For some applications, however, it is enough to compute a list of the k most central nodes. As shown
by Bergamini et al. [2], limiting oneself to this so-called top-k closeness centrality problem can decrease
the computational effort significantly for real-world networks. The idea of existing approaches [7, 2] is
to compute upper bounds on the closeness of each node. If we find k nodes whose closeness is higher
than the upper bounds on the remaining nodes, we know these nodes have to be the top k.
Although these approaches were shown to work very well in practice, they are asymptotically not
faster than computing closeness for all nodes. In fact, the most central node in a graph cannot be computed in O(|E|2− ) in directed graphs in the worst-case, under reasonable complexity assumptions [2].
Many real-world networks change over time; just think of social networks constantly adding new
users (node insertions) or friendship relations (edge insertions). Terminating a friendship in the social
network corresponds to an edge removal. Similar effects can be seen in the web graph or co-authorship
graphs with sliding time windows. Edge modifications may cause shortest paths to appear or disappear,
depending on the modification. A simple strategy to get the new closeness centralities of each node
is then to rerun the static algorithm on the modified graph, ignoring any information collected by
previous runs of the algorithm. However, as previous work for related problems [14, 4, 5, 13] has
shown, it is usually much more efficient in practice to make more localized updates to the centrality
values.
Outline and Contribution. This paper presents dynamic algorithms for top-k closeness that handle
both edge insertions and edge removals, see Section 3. Our new algorithms are based on the static
algorithms proposed by Bergamini et al. [3] (and in [2], in a preliminary version). Since traditional
closeness does not apply to disconnected graphs, our algorithms compute a variant called harmonic
closeness, which has been shown in [6] to satisfy all axioms presented in the same paper. However, our
algorithms can be easily adapted to Bavelas’s definition of closeness as well.
Our algorithms reuse information obtained by an initial run of the static algorithm and try to
skip the recomputation of closeness centralities for nodes that are unaffected by modifications of the
graph. In contrast to other dynamic algorithms for closeness centrality, it is not required to compute
the exact closeness centralities of all nodes in the initial graph, making it possible to target networks
with hundreds of millions of edges. Moreover, we specifically design our algorithms to use only a
linear amount of additional memory, since a quadratic memory footprint (typical of most existing
dynamic algorithms for problems based on shortest paths) would be impractical for large instances.
In experiments we obtain significant speedups compared to static recomputation. For example, for
k = 10, our average speedup (geometric mean over the tested instances) is about 76 for insertions in
2

2 PRELIMINARIES

October 4, 2017, 0:52

undirected complex networks. For deletions in directed street networks, we reach an average speedup
of 743. Also, our experiments show some non-trivial results: deletions are mostly faster than insertions
and speedups increase with k for complex networks, whereas they decrease as k increases in street
networks.

2
2.1

Preliminaries
Notation and Problem Definition

Let G be an unweighted graph (either directed or undirected) with n nodes and m edges. We use d(u, v)
to denote the shortest-path distance between two nodes u and v. The set of nodes at distance i from
u is denoted by Ni (u) := {v : d(u, v) = i} and its cardinality by ni (u). The reachable nodes R(u) :=
{v : d(u, v) < +∞} are the nodes with finite distance from u (we denote their cardinality by r(u)).
According to Bavelas’s definition, the closeness centrality of node u in a (strongly) connected graph
is P n−1
[1]. For disconnected graphs, this quantity is not defined, since the denominator would
v∈V d(u,v)
be infinity for all nodes. We consider a variant of closeness called harmonic closeness centrality [6],
defined as follows:
X
1
.
c(u) :=
d(u, v)
v∈V, v6=u

In addition to extending to disconnected graphs in a very natural way, harmonic closeness has been
shown in [6] to satisfy all axioms presented in the same paper (i.e., size, density and score monotonicity).
When talking about dynamic graphs, we refer to G as the graph before the edge update, and to G0
as the modified graph. Similarly, d is the distance on G and d0 the distance on G0 .

2.2

Related Work

Static Algorithms. Closeness centrality is based on pairwise shortest-path distances. In unweighted
graphs, these are usually computed by running a BFS (Breadth-First Search) from each node, requiring
Θ(nm) time. Unfortunately, this is impractical for large networks with hundreds of millions of nodes
and edges. For this reason, several approximation algorithms have been proposed over the years. The
simple approach by Eppstein and Wang samples a set of source nodes, runs a BFS from them and
uses the computed distances to extrapolate the closeness of the other nodes [12]. If the graph has a
bounded diameter, this approach delivers an additive error guarantee with high probability. Cohen et
al. [9] improve on this approach by combining the sampling with a new3-approximation algorithm.
This

−Ω(l3 )
1
1

provides an estimate c̃(v) of the centrality of each node v such that P c̃(v) − c(v) ≥ c(v) ≤ 2e
,
where l is the number of samples. The recent result by Chechik et al. [8] allows to approximate
closeness centrality with a coefficient of variation of  using O(−2 ) BFS computations. Alternatively,
one can make the probability that the maximum relative error exceeds  polynomially small by using
O(−2 log n) BFS computations. Although approximation algorithms can often provide scores that are
close to the real ones, they may fail at preserving the ranking, in particular for nodes with similar
closeness. For example, it was argued in [3] that the algorithm by Chechik et al. [8] would require
O(mn2 ) time to deliver a reliable ranking in a small-world network.
For this reason, the problem of preserving the ranking of the top-k nodes with highest closeness
has been considered, both exactly [20], with high probability [19] and through heuristics [17, 16].
In particular, the exact approaches proposed in [3] (and in [2], in a preliminary version) have been
shown to outperform existing algorithms for finding the top-k nodes with highest closeness centrality.
More specifically, the authors of this prior work propose a method (NBCut) that works best for networks
with small diameter (such as complex networks), and a method (NBBound) that is more efficient on
3

2 PRELIMINARIES

October 4, 2017, 0:52

y

X

z:d(y,z)≤i

Exact

1
d(y, z)

ñi+1
i+1
Pi
r(y) − j=1 ni − ñi+1

i+1
i+2

i+2

Figure 1: Upper bound on c(y) computed by the NBCut algorithm. For nodes up to distance dcut (y)
we know the exact distance. Then, ñdcut (y)+1 nodes are assumed to be at distance dcut (y) + 1 and the
remaining at distance dcut (y) + 2.
networks with relatively large diameter (such as street networks). Since our new dynamic algorithms
build on these two approaches, we explain them in more detail in Section 2.3. Notice that these are
exact approaches, i.e., they find the k nodes with highest closeness and their exact closeness values.
Similarly, also our dynamic algorithms are exact.
Dynamic Algorithms. Many of today’s networks continuously change over time. Recomputing
the centrality values after each edge modification may be too expensive for large instances. Dynamic
algorithms try to update some properties of the graph by limiting the computations to a subset of
the nodes and edges. For updating the closeness of all nodes, a simple algorithm has been proposed
by Kas et al. [14]. The authors use a dynamic algorithm by Ramalingam and Reps [21] for updating
pairwise distances and either increase or decrease the closeness of nodes whose distance has changed.
A major limitation of this approach is its memory requirement of Θ(n2 ), which is too expensive for
large networks.
For unweighted graphs, Sariyüce et al. [22] present optimizations that make the dynamic algorithm
more efficient on complex networks. In particular, they show that the recomputation of closeness
can be skipped for nodes s such that |d(s, u) − d(s, v)| = 1 (where u and v are the endpoints of the
newly inserted or deleted edge). Also, they divide the graph into biconnected components and show
that nodes outside the biconnected component of (u, v) can also be skipped. Finally, they notice that
nodes with the same neighborhood have the same closeness, and therefore (re)computing it for only
one of the nodes is sufficient. Differently from the algorithm by Kas et al. [14], the one by Sariyüce
et al. [23] does not store pairwise distances, resulting in a memory requirement of Θ(n). Nevertheless,
both algorithms require to compute exact closeness centrality at least once on the initial graph, which
might be impractical.

2.3

Static Top-k Closeness

The textbook algorithm would compute closeness by running a BFS from each node. Both top-k
closeness algorithms proposed in [3] try to reduce the running time of the textbook algorithm by
exploiting upper bounds on the closeness. More precisely, NBCut reduces the work done during the
BFSs, but not their number (i. e., it starts a BFS from each node). NBBound, on the contrary, runs
complete BFSs, but on a limited number of nodes. Although both algorithms were proposed using
Bavelas’s definition of closeness, it was shown in [3] how they can be adapted to harmonic closeness.
In the following, we describe them based on this adaptation.
4

3 DYNAMIC TOP-K CLOSENESS CENTRALITY

October 4, 2017, 0:52

NBCut Algorithm for Complex Networks. Assume we are performing a BFS from a node y,
and we have visited all nodes up to distance i. We know that all remaining nodes have at least
distance
i + 1, otherwise they would have been visited already. Also, we know that at most ñi+1 :=
P
w∈Ni (y) degree(w) can be at distance i + 1, since all nodes at distance i + 1 must have at least one
neighbor at distance i from y. Thus, all remaining nodes have to be at distance at least i + 2. Based
on this observation, we can define the following upper bound on c(y):
P
X
r(y) − ij=1 nj − ñi+1
1
ñi+1
c̃(y) :=
+
+
,
(1)
d(y, z) i + 1
i+2
z:d(y,z)≤i

where the first term in the sum accounts for the nodes for which we computed the exact distance, the
second term assumes that exactly ñi+1 nodes are at distance i + 1, and the third term assumes that
all remaining nodes are at distance d + 2 (see Figure 1). Notice that the more nodes are visited during
the BFS, the tighter the bound is (if all nodes are visited, c̃(y) = c(y)). Thus, the NBCut algorithm
(Algorithm 1 in Appendix A) works as follows: assume that we already computed the exact closeness
for at least k nodes, and let xk be the k-th highest closeness value found so far. While running a BFS
from node y, we compute the bound of Eq. (1). If at some point c̃(y) < xk , we can interrupt the search
from y, since y cannot be one of the top-k nodes. We call the distance i at which we interrupt the BFS
the cutoff distance, and we refer to it as dcut (y). Also, we refer to this extended BFS that computes
c̃(y) and returns when c̃(y) < xk as BFScut (Line 6). If the exact closeness c(y) is actually larger than
xk , we run a complete BFS and replace the current k-th node with highest closeness with y (and set
isExact(y) to true in Line 6). Clearly, the order in which the nodes are processed is very important:
ideally we would like to process them in order of decreasing closeness. In [3], the authors show that a
measure based on the number of walks (the ordering O in Algorithm 1) works quite well.
Notice that Eq. (1) requires the number r(y) of nodes reachable from y. In undirected graphs, this
is the size of the connected component of y, which can be easily computed in a preprocessing step.
In directed graphs, the authors of [3] propose an upper bound based on a topological sorting of the
strongly-connected-components DAG (SCC DAG).
NBBound Algorithm for Street Networks. NBBound initially computes an upper bound c̃ on the
closeness of each node and enters the nodes into a priority queue Q, sorted by their value of c̃ (Line 1
of Algorithm 2 in Appendix A). Notice that this is unrelated to the c̃ computed by BFSCut (see [3]
for more details). Then (Lines 4-10), the node v with highest c̃ is extracted and its actual closeness
c(v) is computed using the BFSbound function. In addition to computing the exact closeness of v, this
function also modifies the upper bounds c̃ of the other nodes. In particular, let w and y be any two
nodes visited during the BFS from v. Then, it can be proven [3] that d(w, y) ≥ |d(v, w) − d(v, y)|. By
assuming that d(w, y) = |d(v, w) − d(v, y)|, ∀w, y ∈ V , we get an upper bound on the closeness of all
nodes. If, for some node w, this upper bound is tighter than the current c̃, then c̃ and the priority of
w in Q are updated. The algorithm terminates when k nodes are found such that their exact closeness
is higher than the upper bound on the closeness of the other nodes (Line 12).

3

Dynamic Top-k Closeness Centrality

Let us assume an edge (u, v) has been inserted into or deleted from the graph. Our goal is to update the
list of the top-k nodes and their closeness values faster than computing it from scratch with NBCut or
NBBound. In the following, we first show how we update the number of reachable nodes (Section 3.1)
and compute the set of affected nodes (Section 3.2), which is a preprocessing necessary for both edge
insertions and deletions. Then, we consider edge insertions and deletions separately in Section 3.3 and
Section 3.4.
5

October 4, 2017, 0:52

3.1

3 DYNAMIC TOP-K CLOSENESS CENTRALITY

Updating the Number of Reachable Nodes

The upper bound in Eq. (1) requires the number of reachable nodes r(u) (or an upper bound on r(u)).
For undirected graphs, this is simply the number of nodes in the connected component of u. Instead of
recomputing connected components from scratch after each update, we use a simple dynamic algorithm
similar to the one presented in [11]. Initially, we build a spanning forest of G. When an edge (u, v) is
inserted, we check whether u and v belong to the same component and if not, we merge the components
and (u, v) becomes part of the forest. If we delete an edge (u, v) that is part of the forest, we then
run a pruned BFS from u and interrupt it as soon as we hit v (and, if we do not hit v, we split the
components). If, in turn, we delete an edge (u, v) that is not part of the spanning forest, we know
there has to be another path between u and v and we are done.
For directed graphs, we mentioned in Section 2.3 that a bound based on a topological sorting of the
SCC DAG was proposed in [3]. Since preliminary experiments showed that recomputing this after each
update was a bottleneck for the dynamic algorithm, we replace this bound with the number of nodes
in the weakly-connected component. This does not affect the correctness of the algorithm and can be
updated much more efficiently using basically the same algorithm we use for updating the connected
components in undirected graphs (we simply need to ignore the direction of the edges).

3.2

Finding Affected Nodes

When an edge (u, v) is inserted or deleted from G, some nodes might increase or decrease their closeness
centrality. We call such nodes affected. More precisely, the set A of affected nodes is defined as
A := {y ∈ V : ∃w ∈ V such that d0 (y, w) 6= d(y, w)}. It is easy to see that, if d0 (y, w) 6= d(y, w), then
either d0 (y, u) 6= d(y, u) or d0 (y, v) 6= d(y, v). Indeed, if the distances from y to both u and v stay the
same, it means that the insertion or deletion of (u, v) does not move any node up or down the BFS
DAG rooted in y. Thus, the set of affected nodes can be easily identified by running two BFSs from u
(one on G and one on G0 ) and two BFSs from v (one on G and one on G0 ). If the graph is directed, the
BFSs have to be run on G and G0 transposed, since we are interested in the nodes that change their
distance to u or v. Once we know all the distances to u and v in G and G0 , we can simply compare
them and mark all nodes y such that d0 (y, u) 6= d(y, u) or d0 (y, v) 6= d(y, v) as affected.
We know that the closeness of all unaffected nodes v does not change. Therefore, the previously
computed upper bound c̃ and, if it was computed, the previous exact closeness value c(v) are still valid.

3.3

Update after an edge insertion

We first focus on updating the NBCut top-k closeness algorithm. Before the insertion, we assume
that, for each node y, we know c̃(y), dcut (y) and isExact(y) computed by the function BFScut. Also,
we assume the nodes are sorted by their c̃ value in a priority queue Q. After an insertion, affected
nodes increase their closeness. One first simple strategy would be to run BFScut from each affected
node, using as xk the current node with the k-th highest closeness. This would already save some time
compared to the static algorithm, since no work is performed for unaffected nodes. In the following, we
propose some further improvements. Algorithm 3 in Appendix A shows the pseudocode of the dynamic
algorithm. Initially, Line 1 and Line 2 update the number of reachable nodes and compute the set
A of affected nodes, as described in Section 3.1 and Section 3.2, respectively. Then (Lines 3-8), the
affected nodes that are among the top k are removed from TopK. For each affected node y, Lines 10-16
try to efficiently update c̃, in order to avoid a new BFScut (as we will see in the following). If this is
not possible, Lines 17-28 run BFScut and update TopK as in the static algorithm.
Skipping Far-away Nodes. Let y be an affected node such that isExact(y) is false, i.e., a node
for which BFScut has been interrupted at some cutoff level dcut (y). W.l.o.g., let us assume that
6

3 DYNAMIC TOP-K CLOSENESS CENTRALITY

October 4, 2017, 0:52

d(y, u) < d(y, v) if G is undirected. We recall that we know d(·, u) from the identification of the
affected nodes described in Section 3.2.
If d(y, u) > dcut (y) and r0 (y) = r(y), the upper bound c̃(y) is still valid. Figure 2 (left) shows this
case. The reason for this is that u has not been visited by BFScut and therefore the existence of edge
(u, v) does not affect the bound in Eq. (1). If d(y, u) > dcut (y) but r0 (y) 6= r(y) (i.e., the insertion
has increased the number of nodes reachable from y), we can simply replace r(y) with r0 (y) in Eq. (1),
r0 (y)
obtaining c̃0 (y) = c̃(y) − dcutr(y)
(y)+2 + dcut (y)+2 . If c̃(y) < xk , y can therefore be skipped and no BFScut on
G0 has to be run from it. We call such nodes far-away nodes (Line 11 of Algorithm 3 in Appendix A).
Skipping Boundary Nodes. If d(y, u) is equal to dcut (y) (Figure
P 2, right), the bound in Eq. (1)
is affected, as the degree of u changes (we recall that ñi+1 :=
w∈Ni (y) degree(w)). In particular,
ñ0dcut (y)+1 after the insertion is equal to ñdcut (y)+1 + 1, since the degree of u has increased by one. Thus,
we can easily compute the new bound from the old one without running a new BFScut from y as follows
(we use dcut instead of dcut (y) for simplicity):
P cut
Pdcut
0
nj − ñdcut +1
r(u) − dj=1
ñdcut +1 + 1 r (u) − j=1 nj − ñdcut +1 − 1
ñdcut +1
0
c̃ (y) − c̃(y) =
+
−
−
dcut + 1
dcut + 2
dcut + 1
dcut + 2
0
r(y) − r (y) + 1
1
−
.
=
dcut + 1
dcut + 2
Boundary nodes are handled in Line 13 of Algorithm 3 in Appendix A.
Distance-based Bounds. The improvements described in the previous two paragraphs do not apply
to affected nodes y for which d(y, u) < dcut (y). Let z be any node such that d0 (y, z) < d(y, z) (if y
is affected, there has to exist such a node). Since all new shortest paths have to go through (u, v)
(and thus through u), we can write d0 (y, z) as d0 (y, u) + d0 (u, z) = d(y, u) + d0 (u, z), since the distance
from y to u cannot change as a consequence of the insertion of (u, v). As for d(y, z), there are
two options: either u was part of a shortest path from y to z also before the insertion – and thus
d(y, z) = d(y, u) + d(u, z), or there was a shorter path from y to z not going through u – and therefore
d(y, z) < d(y, u) + d(u, z). In both cases, we can say that d(y, z) ≤ d(y, u) + d(u, z). Putting this
1
1
1
1
together, we get d0 (y,z)
− d(y,z)
≤ d(y,u)+d
0 (u,z) − d(y,u)+d(u,z) . Thus:
c0 (y) − c(y) =
≤
≤

X

z∈V

X

z∈V

diam
X
i=1

1
1
−
d0 (y, z) d(y, z)



1
1
−
0
d(y, u) + d (u, z) d(y, u) + d(u, z)



(2)


1
n0i (u) − ni (u)
i + d(y, u)

where diam is the
of G. Notice that Eq. (2) implies that, if c̃(y) is an upper bound on c(y), then
Pdiameter
diam
1
0
c̃ (y) := c̃(y) + i=1 i+d(y,u) (n0i (u) − ni (u)) is an upper bound on c0 (y). The values (n0i (u) − ni (u))
can be easily computed with one BFS from u in G and G0 (this can also be combined with the BFSs
we run to identify the affected node, see Section 3.2). Then, for each affected node that is neither
a boundary node nor a far-away node, we compute a new upper bound as in Eq. (2). If this is still
smaller than xk , no BFScut has to be performed from the node. Notice that the computation of the
new bound requires Θ(diam) operations. Since the diameter in complex networks is very small (often
assumed to be constant), this is much faster than running a BFScut, which can take up to Θ(n + m)
7

3 DYNAMIC TOP-K CLOSENESS CENTRALITY

October 4, 2017, 0:52

y

y

Exact

Exact
u

dcut
u

dcut
v

v

Figure 2: Left: u and v are far-away nodes for y. Right: u is a boundary node.
time. The distance-based bounds are computed in Line 15 of Algorithm 3. In Line 16, we set dcut (y)
to diam to indicate that the current bound is not a result of a BFScut and should not be used in the
future to skip far-away or boundary nodes.
Updating NBBound. So far we described how to update top-k closeness assuming that NBCut has
been run on the initial graph. We recall that NBBound only runs complete BFSs, until we find k
nodes whose closeness is higher than the upper bounds on the remaining nodes. Thus, there is no
cutoff threshold that we can use to skip far-away or boundary nodes. However, we can still make some
considerations. First, also in this case c(y) and c̃(y) of unaffected nodes are still valid and do not need
to be changed. Also, the distance-based bounds described in the previous paragraph can be applied to
NBBound as well. If there are nodes y whose new bound is higher than the k-th highest closeness value,
we run a BFS from y. We stop when there is no affected node left whose c̃ is higher than TopK[k],
similarly to the static algorithm. Algorithm 4 in Appendix A shows the pseudocode.

3.4

Update After an Edge Deletion

In some sense, edge deletions are easier to handle than edge insertions. Indeed, since closeness can
only decrease as a consequence of a deletion, nothing needs to be done in case none of the top-k nodes
is affected (whereas for insertions there could be nodes that increase their closeness and “overtake”
the previous top k). Also, notice that for affected nodes the previous upper bounds are still valid
(although they might be less tight). If for some affected node y we know the exact closeness c(y)
before the insertion, this becomes now an upper bound on the closeness of y in the new graph (thus,
we set isExact(y) to true).
Once this is done, the algorithm goes through the nodes in Q ordered by c̃. If we find some node
y for which isExact(y) = false, then we compute its new c0 (y) and update its priority in Q. We stop
when isExact is true for the first k nodes in Q. Notice that this approach works for both NBCut and
NBBound. Algorithm 5 in Appendix A shows the pseudocode for deletions, based in NBCut. The one
based on NBBound is basically the same, with the difference that in Line 14 we do not run a BFScut,
but a BFSbound, as in Algorithm 2.

3.5

Running Times and Memory Requirements

The update of the number of reachable nodes described in Section 3.1 takes O(n + m) in the worst
case – the time to run a BFS from scratch. Computing the set of affected nodes takes Θ(n + m) time,
since we need to run a BFS from u in G and G0 (in the graph is undirected, also from v). Then,
the algorithms described in Section 3.3 and Section 3.4 have to run, in the worst case, a BFScut (or
8

4 EXPERIMENTS

October 4, 2017, 0:52

BFSbound, if we are considering the algorithm based on NBBound) for each affected node. Since the
worst-case running time of both BFScut and BFSbound is O(n + m) [3], in the worst case the running
time of the dynamic algorithms is O(|A|(n + m)), where |A| is the number of affected nodes. However,
we will see in Section 4 that the number of calls to BFScut is usually a small fraction of the total
number of affected nodes (which is, in turn, often only a small fraction of the total number of nodes).
Concerning memory, our algorithms need to store the bound c̃(y), isExact(y), the number r(y) of
reachable nodes and the cutoff distance dcut (y), for each v ∈ V (as well as the list TopK with the k
nodes with maximum closeness). This requires only Θ(n) memory, which is asymptotically the same
as the static top-k algorithms.

4
4.1

Experiments
Experimental Setup

Data sets. We test our algorithms on numerous directed and undirected real-world complex networks
(e. g., social networks or web graphs) and street networks. All of them can be retrieved from the public
repositories SNAP (snap.stanford.edu), LASAGNE (lasagne-unifi.sourceforge.net), KONECT
(konect.uni-koblenz.de/networks) and GEOFABRIC (download.geofabrik.de); the graphs are
listed in Tables 1, 2 and 3 in Appendix B. Since the street networks in Table 3 are all directed, we also
consider an undirected version of them, by ignoring the direction of edges. For each tested graph, we
either add or remove 100 edges one at a time and run the dynamic algorithm after each update. Due
to time constraints, we only run the static algorithm once every 10 updates (this does not affect results
considerably, since the running time of the static algorithm is always approximately the same). For
edge insertions we remove 100 random edges from the original graph before running the algorithms,
and then add them one-by-one, whereas for removals we just delete 100 random edges.
Implementation and settings. Since NBCut outperforms NBBound on complex networks, we only
use NBCut and the new dynamic algorithm based on it (Algorithms 3 and 5 in Appendix A) for our
experiments on complex networks. Similarly, we only use NBBound and the dynamic algorithm based
on it for our experiments on street networks (Algorithm 2 in Appendix A). We recall that our dynamic
algorithm for directed graphs uses the number of nodes in the weakly connected components instead of
the bound originally proposed in [3]. However, for the static case, we use the original bound, in order
to make a fair comparison with previous work. We recall that all algorithms are exact, i.e., they find
the k nodes with highest closeness and their exact scores, so they only differ in their running time and
not in the results they find.
The machine we used for our experiments is a shared-memory server equipped with 256 GB RAM
and 2 x 8 Intel(R) Xeon(R) E5-2680 cores at 2.7 GHz of which we use only one since we executed our
algorithms sequentially (i. e., using a single thread). The code has been written in C++ and uses the
open-source NetworKit framework [24]. We plan to publish our code in future releases of the package.

4.2

Speedups on Recomputation

Dynamic Complex Networks. First, we study the effect of the optimizations proposed in Section 3.3. Table 5 in Appendix B.2 contains the average number of affected nodes over the tested edge
insertions and the percentage of nodes skipped due to each of the optimizations in undirected graphs
(results for k = 10). The average number of affected nodes is never higher than 34% of the total
number of nodes. Also, in all graphs, skipping far-away nodes allows us to ignore the vast majority of
affected nodes after an update. Combined with the cheap updates for boundary nodes and applying
the distance-based bounds, we need to run a new BFScut for less than 1% of the affected nodes on
9

4 EXPERIMENTS

October 4, 2017, 0:52

most graphs. Notice that the column BFScuts contains the percentage of affected nodes for which we
run a new BFScut. The percentage of the total number of nodes is therefore much smaller. Table 4
in Appendix B.2 shows the results for the directed case. Compared to undirected graphs, insertions
typically affect smaller portions of the graph (average values at most ≈ 7%). Among them, usually
a smaller percentage (compared to undirected graphs) are far-away nodes, probably because mostly
nodes that are very close to the inserted edge are affected. However, several nodes are skipped because
of the distance-based bounds, resulting in a very small number of BFSs. The highest numbers are for
p2p-Gnutella08, for which the BFScuts are ≈ 31% of the affected nodes and ≈ 1.5% of the total.
The speedups (ratio between the running times) of our dynamic algorithm on the static one for
complex networks are summarized in the lower part of Figure 3. Table 6 and Table 7 in Appendix B.3
report the detailed values for insertions in directed and undirected graphs, respectively. For undirected
networks, the geometric mean of the speedups (over the 100 edge insertions) are always at least in the
double-digit range (with the only exception of Mus_musculus, where the average speedup for k = 1
is 8.4). Also, the speedups grow for bigger values of k, reaching an average speedup (over all tested
undirected networks) of 123 for k = 100. Although for directed graphs the average speedups vary a lot
(from ≈ 10 for as-caida20071105 to ≈ 3368 for web-Stanford, for k = 1), the results are mostly even
better than for the undirected case: the average speedups over all tested networks are 62 for k = 1,
93 for k = 10 and 174 for k = 100. This can be explained by the smaller number of affected nodes in
directed networks (see Tables 5 and 4 in Appendix B.2).
Tables 8 and 9 in Appendix B.3 show the results for edge deletions (on directed and undirected
graphs, respectively). Interestingly, deletions are mostly faster than insertions for directed graphs,
whereas they are usually slower in the undirected case. For most shortest-paths based problems insertions are easier than deletions: for example, pairwise distances can be updated in time O(n2 ) after an
edge insertion, but not after an edge deletion [10]. In our case, we know deletions can only decrease
centrality. Thus, all previous upper bounds on the centralities are still valid and, if none of the top-k
nodes is affected, nothing needs to be updated. In insertions, on the contrary, any affected node could
increase its centrality and become one of the top-k. If the number of affected nodes is small (as it is
usually the case for directed graphs, see Table 4), it is quite unlikely that a top-k node is among the
affected ones. This happens much more often in undirected graphs, where a larger number of nodes
is often affected. As for insertions, the speedups increase with k: for directed graphs, the geometric
mean of the speedups is 74 for k = 1, 160 for k = 10 and 314 for k = 100, whereas for undirected
graphs it is 12.5 for k = 1, 25.8 for k = 10 and 50.2 for k = 100. All detailed running times for both
insertions and deletions can be found in Appendix B.4.
Dynamic Street Networks. The four tables in Appendix B.5 show the speedups for street networks,
for both edge insertions and deletions, on directed and undirected graphs. Figure 3 summarizes all
results for both complex and street networks (the results for street networks are in the upper part
of the figure). As for complex networks, speedups in street networks are considerably higher in the
directed case. However, differently from complex networks, speedups generally decrease as k increases.
In this respect, notice that the running times of the static algorithm (Appendix B.6) do not change
considerably for different values of k (at least, compared to most complex networks). On the other
hand, if k is larger, it is also more likely that some of the affected nodes is either among the top-k
or overtakes one of the top-k, slowing down the dynamic algorithm. Nevertheless, even for k = 100,
the dynamic algorithm is on average ≈ 49 times faster than recomputation for insertions in undirected
street networks and ≈ 242 times in directed street networks. The results for deletions are even better:
≈ 67 in the undirected case and ≈ 519 in the directed one. The results are significantly better for
k = 1, reaching an average speedup of ≈ 848 for edge deletions in directed graphs, and ≈ 187 in
undirected graphs.

10

5 CONCLUSIONS

October 4, 2017, 0:52

k=1
k = 10
k = 100

Street

Deletions
Undirected
Deletions
Directed
Additions
Undirected
Additions
Directed

Complex

Deletions
Undirected
Deletions
Directed
Additions
Undirected
Additions
Directed

0

100

200

300

400

500

600

700

800

900

Geometric mean of the speedups

Figure 3: Geometric mean of the average speedups over all tested networks, for different values of k.
The upper part of the plot shows the results for street networks, whereas the lower part shows the
results for complex networks. Detailed numbers can be found in Appendix B.3 and Appendix B.5.

5

Conclusions

We have developed and implemented fully-dynamic algorithms for top-k closeness centrality, tailored to
both complex and street networks. Using properties of the modified graph, we are able to significantly
reduce the number of operations required to update the most central nodes.
As a result, we achieve high speedups on static recomputation, in line with those obtained by
other dynamic algorithms for related problems (e.g. [14, 4, 5, 13]), confirming the fact that efforts
in developing dynamic algorithms are well spent. Differently from most existing algorithms updating
shortest-paths-based centralities, the techniques we propose use a linear (in the number of nodes)
amount of additional memory. Although storing more information (e.g., the distances computed during
BFScut on the initial graph) might lead to even higher speedups, a quadratic memory footprint would
not allow us to target networks with millions of nodes. An interesting question is whether the memory
requirements of other dynamic algorithms for related problems can be reduced, using similar techniques
as the ones presented in this paper.
Future work includes extension to batch updates, where several edge updates occur at the same time,
and to other centrality measures, such as betweenness. For the latter, a static algorithm for finding
the top-k nodes with highest betweenness has been proposed in [15]. Thus, an interesting research
question is whether this can be further improved and/or efficiently updated in dynamic networks.

11

REFERENCES

October 4, 2017, 0:52

References
[1] A. Bavelas. Communication patterns in task-oriented groups. Journal of the Acoustical Society of
America, 22:725–730, 1950.
[2] E. Bergamini, M. Borassi, P. Crescenzi, A. Marino, and H. Meyerhenke. Computing top-k closeness centrality faster in unweighted graphs. In 2016 Proceedings of the Eighteenth Workshop on
Algorithm Engineering and Experiments (ALENEX), pages 68–80. SIAM, 2016.
[3] E. Bergamini, M. Borassi, P. Crescenzi, A. Marino, and H. Meyerhenke. Computing top-k closeness
centrality faster in unweighted graphs. CoRR, abs/1704.01077, 2017.
[4] E. Bergamini and H. Meyerhenke. Approximating betweenness centrality in fully dynamic networks. Internet Mathematics, 12(5):281–314, 2016.
[5] E. Bergamini, H. Meyerhenke, M. Ortmann, and A. Slobbe. Faster betweenness centrality updates
in evolving networks. In 16th International Symposium on Experimental Algorithms, SEA 2017,
June 21-23, 2017, London, UK, volume 75 of LIPIcs, pages 23:1–23:16. Schloss Dagstuhl - LeibnizZentrum fuer Informatik, 2017.
[6] P. Boldi and S. Vigna. Axioms for centrality. Internet Mathematics, 10(3-4):222–262, 2014.
[7] M. Borassi, P. Crescenzi, and A. Marino. Fast and simple computation of top-k closeness centralities. arXiv preprint arXiv:1507.01490, 2015.
[8] S. Chechik, E. Cohen, and H. Kaplan. Average distance queries through weighted samples in graphs
and metric spaces: High scalability with tight statistical guarantees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015,
volume 40 of LIPIcs, pages 659–679. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
[9] E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Computing classic closeness centrality, at
scale. In Proceedings of the second ACM conference on Online social networks, COSN 2014,
Dublin, Ireland, October 1-2, 2014, pages 37–50. ACM, 2014.
[10] C. Demetrescu and G. F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM,
51(6):968–992, 2004.
[11] D. Ediger, J. Riedy, D. A. Bader, and H. Meyerhenke. Computational graph analytics for massive
streaming data. In Large Scale Network-Centric Distributed Systems, pages 619–648. John Wiley
& Sons, Inc., 2013.
[12] D. Eppstein and J. Wang. Fast approximation of centrality. Journal of Graph Algorithms and
Applications, 8:39–45, 2004.
[13] O. Green, R. McColl, and D. A. Bader. A fast algorithm for streaming betweenness centrality. In
SocialCom/PASSAT, pages 11–20. IEEE, 2012.
[14] M. Kas, K. M. Carley, and L. R. Carley. Incremental closeness centrality for dynamically changing
social networks. In J. G. Rokne and C. Faloutsos, editors, Advances in Social Networks Analysis
and Mining 2013, ASONAM ’13, Niagara, ON, Canada - August 25 - 29, 2013, pages 1250–1258.
ACM, 2013.

12

REFERENCES

October 4, 2017, 0:52

[15] M. Lee and C. Chung. Finding k-highest betweenness centrality vertices in graphs. In C. Chung,
A. Z. Broder, K. Shim, and T. Suel, editors, 23rd International World Wide Web Conference,
WWW ’14, Seoul, Republic of Korea, April 7-11, 2014, Companion Volume, pages 339–340. ACM,
2014.
[16] Y.-s. Lim, D. S. Menasché, B. Ribeiro, D. Towsley, and P. Basu. Online estimating the k central
nodes of a network. In IEEE Network Science Workshop (NSW), 2011.
[17] E. L. Merrer, N. L. Scouarnec, and G. Trédan. Heuristical top-k: fast estimation of centralities in
complex networks. Inf. Process. Lett., 114(8):432–436, 2014.
[18] M. Newman. Networks: An Introduction. Oxford University Press, 2010.
[19] K. Okamoto, W. Chen, and X. Li. Ranking of closeness centrality for large-scale social networks.
In F. P. Preparata, X. Wu, and J. Yin, editors, Frontiers in Algorithmics, Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings, volume 5059
of Lecture Notes in Computer Science, pages 186–195. Springer, 2008.
[20] P. W. Olsen, A. G. Labouseur, and J. Hwang. Efficient top-k closeness centrality search. In
I. F. Cruz, E. Ferrari, Y. Tao, E. Bertino, and G. Trajcevski, editors, IEEE 30th International
Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014, pages
196–207. IEEE Computer Society, 2014.
[21] G. Ramalingam and T. W. Reps. On the computational complexity of dynamic graph problems.
Theoretical Computer Science, 158(1&2):233–277, 1996.
[22] A. E. Sariyüce, K. Kaya, E. Saule, and Ü. V. Çatalyürek. Incremental algorithms for closeness
centrality. In Proceedings of the 2013 IEEE International Conference on Big Data, 6-9 October
2013, Santa Clara, CA, USA, pages 487–492. IEEE, 2013.
[23] A. E. Sariyuce, K. Kaya, E. Saule, and U. V. Catalyurek. Incremental algorithms for network
management and analysis based on closeness centrality. arXiv preprint arXiv:1303.0422, 2013.
[24] C. L. Staudt, A. Sazonovs, and H. Meyerhenke. NetworKit: A tool suite for large-scale complex
network analysis. Network Science, 4:508–530, 2016.

13

A PSEUDOCODES

October 4, 2017, 0:52

A

Pseudocodes

Algorithm 1: NBCut algorithm for top-k closeness centrality in static graphs [3].
Input : A graph G = (V, E)
Output: Top-k nodes with highest closeness centrality
1 TopK ← [ ];
2 r ← computeReachable(G);
3 Define an ordering O on the nodes;
4 xk ← 0;
5 foreach v ∈ V according to the ordering O do
6
(c̃(v), isExact(v ), dcut (v)) ← BFScut(v, xk );
7
if isExact(v) ∧ c̃(v) > xk then
8
TopK.insert(c̃(v), v);
9
if TopK.size() > k then
10
TopK.removeMin();
11
end
12
if TopK.size() = k then
13
xk ← TopK.getMin();
14
end
15
end
16 end
17 return TopK;

Algorithm 2: NBBound algorithm for top-k closeness centrality in static graphs [3].
Input : A graph G = (V, E)
Output: Top-k nodes with highest closeness centrality
1 c̃, Q ← computeBounds(G);
2 TopK ← [ ];
3 for v ∈ V do c(v) = 0;
4 while Q is not empty do
5
v ← Q.extractMax();
6
if |TopK| ≥ k and c̃(v) > TopK[k] then return TopK;
7
c(v) ← BFSbound(v); // This function might also modify c̃
8
add v to TopK, and sort TopK according to c;
9
update Q according to the new bounds;
10 end

14

A PSEUDOCODES

October 4, 2017, 0:52

Algorithm 3: Recomputation of the top-k nodes after an edge insertion (based on NBCut).
Data: G = (V, E), (u, v) ∈
/E
Result: Top-k nodes with the highest closeness in G0 := (V, E ∪ {u, v})
1 Compute r 0 (y) ∀y ∈ V ;
2 Compute the set A of affected nodes, d(·, u), d0 (·, u);
3 xk ← TopK.getMin();
4 forall w ∈ A do
5
if w ∈ TopK then
6
TopK.remove(w);
7
end
8 end
9 foreach y ∈ A do
10
if dcut (y) < d(y, u) ∧ not isExact(y) then
/* y is a far-away node
11
12

13
14

15
16
17

18
19
20
21
22
23
24
25
26
27
28
29
30

c̃0 (y)

← c̃(y) −

r(y)
dcut (y)+2

+

else if dcut (y) == d(y, u) ∧ not isExact(y) then
/* y is a boundary node
c̃0 (y)

← c̃(y) −

r(y)−r0 (y)+1
dcut (y)+2

*/

r0 (y)
dcut (y)+2 ;

+

*/

1
dcut (y)+1 ;

else
/* we compute the distance-based bounds
P
1
0
c̃0 (y) ← c̃(y) + diam
i=1 i+d(y,u) (ni (u) − ni (u));

dcut (y) ← diam;
if c̃0 (y) ≥ xk then
/* we have to run a new BFScut
(c̃0 (y), isExact(y), dcut (y)) ← BFScut(y, xk );
if isExact(y) ∧ c̃0 (y) > xk then
TopK.insert(c̃0 (y), y);
if TopK.size() > k then
TopK.removeMin();
end
if TopK.size() = k then
xk ← TopK.getMin();
end
end
end
end
Set c̃, r, ni to c̃0 , r0 , n0i ;

15

*/

*/

A PSEUDOCODES

October 4, 2017, 0:52

Algorithm 4: Recomputation of the top-k nodes after an edge insertion (based on NBBound).
Data: G = (V, E), (u, v) ∈
/E
Result: Top-k nodes with the highest closeness in G0 := (V, E ∪ {u, v})
1 Compute the set A of affected nodes, d(·, u), d0 (·, u);
2 forall w ∈ A do
3
if w ∈ TopK then
4
TopK.remove(w);
5
end
6 end
7 Q ← ∅;
8 foreach y ∈ A do
/* we update the bounds on the affected nodes
*/
Pdiam
1
0
0
9
c̃ (y) ← c̃(y) + i=1 i+d(y,u) (ni (u) − ni (u));

10
11
12

13
14
15
16
17
18

insert y into Q with priority c̃0 (y);
end
while Q is not empty do
y ← Q.extractMax();
if |TopK| ≥ k and c̃(y) > TopK[k] then return TopK;
c(y) ← BFSbound(v); // This function might also modify c̃
add y to TopK, and sort TopK according to c;
update Q according to the new bounds;
end

16

A PSEUDOCODES

October 4, 2017, 0:52

Algorithm 5: Recomputation of the top-k nodes after an edge deletion (based on NBCut).
Data: G = (V, E), (u, v) ∈
/E
Result: Top-k nodes with the highest closeness in G0 := (V, E ∪ {u, v})
Assume: Q = priority queue with nodes sorted by c̃;
1 Compute r 0 (y) ∀y ∈ V ;
2 Compute the set A of affected nodes, d(·, u), d0 (·, u);
3 forall w ∈ A do
4
if w ∈ TopK then
5
TopK.remove(w);
6
end
7
isExact(w) ← false;
8 end
9 xk ← 0;
10 while Q is not empty do
11
y ← Q.extractMax();
12
if |TopK| ≥ k and c̃(y) > TopK[k] then return TopK;
13
if not isExact(y) then
/* We run a new BFScut
14
(c̃0 (y), isExact(y), dcut (y)) ← BFScut(y, xk );
15
end
16
if isExact(y) ∧ c̃0 (y) > xk then
17
TopK.insert(c̃0 (y), y);
18
if TopK.size() > k then
19
TopK.removeMin();
20
end
21
if TopK.size() = k then
22
xk ← TopK.getMin();
23
end
24
end
25 end
26 Set c̃, r, ni to c̃0 , r 0 , n0i ;

17

*/

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

B
B.1

Additional experimental results
Overview of Networks
Graph

Graph
polblogs
p2p-Gnutella08
wiki-Vote
p2p-Gnutella09
p2p-Gnutella06
p2p-Gnutella04
freeassoc
as-caida20071105
p2p-Gnutella31
soc-Epinions1
web-Stanford
web-NotreDame
wiki-Talk
cit-Patents

Nodes

Edges

1224
6301
7115
8114
8717
10876
14213
26475
62586
75879
281903
325729
2394385
3774768

19025
20777
103689
26013
31525
39994
72176
106762
147892
508837
2312497
1469679
5021410
16518948

HC-BIOGRID
Mus_musculus
Caenorhabditis_elegans
ca-GrQc
advogato
hprd_pp
ca-HepTh
Drosophila_melanogaster
oregon1_010526
oregon2_010526
Homo_sapiens
GoogleNw
dip20090126_MAX
ca-HepPh
CA-AstroPh
CA-CondMat
email-Enron
loc-brightkite
gowalla
com-dblp
com-amazon
com-youtube

Table 1: Overview of directed complex networks
used in the experiments.

Nodes

Edges

4039
4610
4723
5241
7418
9465
9877
10625
11174
11461
13690
15763
19928
12008
18772
23133
36692
58228
196591
317080
334863
1134890

10321
5747
9842
14484
48037
37039
25998
40781
23409
32730
61130
148585
41202
118521
198110
93497
183831
214078
950327
1049866
925872
2987624

Table 2: Overview of undirected complex networks used in the experiments.

Graph
maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

Nodes

Edges

22591
31097
54972
61082
80262
91188
96977
237174

27088
31974
56616
63793
82245
101437
103198
243185

Table 3: Overview of street networks used in the experiments.

18

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

B.2

Impact of Optimizations
Graph

affected

% affected

far-away

boundary

dist. bound

BFScuts

39
311
31
426
589
773
323
2076
2895
659
3411
10968
3896
161

3.166%
4.942%
0.440%
5.245%
6.752%
7.108%
2.273%
7.843%
4.625%
0.868%
0.142%
3.891%
1.196%
0.004%

41.084%
42.941%
0.287%
50.895%
60.853%
67.576%
0.000%
87.803%
71.353%
13.611%
96.579%
66.812%
94.599%
0.000%

13.265%
19.577%
0.255%
17.709%
20.203%
17.189%
0.000%
11.912%
13.087%
38.786%
3.306%
12.232%
2.200%
0.000%

36.310%
6.102%
79.355%
12.175%
7.343%
6.639%
95.220%
0.247%
10.360%
20.705%
0.106%
14.690%
3.112%
99.901%

9.342%
31.380%
20.102%
19.220%
11.601%
8.597%
4.780%
0.038%
5.200%
26.898%
0.009%
6.265%
0.090%
0.099%

polblogs
p2p-Gnutella08
wiki-Vote
p2p-Gnutella09
p2p-Gnutella06
p2p-Gnutella04
freeassoc
as-caida20071105
p2p-Gnutella31
soc-Epinions1
wiki-Talk
web-Stanford
web-NotreDame
cit-Patents

Table 4: Impact of optimizations in directed networks for k = 10, averaged over 100 random edge
insertions. The column “affected” contains the average number of affected nodes and “% affected” its
percentage of the total number of nodes. The next three columns report the percentage of affected
nodes that can be skipped for each optimization and the last column the percentage of affected nodes
for which a BFScut has been run.

Graph
HC-BIOGRID
Mus_musculus
Caenorhabditis_elegans
ca-GrQc
advogato
hprd_pp
ca-HepTh
Drosophila_melanogaster
oregon1_010526
oregon2_010526
Homo_sapiens
GoogleNw
dip20090126_MAX
ca-HepPh
CA-AstroPh
CA-CondMat
email-Enron
loc-brightkite
gowalla
com-dblp
com-amazon
com-youtube

affected

% affected

far-away

boundary

dist. bound

BFScuts

598
1556
508
690
281
731
1362
836
1932
1470
692
838
3082
745
795
3026
2097
5973
16581
67781
71059
101963

14.812%
33.762%
10.758%
13.170%
3.784%
7.728%
13.795%
7.872%
17.288%
12.824%
5.054%
5.316%
15.467%
6.204%
4.233%
13.081%
5.716%
10.259%
8.434%
21.377%
21.220%
8.984%

61.555%
62.127%
70.768%
81.017%
58.696%
92.468%
89.968%
85.411%
76.625%
76.226%
93.008%
39.976%
44.315%
77.089%
93.756%
93.658%
93.122%
72.360%
74.731%
92.218%
88.512%
86.257%

8.876%
7.547%
6.794%
7.090%
18.037%
5.731%
5.780%
10.178%
22.486%
22.781%
5.686%
59.204%
11.963%
3.473%
4.596%
5.090%
6.144%
7.362%
1.456%
2.708%
3.888%
12.424%

27.527%
29.682%
21.452%
10.792%
21.496%
1.471%
2.641%
2.483%
0.805%
0.774%
1.003%
0.717%
35.153%
18.230%
1.506%
1.050%
0.665%
19.820%
23.786%
5.044%
7.057%
0.908%

2.043%
0.644%
0.986%
1.101%
1.771%
0.329%
1.611%
1.927%
0.084%
0.220%
0.304%
0.103%
8.569%
1.208%
0.142%
0.202%
0.069%
0.459%
0.026%
0.029%
0.543%
0.411%

Table 5: Impact of optimizations in undirected complex networks for k = 10, averaged over 100 random
edge insertions. The column “affected” contains the average number of affected nodes and “% affected”
its percentage of the total number of nodes. The next three columns report the percentage of affected
nodes that can be skipped for each optimization and the last column the percentage of affected nodes
for which a BFScut has been run.

19

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

B.3

Speedups for Complex Networks
Graph
gmean

k=1
min

max

gmean

k = 10
min

max

gmean

k = 100
min

polblogs
p2p-Gnutella08
wiki-Vote
p2p-Gnutella09
p2p-Gnutella06
p2p-Gnutella04
freeassoc
as-caida20071105
p2p-Gnutella31
soc-Epinions1
web-Stanford
web-NotreDame
wiki-Talk
cit-Patents

41.6
18.9
52.6
37.8
21.4
23.9
433.8
9.6
76.1
11.1
3367.6
50.7
14.5
1699.1

11.3
1.7
2.0
5.8
9.4
9.0
91.2
2.7
16.4
0.1
0.4
12.5
11.1
1127.4

67.5
34.1
85.1
75.5
34.7
35.3
685.8
12.7
194.2
73.8
21500.8
72.3
15.7
1897.9

78.5
32.6
53.1
24.7
26.0
30.6
347.4
14.1
48.0
35.1
3364.7
569.7
43.6
2237.3

1.9
0.7
1.2
1.0
1.4
2.2
1.6
2.1
3.1
0.1
0.6
6.0
6.0
823.2

149.2
268.6
156.0
189.3
210.2
277.6
766.1
19.5
491.8
386.7
28577.8
901.6
51.2
2636.3

146.8
53.7
191.4
45.7
45.8
34.4
403.1
99.3
21.2
84.7
5270.0
1363.2
174.3
2513.0

3.5
1.2
7.2
1.3
1.8
2.4
11.8
3.9
1.1
0.3
0.9
15.2
11.1
365.6

252.4
503.1
298.2
707.7
689.9
804.3
831.6
221.2
1084.7
1284.7
41562.7
2560.3
235.0
3393.6

(geometric) mean

61.9

6.8

118.2

93.9

2.3

362.7

174.7

3.8

922.6

max

Table 6: Speedups on recomputation over 100 edge insertions in directed complex networks, for k ∈
{1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min” and
“max” the minimum and the maximum speedup.

Graph
HC-BIOGRID
Mus_musculus
Caenorhabditis_elegans
ca-GrQc
advogato
hprd_pp
ca-HepTh
Drosophila_melanogaster
oregon1_010526
oregon2_010526
ca-HepPh
Homo_sapiens
GoogleNw
CA-AstroPh
dip20090126_MAX
CA-CondMat
email-Enron
loc-brightkite
gowalla
com-dblp
com-amazon
com-youtube
(geometric) mean

gmean

k=1
min

max

gmean

k = 10
min

37.8
8.4
12.1
25.9
37.5
18.1
30.8
19.3
12.2
16.7
365.4
20.6
31.3
133.1
53.1
35.8
56.0
23.2
15.9
140.1
445.1
11.6
34.6

max

gmean

k = 100
min

6.1
3.6
3.7
8.5
11.8
4.4
3.6
5.3
2.9
3.8
15.6
5.5
8.8
6.8
6.5
9.3
2.0
4.3
3.8
17.6
19.6
2.8

65.3
39.6
17.5
84.3
42.6
26.5
205.9
27.0
19.4
24.1
704.1
26.6
36.9
288.1
645.1
183.8
267.2
33.1
22.1
282.7
1389.8
17.0

42.0
14.0
18.9
39.7
62.1
31.8
36.8
59.6
15.1
22.4
397.6
34.8
798.4
280.1
54.1
50.1
105.9
133.2
142.1
130.4
304.6
505.9

6.2
3.7
3.7
7.2
2.6
3.6
4.7
9.5
2.4
2.9
3.7
6.2
78.8
28.5
6.2
5.0
11.0
2.9
8.4
15.1
8.8
4.1

97.0
101.8
35.9
159.7
108.2
55.2
385.0
156.1
29.5
44.8
3352.4
64.2
1045.3
414.5
1096.5
417.8
442.8
1200.6
257.3
357.3
1853.6
2122.3

79.0
20.5
35.7
53.4
107.4
51.8
54.7
60.2
50.8
80.8
487.0
59.1
886.6
418.4
57.1
94.7
222.6
132.9
936.0
108.7
518.3
479.2

4.9
2.6
2.9
3.4
3.2
3.6
4.4
3.5
2.6
3.4
7.1
4.8
11.4
11.3
9.3
3.3
5.2
5.0
6.7
4.7
9.0
2.0

332.4
358.4
162.6
420.9
268.3
323.1
957.5
272.6
225.4
258.8
972.2
424.8
1452.1
6602.3
1878.0
1458.5
446.8
2028.6
3463.2
766.4
5538.1
3669.0

5.9

77.3

75.7

6.3

265.9

123.3

4.6

790.7

max

Table 7: Speedups on recomputation over 100 edge insertions in undirected complex networks, for
k ∈ {1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min”
and “max” the minimum and the maximum speedup.
20

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

Graph
gmean

k=1
min

max

gmean

k = 10
min

max

gmean

k = 100
min

polblogs
p2p-Gnutella08
wiki-Vote
p2p-Gnutella09
p2p-Gnutella06
p2p-Gnutella04
freeassoc
as-caida20071105
p2p-Gnutella31
soc-Epinions1
web-Stanford
web-NotreDame
wiki-Talk
cit-Patents

43.0
16.6
32.1
36.6
45.0
23.5
373.5
8.6
68.8
41.1
3796.1
58.7
21.6
3717.3

29.7
2.0
28.6
8.4
13.4
8.9
305.6
8.1
10.3
37.0
3711.1
49.6
20.1
2923.6

47.7
31.6
33.9
75.2
53.4
27.4
1412.8
8.8
220.0
43.4
3887.1
69.6
22.8
4394.9

94.7
59.2
61.2
36.1
33.4
63.7
397.8
14.0
132.5
138.6
6019.9
859.7
81.1
6357.6

78.4
0.8
59.1
1.1
1.6
5.2
331.3
12.1
2.9
108.7
4281.5
781.9
75.8
3543.7

102.5
229.6
63.3
182.4
148.9
236.2
1398.6
14.5
652.2
165.0
55778.7
896.5
84.8
7096.1

106.6
114.2
98.2
35.7
145.0
89.7
332.1
154.2
190.4
629.3
9471.6
2353.9
348.4
3472.4

61.2
2.5
32.4
4.3
4.8
7.7
72.2
124.5
7.5
266.8
6989.9
2166.3
335.9
180.5

151.3
523.9
116.7
155.7
614.4
794.0
1683.0
161.9
1585.5
754.6
104810.2
2486.6
366.2
7523.4

(geometric) mean

73.9

38.8

104.3

159.9

40.9

360.5

314.3

62.2

879.0

max

Table 8: Speedups on recomputation over 100 edge removals in directed complex networks, for k ∈
{1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min” and
“max” the minimum and the maximum speedup.

Graph
HC-BIOGRID
Mus_musculus
Caenorhabditis_elegans
ca-GrQc
advogato
hprd_pp
ca-HepTh
Drosophila_melanogaster
oregon1_010526
oregon2_010526
ca-HepPh
Homo_sapiens
GoogleNw
CA-AstroPh
dip20090126_MAX
CA-CondMat
email-Enron
loc-brightkite
gowalla
com-dblp
com-amazon
com-youtube
(geometric) mean

gmean

k=1
min

max

gmean

k = 10
min

8.8
6.0
4.2
17.1
11.1
5.6
12.7
5.6
3.9
4.6
116.8
5.5
9.1
65.6
89.4
13.5
17.1
6.0
4.6
37.3
155.9
3.4
12.5

max

gmean

k = 100
min

1.8
2.9
1.6
1.7
2.4
1.6
1.3
1.6
2.0
2.0
1.0
1.9
2.3
1.1
1.7
2.2
1.3
1.6
2.2
2.7
8.1
1.9

15.2
104.8
6.3
339.4
407.8
6.9
478.3
6.8
5.1
5.9
8902.1
6.5
13.0
4020.2
182.4
470.7
780.5
230.0
5.4
81.6
461.2
4.4

11.3
9.6
6.1
22.6
20.7
8.2
17.2
21.3
4.5
6.1
109.4
9.1
149.5
88.4
81.2
21.4
30.1
40.2
36.2
39.3
99.4
117.4

1.3
2.8
1.5
2.2
1.1
1.4
1.2
1.4
1.7
1.5
1.0
1.2
1.0
1.1
1.4
1.3
7.6
1.1
1.2
2.3
3.0
1.0

24.6
350.2
13.2
576.8
1207.4
14.4
937.3
39.2
7.9
11.3
9336.2
15.8
354.1
5886.6
264.5
996.5
1204.6
2566.3
60.0
101.9
539.6
585.6

24.2
13.9
12.9
39.8
35.9
22.9
27.3
20.3
14.9
20.2
129.7
31.5
164.7
207.8
102.9
47.2
63.5
45.6
336.8
50.3
211.3
156.9

2.4
2.2
1.8
2.4
1.4
1.3
2.0
1.7
1.6
2.4
1.0
1.5
1.1
1.1
1.8
1.8
4.8
1.4
1.3
1.9
9.5
1.1

86.8
679.9
58.8
1679.5
3046.0
86.3
2436.8
69.7
63.1
66.0
12759.1
106.9
507.9
18076.6
487.4
3807.3
3607.3
4319.3
836.0
219.3
1595.0
1029.9

1.9

70.0

25.8

1.5

213.6

50.2

1.8

662.9

max

Table 9: Speedups on recomputation over 100 edge removals in undirected complex networks, for
k ∈ {1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min”
and “max” the minimum and the maximum speedup.

21

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

B.4

Running Times for Complex Networks
Graph
polblogs
p2p-Gnutella08
wiki-Vote
p2p-Gnutella09
p2p-Gnutella06
p2p-Gnutella04
freeassoc
as-caida20071105
p2p-Gnutella31
soc-Epinions1
web-Stanford
web-NotreDame
wiki-Talk
cit-Patents

static [s]

k=1
dynamic [s]

0.0121
0.0148
0.0536
0.0446
0.0242
0.0323
0.2658
0.0416
0.8200
0.8373
207.7361
1.1105
2.9550
351.6200

0.0003
0.0008
0.0010
0.0012
0.0011
0.0013
0.0006
0.0043
0.0108
0.0752
0.0617
0.0219
0.2035
0.2069

k = 10
static[s] dynamic [s]
0.0298
0.1026
0.0969
0.1072
0.1293
0.2238
0.2977
0.0702
2.4506
2.9520
288.4620
13.9541
9.6525
371.7316

0.0004
0.0031
0.0018
0.0043
0.0050
0.0073
0.0009
0.0050
0.0511
0.0840
0.0857
0.0245
0.2212
0.1662

k = 100
static [s] dynamic [s]
0.0586
0.2636
0.1857
0.3640
0.4541
0.8322
0.3493
0.7898
6.0270
12.7048
406.5858
40.1074
43.4118
428.1452

0.0004
0.0049
0.0010
0.0080
0.0099
0.0242
0.0009
0.0079
0.2841
0.1500
0.0772
0.0294
0.2491
0.1704

Table 10: Update times for 100 random edge insertions with k ∈ {1, 10, 100} in directed complex
networks. The columns “static” and “dynamic” contain the average time for the static and dynamic
algorithm, respectively.

Graph
HC-BIOGRID
Mus_musculus
Caenorhabditis_elegans
ca-GrQc
advogato
hprd_pp
ca-HepTh
Drosophila_melanogaster
oregon1_010526
oregon2_010526
ca-HepPh
Homo_sapiens
GoogleNw
CA-AstroPh
dip20090126_MAX
CA-CondMat
email-Enron
loc-brightkite
gowalla
com-dblp
com-amazon
com-youtube

static [s]

k=1
dynamic [s]

0.0317
0.0083
0.0106
0.0270
0.0491
0.0339
0.0705
0.0385
0.0173
0.0233
1.4801
0.0506
0.0810
1.0297
1.6690
0.1445
0.3866
0.2249
0.8203
16.8464
102.1518
3.5802

0.0008
0.0010
0.0009
0.0010
0.0013
0.0019
0.0023
0.0020
0.0014
0.0014
0.0041
0.0025
0.0026
0.0077
0.0314
0.0040
0.0069
0.0097
0.0515
0.1202
0.2295
0.3074

k = 10
static [s] dynamic [s]

k = 100
static [s] dynamic [s]

0.0527
0.0260
0.0217
0.0469
0.1289
0.0708
0.1328
0.2217
0.0263
0.0441
1.5431
0.1228
2.3284
1.4850
2.4519
0.3113
0.6290
2.3622
9.0723
20.9283
118.0336
427.8860

0.1791
0.0976
0.0980
0.1324
0.3229
0.4217
0.3514
0.3956
0.2057
0.2568
2.0807
0.8286
3.3147
4.5794
4.5685
1.1810
1.9659
4.3341
127.8335
44.7540
345.3928
759.7169

0.0013
0.0019
0.0011
0.0012
0.0021
0.0022
0.0036
0.0037
0.0017
0.0020
0.0039
0.0035
0.0029
0.0053
0.0453
0.0062
0.0059
0.0177
0.0638
0.1605
0.3875
0.8458

0.0023
0.0048
0.0027
0.0025
0.0030
0.0081
0.0064
0.0066
0.0040
0.0032
0.0043
0.0140
0.0037
0.0109
0.0800
0.0125
0.0088
0.0326
0.1366
0.4117
0.6663
1.5854

Table 11: Update times for 100 random edge insertions with k ∈ {1, 10, 100} in undirected complex
networks. The columns “static” and “dynamic” contain the average time for the static and dynamic
algorithm, respectively.

22

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

Graph
polblogs
p2p-Gnutella08
wiki-Vote
p2p-Gnutella09
p2p-Gnutella06
p2p-Gnutella04
freeassoc
as-caida20071105
p2p-Gnutella31
soc-Epinions1
web-Stanford
web-NotreDame
wiki-Talk
cit-Patents

static [s]

k=1
dynamic [s]

0.0188
0.0163
0.0527
0.0448
0.0444
0.0307
0.2904
0.0422
0.8146
0.8558
207.5102
1.1191
2.8892
337.1497

0.0004
0.0010
0.0016
0.0012
0.0010
0.0013
0.0008
0.0049
0.0118
0.0208
0.0547
0.0191
0.1339
0.0907

k = 10
static [s] dynamic [s]

k = 100
static [s] dynamic [s]

0.0401
0.1189
0.0995
0.1087
0.1245
0.2646
0.3084
0.0713
2.5231
2.9626
276.8251
13.9595
9.8011
375.2206

0.0580
0.2669
0.1859
0.3623
0.5147
0.8984
0.3455
0.7937
6.1104
12.7745
406.2662
40.1689
43.7422
396.8926

0.0004
0.0020
0.0016
0.0030
0.0037
0.0042
0.0008
0.0051
0.0190
0.0214
0.0460
0.0162
0.1208
0.0590

0.0005
0.0023
0.0019
0.0101
0.0035
0.0100
0.0010
0.0051
0.0321
0.0203
0.0429
0.0171
0.1256
0.1143

Table 12: Update times for 100 random edge deletions with k ∈ {1, 10, 100} in directed complex
networks. The columns “static” and “dynamic” contain the average time for the static and dynamic
algorithm, respectively.

Graph
HC-BIOGRID
Mus_musculus
Caenorhabditis_elegans
ca-GrQc
advogato
hprd_pp
ca-HepTh
Drosophila_melanogaster
oregon1_010526
oregon2_010526
ca-HepPh
Homo_sapiens
GoogleNw
CA-AstroPh
dip20090126_MAX
CA-CondMat
email-Enron
loc-brightkite
gowalla
com-dblp
com-amazon
com-youtube

static [s]

k=1
dynamic [s]

0.0317
0.0086
0.0101
0.0260
0.0492
0.0339
0.0656
0.0410
0.0163
0.0235
1.4666
0.0497
0.0875
1.0323
1.6675
0.1444
0.3726
0.2105
0.8376
16.0662
98.1340
3.6342

0.0036
0.0014
0.0024
0.0015
0.0044
0.0061
0.0051
0.0074
0.0042
0.0051
0.0126
0.0091
0.0096
0.0157
0.0187
0.0107
0.0217
0.0352
0.1825
0.4307
0.6294
1.0569

k = 10
static [s] dynamic [s]

k = 100
static [s] dynamic [s]

0.0496
0.0261
0.0209
0.0443
0.1272
0.0692
0.1278
0.2310
0.0250
0.0445
1.5403
0.1217
2.3516
1.4989
2.4406
0.3036
0.6040
2.3587
9.4024
20.3018
116.4843
427.4117

0.1720
0.0989
0.0950
0.1297
0.3217
0.4139
0.3346
0.4046
0.2009
0.2601
2.1020
0.8283
3.3499
4.6072
4.5202
1.1564
1.9093
4.3993
131.2249
43.8383
349.3862
751.0728

0.0044
0.0027
0.0035
0.0020
0.0062
0.0084
0.0074
0.0109
0.0056
0.0073
0.0141
0.0133
0.0157
0.0170
0.0301
0.0142
0.0201
0.0586
0.2595
0.5169
1.1724
3.6402

0.0071
0.0071
0.0073
0.0033
0.0090
0.0180
0.0122
0.0199
0.0135
0.0129
0.0162
0.0263
0.0203
0.0222
0.0439
0.0245
0.0300
0.0964
0.3896
0.8710
1.6538
4.7879

Table 13: Update times for 100 random edge removals with k ∈ {1, 10, 100} in undirected complex
networks. The columns “static” and “dynamic” contain the average time for the static and dynamic
algorithm, respectively.

23

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

B.5

Speedups for Street Networks
Graph
gmean

k=1
min

max

gmean

k = 10
min

maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

485.9
431.5
162.8
193.9
455.2
438.7
534.3
1181.4

(geometric) mean

412.3

max

gmean

k = 100
min

9.3
2.8
6.7
9.4
8.2
20.7
70.7
86.6

734.5
13250.3
12125.3
6855.9
6440.1
6884.2
14497.9
4154.8

482.7
276.5
159.5
117.3
453.2
519.3
502.0
1257.0

3.7
1.7
2.2
1.2
37.1
11.0
19.2
63.2

883.5
11531.9
15470.6
7589.3
16065.3
14307.0
25484.5
6980.3

584.8
148.1
93.2
70.2
405.8
283.3
153.7
1167.9

10.9
3.2
1.3
3.2
23.7
4.9
7.3
33.3

980.4
15783.5
27578.6
971.1
21588.5
13639.7
28820.4
5929.5

14.2

6191.9

372.5

7.3

9144.8

241.8

6.7

8220.6

max

Table 14: Speedups on recomputation over 100 edge insertions in directed street networks, for k ∈
{1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min” and
“max” the minimum and the maximum speedup.

Graph
gmean

k=1
min

max

gmean

k = 10
min

maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

285.3
110.2
69.1
49.9
86.8
107.1
86.2
220.9

(geometric) mean

108.5

max

gmean

k = 100
min

26.0
1.1
7.0
2.4
16.8
3.9
5.3
9.1

481.6
4115.4
5274.2
4410.2
4434.3
2902.7
5135.8
1318.3

311.2
61.6
37.9
36.2
71.6
130.7
68.1
272.3

17.1
1.7
4.6
4.0
8.2
2.9
20.9
8.5

564.5
4473.0
8756.1
4264.1
6111.2
4338.3
9255.8
2563.5

308.0
36.8
11.2
14.3
55.1
62.3
23.6
218.0

7.6
1.2
2.4
2.3
4.1
2.9
4.0
8.7

663.7
6374.2
13198.3
5294.5
7957.4
8218.3
10407.4
1631.4

5.9

2821.6

90.7

6.2

3950.4

48.8

3.5

4892.4

max

Table 15: Speedups on recomputation over 100 edge insertions in undirected street networks, for
k ∈ {1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min”
and “max” the minimum and the maximum speedup.

Graph
gmean

k=1
min

max

gmean

k = 10
min

maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

740.9
809.5
609.7
332.6
2018.3
688.6
769.2
2049.9

(geometric) mean

847.7

max

gmean

k = 100
min

29.9
0.8
39.4
10.3
165.4
169.2
11.8
288.8

1227.1
12583.8
11082.1
758.7
14889.7
8015.5
14131.3
8574.0

795.1
697.2
382.0
237.9
2333.4
613.3
556.2
2326.7

25.8
0.7
27.4
7.6
78.0
111.1
7.3
150.5

1338.0
13509.7
24102.8
803.2
28155.3
14959.3
34348.3
11610.8

857.4
518.8
214.1
116.0
2098.5
392.5
292.8
1986.6

10.3
0.6
9.2
5.1
25.1
32.7
4.2
39.3

1655.0
18936.6
35979.0
988.9
35160.2
17787.7
46801.4
13917.1

31.1

6084.0

743.4

20.7

9357.4

519.3

9.0

12082.7

max

Table 16: Speedups on recomputation over 100 edge removals in directed street networks, for k ∈
{1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min” and
“max” the minimum and the maximum speedup.
24

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

Graph
gmean

k=1
min

max

gmean

k = 10
min

maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

328.9
123.6
170.5
94.2
399.3
182.1
95.0
334.8

(geometric) mean

187.2

max

gmean

k = 100
min

24.5
0.2
16.3
2.4
26.6
64.0
0.1
36.4

539.9
1795.7
4666.8
4243.1
2919.2
1306.5
4535.5
1314.7

389.2
93.7
57.9
53.2
406.2
144.3
54.0
326.8

23.1
0.2
15.7
3.2
28.4
54.9
0.1
28.8

658.6
4421.8
6926.5
4610.9
4518.0
1521.2
6283.8
1995.2

404.1
55.5
13.8
11.7
347.9
63.0
21.4
244.1

8.9
0.3
6.0
2.4
8.8
18.6
0.1
11.1

806.0
6637.0
11481.9
5920.1
5519.6
2144.7
7672.6
2319.9

5.2

2138.0

135.9

5.2

3076.0

67.2

2.9

4078.9

max

Table 17: Speedups on recomputation over 100 edge removals in undirected street networks, for k ∈
{1, 10, 100}. The column “gmean” contains the geometric mean of the achieved speedups, “min” and
“max” the minimum and the maximum speedup.

B.6

Running Times for Street Networks
Graph
maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

static [s]

k=1
dynamic [s]

0.1959
4.0750
10.2787
6.4567
15.7533
16.3053
32.5222
46.1730

0.0004
0.0094
0.0631
0.0333
0.0346
0.0372
0.0609
0.0391

k = 10
static [s] dynamic [s]
0.2038
4.2421
12.5527
7.0189
15.8417
17.8396
34.8647
52.2209

0.0004
0.0153
0.0787
0.0598
0.0350
0.0344
0.0695
0.0415

k = 100
static [s] dynamic [s]
0.2897
4.0176
18.3544
8.3399
19.8871
20.9484
47.5453
54.7890

0.0005
0.0271
0.1969
0.1188
0.0490
0.0739
0.3092
0.0469

Table 18: Update times for 100 random edge insertions with k ∈ {1, 10, 100} in directed street networks.
The columns “static” and “dynamic” contain the average time for the static and dynamic algorithm,
respectively.

Graph
maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

static [s]

k=1
dynamic [s]

0.1691
2.7337
9.5222
5.4850
7.5368
9.0850
21.6908
17.4890

0.0006
0.0248
0.1377
0.1100
0.0868
0.0849
0.2517
0.0792

k = 10
static [s] dynamic [s]
0.2071
1.8672
11.2397
5.5143
9.2345
10.0963
23.7571
19.3370

0.0007
0.0303
0.2963
0.1524
0.1290
0.0772
0.3488
0.0710

k = 100
static [s] dynamic [s]
0.2508
2.8906
21.6126
7.0543
10.2358
13.6970
38.5866
25.3668

0.0008
0.0786
1.9293
0.4931
0.1858
0.2198
1.6374
0.1163

Table 19: Update times for 100 random edge insertions with k ∈ {1, 10, 100} in undirected street
networks. The columns “static” and “dynamic” contain the average time for the static and dynamic
algorithm, respectively.

25

B ADDITIONAL EXPERIMENTAL RESULTS

October 4, 2017, 0:52

Graph
maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

static [s]

k=1
dynamic [s]

0.2083
3.4412
11.2583
5.8541
19.8018
15.1507
29.0321
43.8422

0.0003
0.0043
0.0185
0.0176
0.0098
0.0220
0.0377
0.0214

k = 10
static [s] dynamic [s]
0.2424
3.6236
12.0275
6.2707
19.9973
14.7942
31.2502
45.3105

0.0003
0.0052
0.0315
0.0264
0.0086
0.0241
0.0562
0.0195

k = 100
static [s] dynamic [s]
0.2888
4.8986
17.9281
7.6060
23.3713
18.3038
42.3123
51.5531

0.0003
0.0094
0.0838
0.0656
0.0111
0.0466
0.1445
0.0260

Table 20: Update times for 100 random edge removals with k ∈ {1, 10, 100} in directed street networks.
The columns “static” and “dynamic” contain the average time for the static and dynamic algorithm,
respectively.

Graph
maldives
faroe-islands
liechtenstein
isle-of-man
equatorial-guinea
malta
belize
azores

static [s]

k=1
dynamic [s]

0.1689
1.8495
9.2484
4.7809
9.2114
8.6663
16.8559
16.5104

0.0005
0.0150
0.0542
0.0508
0.0231
0.0476
0.1775
0.0493

k = 10
static [s] dynamic [s]
0.2073
2.0199
10.2024
5.1547
10.0027
9.1300
18.9041
17.9961

0.0005
0.0216
0.1761
0.0968
0.0246
0.0633
0.3498
0.0551

k = 100
static [s] dynamic [s]
0.2535
3.0493
17.7007
6.6677
12.8164
12.4407
30.4396
23.8098

0.0006
0.0549
1.2800
0.5684
0.0368
0.1975
1.4236
0.0975

Table 21: Update times for 100 random edge removals with k ∈ {1, 10, 100} in undirected street
networks. The columns “static” and “dynamic” contain the average time for the static and dynamic
algorithm, respectively.

26

