# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 4 Experimental Results
### Datasets  
Ref. [15] uses datasets from the Koblenz network [22]. These datasets have an (edge) activity that ranges from a low of about 1 to a high of about 3.67, which is rather low. Further, all \(\lambda\) values are 1. The Koblenz datasets are described in Table 1. These datasets are in the form of CSGs where every allowed travel from one vertex to another is a single time instance. To benchmark our algorithm against the shortest paths algorithm of [15] on a wide variety of temporal graphs, we prepared synthetic datasets using the Koblenz graphs as follows:  
1. Obtain the underlying static graph from each Koblenz \(CSG\). For this, we replaced each temporal edge \((u,v,t,\lambda)\) by the static edge \((u,v)\) and eliminated duplicate static edges.
2. Represent the static graph obtained in the previous step as an array adjacency list.
3. On every static edge, we randomly add temporal intervals. The temporal intervals are added using three random variables, number of allowed travel intervals \(I\), duration of each interval \(D\) and the travel time on each interval \(T\). Values are assigned to each of these random variables using a normal distribution around three parameters \((\mu_{I},\mu_{D},\mu_{T})\), respectively. These parameters are the mean values for the normal distribution defining the three random variables \((I,D,T)\), respectively.  
We increase the activity factor in the temporal graph by gradually increasing the value of the parameter \(\mu_{D}\). For each \(ITG\) obtained using the method described above, we obtain an equivalent \(CSG\) to benchmark against the shortest path algorithm of [15]. The synthetic datasets obtained as outlined above are described in Table 2. For the _growth_ dataset, the number of contact sequence edges is too large to accommodate in a 32-_bit_ integer for \(\mu_{D}=20\) and \(\mu_{D}=50\). Therefore, it was infeasible to build a corresponding \(CSG\) and run the algorithm from [15] on it. However, we could still run our algorithm on the \(ITG\) representation; the run times were quite reasonable. Table 3 reports the size of each of the synthetic datasets on disk. As we increase the activity factor of the temporal graph by increasing the \(\mu_{D}\) parameter, the size of the \(CSG\) representation of the graph increases significantly. For example, for the _enron_ dataset, the size of the \(ITG\) is 19.5 MB for \(\mu_{D}=50\), as compared to 10.7 GB for the \(CSG\) representation of the same temporal graph, which is a ratio of approximately 563.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Dataset** & \(|\mathbf{V}|\) & \(|\mathbf{E_{s}}|\) & \(\mathbf{cs-Edges}\) & **Activity** \\ \hline epin & 131.8 K & 840.8 K & 841.3 K & 1 \\ elec & 7119 & 103.6 K & 103.6 K & 1 \\ fb & 63.7 K & 817 K & 817 K & 1 \\ growth & 1870.7 K & 39,953 K & 39,953 K & 1 \\ youtube & 3223 K & 9375 K & 9375 K & 1 \\ digg & 30.3 K & 85.2 K & 87.6 K & 1.02 \\ slash & 51 K & 130.3 K & 140.7 K & 1.07 \\ conflict & 118 K & 2027.8 K & 2917.7 K & 1.43 \\ arxiv & 28 K & 3148 K & 4596 K & 1.45 \\ enron & 87,274 & 320.1 K & 1148 K & 3.58 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Koblenz graph statistics.