# Path Algorithms for Contact Sequence Temporal Graphs +
## 3 Results
### Number of Nodes and Edges after Transformation  
In Section 2.1, we computed an upper bound on the number of nodes and edges in OSE, TRG_Wu, TRG_Zschoche, and TRG_Ours. Table 3 gives the actual number of nodes and edges for the datasets used in this paper.  
As can be seen from Table 3, the number of nodes and vertices in TRG_Ours is less than that of the other TRG structures but more than that of OSE for all 12 datasets.  
As noted in Section 2.1.2, the relative number of vertices and edges in TRG_Wu and TRG_Zschoche is very data-dependent. TRG_Zschoche has more vertices and edges than TRG_Wu on the airline dataset. In this dataset, \(w>1\) for all edges. The remaining 11 datasets have \(w=1\) for all edges. TRG_Zschoche has the same number of vertices as TRG_Wu on seven of these 11 datasets and a smaller number on the remaining four;  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Dataset** & \(|V|\) & \(|E|\) & \(|E_{s}|\) & \(|E|/|E_{s}|\) \\ \hline airline & 351 & 599,183 & 5704 & 105.046 \\ arxiv & 28,093 & 9,193,606 & 6,296,894 & 1.46 \\ conflict & 116,836 & 5,835,570 & 4,055,742 & 1.44 \\ digg & 30,360 & 86,203 & 85,247 & 1.01 \\ elec & 7115 & 103,617 & 103,617 & 1 \\ enron & 86,978 & 2,269,980 & 594,912 & 3.82 \\ epin & 131,580 & 840,799 & 840,799 & 1 \\ fb & 63,731 & 1,634,070 & 1,634,070 & 1 \\ flicker & 2,302,925 & 33,140,017 & 33,140,017 & 1 \\ growth & 1,870,709 & 39,953,145 & 39,953,145 & 1 \\ slash & 51,083 & 139,789 & 130,370 & 1.07 \\ youtube & 3,223,585 & 18,750,748 & 18,750,748 & 1 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Description of the datasets used in this paper.  
\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline  & \(|V|\) & \(|E|\) & \(|V|\) & \(|E|\) & \(|V|\) & \(|E|\) \\ \hline airline & & & arxiv & & conflict & \\ \hline OSE & 351 & 599,183 & OSE & 28,093 & 9,193,606 & OSE & 116,836 & 5,835,570 \\ TRG\_Wu & 973,032 & 1,817,451 & TRG\_Wu & 433,412 & 9,759,445 & TRG\_Wu & 6,382,486 & 15,058,791 \\ TRG\_Ours & 472,244 & 1,071,076 & TRG\_Ours & 244,799 & 9,410,312 & TRG\_Ours & 3,308,079 & 9,026,813 \\ TRG\_Zschoche & 2,058,822 & 2,657,654 & TRG\_Zschoche & 433,412 & 9,598,925 & TRG\_Zschoche & 6,378,348 & 12,097,082 \\ \hline \multicolumn{7}{c}{digg} & \multicolumn{3}{c}{elec} & \multicolumn{3}{c}{enron} \\ \hline OSE & 30,360 & 86,203 & OSE & 7115 & 103,617 & OSE & 86,978 & 2,269,980 \\ TRG\_Wu & 172,384 & 233,330 & TRG\_Wu & 205,284 & 303,496 & TRG\_Wu & 2,730,480 & 6,104,766 \\ TRG\_Ours & 98,434 & 154,277 & TRG\_Ours & 103,372 & 199,874 & TRG\_Ours & 1,452,218 & 3,635,220 \\ TRG\_Zschoche & 172,379 & 228,222 & TRG\_Zschoche & 205,284 & 301,786 & TRG\_Zschoche & 2,728,896 & 4,911,898 \\ \hline \multicolumn{7}{c}{epin} & \multicolumn{3}{c}{fb} & \multicolumn{3}{c}{flicker} \\ \hline OSE & 131,580 & 840,799 & OSE & 63,731 & 1,634,070 & OSE & 2,302,925 & 33,140,017 \\ TRG\_Wu & 481,859 & 1,219,172 & TRG\_Wu & 1,448,264 & 3,615,273 & TRG\_Wu & 12,600,099 & 44,358,410 \\ TRG\_Ours & 292,878 & 1,002,097 & TRG\_Ours & 787,863 & 2,358,202 & TRG\_Ours & 7,425,807 & 38,262,899 \\ TRG\_Zschoche & 481,859 & 1,191,078 & TRG\_Zschoche & 1,448,208 & 3,018,547 & TRG\_Zschoche & 12,600,099 & 43,437,191 \\ \hline \multicolumn{7}{c}{growth} & \multicolumn{3}{c}{slash} & \multicolumn{3}{c}{youtube} \\ \hline OSE & 1,870,709 & 39,953,145 & OSE & 51,083 & 139,789 & OSE & 3,223,585 & 18,750,748 \\ TRG\_Wu & 34,814,941 & 77,196,220 & TRG\_Wu & 273,371 & 381,167 & TRG\_Wu & 15,446,056 & 32,249,077 \\ TRG\_Ours & 11,466,331 & 49,548,767 & TRG\_Ours & 157,037 & 245,743 & TRG\_Ours & 10,946,613 & 26,473,776 \\ TRG\_Zschoche & 34,814,941 & 72,897,377 & TRG\_Zschoche & 273,371 & 362,077 & TRG\_Zschoche & 15,446,056 & 30,973,219 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Number of nodes and edges in different data structures.  
TRG_Zschoche has a smaller number of edges than TRG_Wu on all 11 of our datasets with \(w=1\). These results are consistent with Section 2.1.2 analysis.