# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 4 Experimentation  
In this section, we present the experimental study we conducted to assess the performance of queue-2 hc. In particular, we implemented both queue-2 hc, bidir-2 hc and fs-2 hc, and designed a test environment to evaluate all considered algorithms on given input graphs. More in details, among the general approaches that go under the name of fs-2 hc, we implemented the version proposed in [7] where the ordering is fixed during the computation of the labeling, while for bidir-2 hc, we implemented both its two versions, given in [26], and selected the fastest for comparisons. Regarding the vertex ordering, we consider either the degree or an approximation of the betweenness, as in [26]. Specifically, for each graph, for the sake of fairness, we selected the ordering yielding faster preprocessing (and hence the most compact labeling) among the two. Setup and InputsOur entire framework is based on NetworkKit [35], a widely adopted open-source toolkit for implementing graph algorithms and performing various types of network analyses. All code has been written in C++ and compiled with GNU g++ v.7.4.0 (O3 opt. level) under Linux (Kernel 5.3.0-53). Implementations of bidir-2 hc and queue-2 hc are both sequential, while fs-2 hc can exploit core-level parallelism for unweighted instances [8]. All tests have been executed on a workstation equipped with an Intel(r) Xeon(r) CPU E5-2643 v3 3.40 GHz, 128 GB of RAM of type DIMM Synchronous 2133 MHz (0.5 ns), and three levels of cache (384 KiB L1 cache, 1536 KiB L2 cache, 20 MiB L3 cache). As input to our tests, inspired by other studies on the subject [4; 7; 8; 14; 17; 26; 27; 36], we used a large set of both real-world datasets, taken from known publicly available repositories, such as SNAP [37], NetworkRepository [38] and KONECT [39], and synthetic graphs, randomly generated via well-known algorithms for random graph generation, such as the _Erdos-Renyi_ model [40] and the Barabasi-Albert model [41]. We considered both directed/undirected graphs and weighted/unweighted ones. All details of the tested inputs can be found at the corresponding URLs, while sizes and main characteristics are given in Table 1.  
**Experiments. ** To assess the performance of queue-2 hc against bidir-2 hc and fs-2 hc, we performed a set of experimental trials that aim at modeling the real-world scenarios where the studied algorithms are supposed to be employed. Specifically, we assume we are given a time-evolving network, subject to decremental modifications, and we need to mine distances between vertices of the graph. Hence, our experimental setup is as follows: for each input graph we start by computing an initial 2-hop-cover labeling via fs-2 hc. Then, the graph undergoes a sequence of \(k=200\) randomly selected decremental updates (either arc removals or arc weight increases). After each graph modification, we update the labeling (either via bidir-2 hc or queue-2 hc) and measure the computational time required by the dynamic algorithm. Furthermore, we also execute fs-2 hc on the modified graph to recompute a 2-hop-cover labeling from scratch and again measure the required running time. For each of the obtained labelings we measure the _size_, that is the number of label entries,