# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 2 Notation and Background  
In this section, we provide the notation and the background notions that are necessary to introducing the contributions of the paper. In the remainder of the paper, for the sake of simplicity and generality, we consider the most general setting where the graph to be handled is a directed weighted graph \(G=(V,A,w)\), with \(n=|V|\)_vertices_ and \(m=|A|\)_arcs_, such that \(w:A\to\mathbb{R}^{+}\) is a weight function assigning a positive real \(w(u,v)\) to any \(\operatorname{arc}\left(u,v\right)\in A\).  
A _path_\(P_{st}\) in \(G\), connecting two vertices \(s\) and \(t\), is a sequence of arcs \((v_{0},v_{1}),(v_{1},v_{2}),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_{k})\) where \(v_{0}=s\), \(v_{k}=t\), and each consecutive pair of arcs in the sequence shares a common endpoint. We call \(k\) the _length_ of the path itself, i.e., the number of arcs in the sequence. A path is _simple_ if it does not contain self-loops, i.e., if any vertex in the sequence of arcs appears only once. Moreover, we denote by \(w(P)\) the _weight_ of a path \(P\), defined as the sum of the weights of its constituting arcs, i.e., \(w(P)=\sum_{(u,v)\in P}w(u,v)\). A path \(P\), connecting two vertices \(u\) and \(v\), that has minimum weight among all paths in \(G\) between said two vertices is called a _shortest path_ from \(u\) to \(v\). We call \(d(u,v)=w(P)\) the _distance_ from vertex \(u\) to vertex \(v\) in \(G\), which is the weight of a shortest path from \(u\) to \(v\) in \(G\). If such a path does not exist, i.e., vertices are disconnected, then we assume \(d(u,v)=\infty\). Observe that conventionally, in unweighted graphs we have \(w(u,v)=1\) for all \((u,v)\in A\). Therefore, the weight of a shortest path equals its length in these graphs.  
We denote by \(N_{out}(v)\) (\(N_{in}(v)\), respectively) the set of the _outgoing_ (_incoming_, respectively) _neighbors_ of \(v\) in \(G\), that is \(N_{out}(v)=\{u\in V|\{v,u\}\in A\}\) (\(N_{in}(v)=\{u\in V|\{u,v\}\in A\}\), respectively). Clearly, in undirected graphs we have \(N_{out}(v)=N_{in}(v)\) for any \(v\in V\). Furthermore, we denote by \(G^{T}=(V,A^{T},w)\) the _transpose_ of \(G\) where an \(\operatorname{arc}\left(u,v\right)\in A^{T}\) if and only if \((v,u)\in A\), and \(w(u,v)=w(v,u)\). Similarly, we use \(N_{out}^{T}(v)\) (\(N_{in}^{T}(v)\), respectively) to denote the set of the _outgoing_ (_incoming_, respectively) _neighbors_ of \(v\) in \(G^{T}\). A _graph update_ or _modification_ can be either _incremental_, if it is an insertion of a new arc or a decrease in the weight of an existing arc, or _decremental_, if otherwise it is a deletion or an increase in the weight of an existing arc. Please note that insertions/deletions of arcs can be easily modeled as decreases of weights from \(\infty\) to \(w(x,y)\) and vice versa. Notice also that vertex insertions/deletions can be easily modeled as sets of modifications to the corresponding arcs, hence the approaches for handling arc updates can be easily extended to manage vertex insertions/deletions by repeatedly executing them for the set of adjacent arcs. For the sake of clarity, we use \(d_{G}\) to represent the distance function in a given graph \(G\) but we omit subscripts from our notation whenever the meaning is clear from the context.