# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 4 Experimentation
\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Dataset** & **Network Type** & \(|\mathbf{V}|\) & \(|\mathbf{E}|\) & **avg deg** & \(\mathbf{S}\) & \(\mathbf{D}\) & \(\mathbf{W}\) \\ \hline Caida (cai) & Ethernet & \(3.20\times 10^{4}\) & \(4.01\times 10^{4}\) & 2.51 & \(\circ\) & \(\circ\) & \(\bullet\) \\ \hline Luxembourg (lux) & Road & \(3.06\times 10^{4}\) & \(7.55\times 10^{4}\) & 4.11 & \(\circ\) & \(\bullet\) & \(\bullet\) \\ \hline wgtGnutella (cnu) & Peer2 Peer & \(6.26\times 10^{4}\) & \(1.48\times 10^{5}\) & 4.73 & \(\circ\) & \(\bullet\) & \(\bullet\) \\ \hline Brightkite (bkt) & Location-based & \(5.82\times 10^{4}\) & \(2.14\times 10^{5}\) & 7.35 & \(\circ\) & \(\circ\) & \(\circ\) \\ \hline Erz (Erz) & Railway & \(1.25\times 10^{5}\) & \(4.02\times 10^{5}\) & 6.43 & \(\circ\) & \(\bullet\) & \(\bullet\) \\ \hline Eu-All (eua) & email & \(2.65\times 10^{5}\) & \(4.19\times 10^{5}\) & 2.77 & \(\circ\) & \(\bullet\) & \(\circ\) \\ \hline Epinions (epn) & Social & \(1.32\times 10^{5}\) & \(8.41\times 10^{5}\) & 12.76 & \(\circ\) & \(\bullet\) & \(\circ\) \\ \hline Barabasi-A. (baa) & Synthetic (Power-Law) & \(6.32\times 10^{5}\) & \(1.00\times 10^{6}\) & 3.17 & \(\bullet\) & \(\circ\) & \(\bullet\) \\ \hline web-NotreDame (ntr) & HyperLinks & \(3.26\times 10^{5}\) & \(1.09\times 10^{6}\) & 6.69 & \(\circ\) & \(\circ\) & \(\circ\) \\ \hline Netherlands (nld) & Road & \(8.92\times 10^{5}\) & \(2.28\times 10^{6}\) & 5.11 & \(\circ\) & \(\bullet\) & \(\bullet\) \\ \hline YouTube (ytb) & Social & \(1.13\times 10^{6}\) & \(2.99\times 10^{6}\) & 5.26 & \(\circ\) & \(\circ\) & \(\circ\) \\ \hline Wikitalk (wtk) & Communication & \(2.39\times 10^{6}\) & \(5.02\times 10^{6}\) & 4.19 & \(\circ\) & \(\bullet\) & \(\circ\) \\ \hline Human-Genome (bio) & Biological & \(1.43\times 10^{4}\) & \(9.03\times 10^{6}\) & 1262.94 & \(\circ\) & \(\circ\) & \(\bullet\) \\ \hline AS-Skitter (ski) & Computer & \(1.70\times 10^{6}\) & \(1.11\times 10^{7}\) & 13.08 & \(\circ\) & \(\circ\) & \(\circ\) \\ \hline DBPedia (dbp) & Knowledge & \(3.97\times 10^{6}\) & \(1.29\times 10^{7}\) & 6.97 & \(\circ\) & \(\bullet\) & \(\circ\) \\ \hline Erdős-Renyi (red) & Synthetic (Uniform) & \(1.00\times 10^{4}\) & \(2.50\times 10^{7}\) & 2499.11 & \(\bullet\) & \(\circ\) & \(\bullet\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overview of the used input graphs. The first and second columns reports name of the dataset and type of the corresponding network. Third and fourth columns show number of vertices and arcs of the graph, while the fifth column reports the average vertex degree. The last three columns, namely \(\mathbf{S}\), \(\mathbf{D}\), and \(\mathbf{W}\), respectively, indicate whether the graph is synthetic or real-world and whether it is directed/weighted or not, respectively (\(\bullet\) = true, \(\circ\) = false). Graphs are ordered according to their number of arcs, non-decreasing. and the _average query time_, i.e., the average time for answering a query via the labeling for \(q=10^{6}\) randomly selected pairs of vertices of the graph (in microseconds). This latter step is done both for the sake of correctness, to test that the labelings return the same values of distances, and for evaluating the quality of the labelings updated via the dynamic algorithms, against that of the labeling recomputed via fs-2 hc, as in [26]. In fact, it is known that compact labelings yield better performance in terms of average query times [3]. At the end of the k updates, statistic measures of central tendency and dispersion (e.g., mean, median, interquartile range, standard deviation) are computed for all observed performance indicators. The results of our experimentation are summarized in Table 2, where we compare the running time of queue-2 hc against that of bidir-2 hc and fs-2 hc, respectively, by showing both mean and median values, as central tendency measures.