# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### Profiling of Algorithm bidir-2 hc
\(h\in H_{b}(x,y)\) and there is a vertex \(u\in N_{out}(v)\) such that: (i) \((h,\delta_{uh})\in L_{out}(u)\); (ii) \(w(v,u)+\delta_{uh}=\delta_{vh}\); (iii) \(u\
ot\in F^{L}_{G}(x,y)\). **Case 1. ** If \(h\
ot\in H_{b}(x,y)\), we have that \(h\) is not a hub vertex for pair \(x,h\) in \(L\). This implies that there exists another hub vertex \(h^{\prime}\) that covers pair \(x,h\) which in turn implies that:

Figure 4: Consider again the graph of Figure 1 and a corresponding 2-hop-cover labeling. Assume \(arc(4,0)\) is removed. We have that vertex \(3\) is in \(F^{L}_{G}(0,1)\) and vertex \(0\) is in \(B^{L}_{G}(0,1)\). However, there is no outdated label entry in \(L_{out}(3)\) but the decremental operation on arc \((4,0)\) causes the cover property to be broken for pair \((3,0)\). * either \(d_{G}(x,h)=d_{G}(x,h^{\prime})+d_{G}(h^{\prime},h)<w(x,y)+d_{G}(y,h)\);
* or \(d_{G}(x,h)=d_{G}(x,h^{\prime})+d_{G}(h^{\prime},h)=w(x,y)+d_{G}(y,h)\) but \(h\) is not hub vertex (that is \(h\) does not belong to \(L_{\mathrm{out}}(x)\)) since \(h^{\prime}\) precedes both \(h\) and \(x\) in the vertex ordering (\(h^{\prime}<h\) and \(h^{\prime}<x\)) and since \(L\) is well-ordered. In both sub-cases we obtain a contradiction, as \((h,\delta_{vh})\) is not outdated (the decremental operation does not change the value of \(\delta_{vh}\)). **Case 2. ** We have that there exists a neighbor of \(v\), namely \(u\), that is not in \(F_{G}^{L}(x,y)\). Hence, its outgoing label, by Property 2, does not contain any incorrect entry and we have \(\delta_{uh}=d_{G}(u,h)=d_{G^{\prime}}(u,h)\) for any \((h,\delta_{uh})\in L_{\mathrm{out}}(u)\). Therefore, as \((v,u)\in A\) and the weight of \((v,u)\) does not change in \(G^{\prime}\), we have that \(d_{G}(v,h)=w(v,u)+d_{G}(u,h)=d_{G^{\prime}}(v,h)\) and thus the label entry \(\delta_{vh}\) is not outdated, which is a contradiction. (\(\Leftarrow\)) Again by contradiction we assume that there is a non-outdated (correct) entry \((h,\delta_{vh})\in L_{\mathrm{out}}(v)\) while \(h\in H_{b}(x,y)\) and there is no vertex \(u\in N_{\mathrm{out}}(v)\) such that: (i) \((h,\delta_{uh}\in L_{\mathrm{out}}(u)\); (ii) \(w(v,u)+\delta_{uh}=\delta_{vh}\); (iii) \(u\
ot\in F_{G}^{L}(x,y)\). Since \(v\in F_{G}^{L}(x,y)\) and \(h\in H_{b}(x,y)\) we know that \(d_{G}(v,h)=d_{G}(v,x)+d_{G}(x,h)=d_{G}(v,x)+w(x,y)+d_{G}(y,h)\). Now, since the entry is correct for \(G^{\prime}\), there must exist another shortest path, say \(P\), in \(G\) that: (i) does not contain \((x,y)\) and such that \(w(P)=d_{G}(v,h)\). Call \(u^{\prime}\) the neighbor of \(v\) on this second shortest path. Since there is no neighbor \(u\) such that \((h,\delta_{uh})\in L_{\mathrm{out}}(u)\) and \(w(v,u)+\delta_{uh}=\delta_{vh}\), it follows that \(h\
ot\)\((h,\delta_{uh})\
ot\in L_{\mathrm{out}}(u^{\prime})\). It follows that pair \(u^{\prime}\), \(h\) is covered by some other vertex, say \(h^{\prime}\), such that \(h^{\prime}<h\) and \(h^{\prime}<u^{\prime}\). Since \((h,\delta_{vh})\in L_{\mathrm{out}}(v)\) we have also that \(h\) must be preceding \(h^{\prime}\) in the vertex ordering (i.e., \(h<h^{\prime}\)) as otherwise the visit rooted at \(h\) would have not reached \(v\) (it would have been pruned thanks to \(h^{\prime}\)). This is a contradiction since for the pruning on \(P\) to happen \(h^{\prime}\) must precede \(h\). An explanatory example of this scenario is shown in Figure 5a. To summarize, Properties 2-3 provide a theoretical basis upon which we design an effective algorithm for removing outdated entries, and for detecting pairs of uncovered vertices in \(G^{\prime}\), as we know that: (i) to find and remove (all and only) outdated entries it suffices to scan labels \(L_{\mathrm{out}}(v)\) (\(L_{\mathrm{in}}(v)\), resp.) of vertices \(v\in F_{G}^{L}(x,y)\) (\(v\in B_{G}^{L}(x,y)\), resp.) and to search for entries in the form \((h,\delta_{vh})\) such that \(h\in H_{b}(x,y)\) (\((h,\delta_{hv})\) such that \(h\in H_{t}(x,y)\), resp.