# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 2 Notation and Background
### 2-hop-cover Labeling
Clearly, for each vertex \(u\) that is not reachable from \(v_{k}\) (that cannot reach \(v_{k}\), respectively), we have \(L_{in}(u)^{k}=L_{in}(u)^{k-1}\) (\(L_{out}(u)^{k}=L_{out}(u)^{k-1}\), respectively). It can be proven that the obtained \(L_{n}\) is a 2-hop-cover labeling [7]. It can also easily seen that both methods guarantee that if \(v<u\) in the considered vertex ordering, then both \(u\
ot\in L_{in}(v)\) and \(u\
ot\in L_{out}(v)\), while \(v\) might be in \(L_{in}(u)\) or in \(L_{out}(u)\). This property, called _well-ordering_ property [22], is quite important, as it can be exploited to prove that the computed labeling is _minimal_[7], in the sense that removing any single label entry from the labeling breaks (i.e., induces the violation of) the cover property for at least one pair of vertices of the graph. Formally speaking, the well-ordering property is as follows. **Property 1** (Well-ordered Labeling). : _Let \(L=\{[L_{out}(v)]_{v\in V},\{L_{in}(v)\}_{v\in V}\}\) be a 2-hop-cover labeling of a graph \(G=(V,A)\). Let \(\{v_{1},v_{2},\ldots,v_{n}\}\) be an ordering on the vertices of \(G\). Then \(L\) is well-ordered if, for any \(v_{i},v_{j}\in V\) such that \(v_{i}<v_{j}\) we have that:_  
* \(Q(v_{i},v_{j},L)=d(v_{i},v_{j})\)_;_
* \(v_{j}\
ot\in L_{in}(v_{i})\) _and_ \(v_{j}\
ot\in L_{out}(v_{i})\)_._  
Please note that minimality is a highly desirable property since it has been empirically shown that 2-hop-cover labelings that are minimal and that are computed by considering certain vertex orderings yield excellent practical performance in terms of both preprocessing time, labeling size, and average query times. In particular, it is known that the performance of the methods above heavily depends on the vertex ordering and it has been experimentally observed that the average label size (and the resulting average running time of the query algorithm) decreases by several orders of magnitudes, with respect to random orderings, if vertices are sorted according to a centrality-related measure, like, e.g., vertex degree or (approximations of) betweenness centrality [3; 7; 26]. Moreover, for well-ordered (minimal) labelings, if distinct ids ranging from 0 to \(n-1\) are assigned to the vertices of \(V\) and, for each vertex \(v\in V\), pairs in \(L_{in}(v)\) and \(L_{out}(v)\) are stored in the form of an array and sorted according to said ids, then \(Q(s,t,L)=d(s,t)\) can be effectively implemented as shown in Algorithm 1 to take \(O(|L_{out}(s)|+|L_{in}(t)|)\) worst-case running time (\(|L_{out}(s)|\) and \(|L_{in}(t)|\) denote the number of label entries in the two labels). Given a label, say \(L_{out}(v)\), of a vertex \(v\) stored as above, in what follows we denote by \(L_{out}(v)[i]\) it i-th element and by \(L_{out}(v).size\) its size. ```
Input: Labeling \(L\), queried vertices \(s,t\in V\) Output: Distance \(d(s,t)\) in \(G\)
1i\(\leftarrow\) 0;
2j\(\leftarrow\) 0;
3d\(\leftarrow\infty\);
4 while\(i<L_{out}(s).size\wedge j<L_{in}(t).size\)do
5\((v,\delta_{sv})\leftarrow L_{out}(s)[i]\);
6\((w,\delta_{wt})\leftarrow L_{in}(t)[j]\);
7 if\(v<w\)then
8\(i\leftarrow\) i+ 1;
9 elseif\(w<v\)then
10\(j\leftarrow\) j+ 1;
11 else
12 if\(d>\delta_{sv}+\delta_{wt}\)then
13\(d\leftarrow\delta_{sv}+\delta_{wt}\)
14\(i\leftarrow\) i+ 1;
15\(j\leftarrow\) j+ 1;
16
17 returnd
```  
**Algorithm 1**Query algorithm for minimal well-ordered labelings  
In the remainder of the paper, we will call fs-2 hc the generic preprocessing strategy, described above, that yields well-ordered minimal labelings. Observe that all dynamic algorithms known can be used regardless of the specific preprocessing strategy used to compute the initial labeling of the graph [7; 26]. We will show that the same holds for the new algorithm proposed in this work. More specifically, all dynamic algorithms considered in this paper only need an initial labeling that is well-ordered, and this is guaranteed if fs-2 hc strategies are used.