# Interactive Graph Stream Analytics in Arkouda
## 7 Experiments
### Experimental Results
#### 7.3.2 Performance  
Existing exact triangle counting algorithms show that, for very large graphs, the communication between different computing nodes will consume the majority of the time. Therefore, reducing the total communication, or improving data access locality during triangle counting, are the key factors for improving the final performance. Since our triangle counting method can maintain load balancing and locality, it can achieve a high performance for large graph streams. Our experimental results show that our streaming triangle algorithm displays high locality. These results are provided in Table 5. We calculate all the local data access times and all the remote data access times during the triangle counting procedure. We define the locality access ratio \(LAR=\frac{NL}{NL+NR}\), where \(NL\) is the total number of local accesses and \(NR\) is the total number of remote accesses. For the three sub-sketches--Head, Mid and Tail--we calculate their LAR values, respectively. From the table we can see that, for all cases, the LAR value is larger than 50% and the average LAR value is 74%. This means that, during our triangle counting procedure, most of the data come from local memory. This is the major reason our method can achieve a high performance. To show the speedup of the streaming process, we compare the execution time of the original complete graph triangle counting and the execution time of our sketch method. The experimental results are given in Table 6. From the table we can see that our streaming method uses much less space and runs much faster to estimate the number of triangles in large graph stream with only one pass. Since the experimental time is very long for large graphs, here we just present three different shrinking factors to show the trend. We can see that, for very large graphs, we can use a very large shrinking factor to significantly reduce the processing space, and the absolute speedup is also very high. However, the relative speedup compared with the shrinking factor is a little bit lower. For relatively small graphs, our shrinking factor is also relatively small, so the absolute speedup is also small but the relative speedup is high. Our experimental results show that the speedup will increase almost linearly with the shrinking factor. We also use an even larger graph benchmark, com-Friendster, a network dataset that has 1,806,067,135 edges and 65,608,366 vertices [[https://snap.stanford.edu/data/](https://snap.stanford.edu/data/)]([https://snap.stanford.edu/data/](https://snap.stanford.edu/data/)) (accessed on 20 July 2021), and run it with two locales. When the shrinking factor is 32,768, it will take 44,719.4 s to build the sketch with a maximum of 235,332 KB memory footprint. The triangle counting time is 22,368.2 s. When the shrinking factor is 65,536, it will take 44,593.0 s to build the sketch with a maximum of 235,288 KB memory footprint. The triangle counting time is 22,296.0 s. If we use the exact method, also with two locales, the program will fail because it runs out of memory. This example really shows that our method can handle very large graphs in a limited memory footprint. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multicolumn{1}{c}{**Metrics**} & \multicolumn{2}{c}{**AbsMaxError**} & \multicolumn{2}{c}{**AbsMeanError**} & \multicolumn{2}{c}{**R-Squared**} \\ \hline \multicolumn{1}{c}{**Regression Methods**} & **Ordered** & **Unordered** & **Ordered** & **Unordered** & **Ordered** & **Unordered** \\ \hline \multirow{6}{*}{Shrink Factor} & 4 & 6.76\% & 8.26\% & 2.84\% & 3.75\% & 91.42\% & 85.10 \% \\ \cline{2-8}  & 8 & 6.08\% & 8.89\% & 3.05\% & 4.13\% & 91.59\% & 82.90\% \\ \cline{2-8}  & 16 & 4.16\% & 8.66\% & 1.97\% & 3.64\% & 96.47\% & 87.85\% \\ \cline{2-8}  & 32 & 6.67\% & 10.80\% & 3.02\% & 4.02\% & 90.85\% & 82.73\% \\ \cline{2-8}  & 64 & 4.66\% & 6.68\% & 2.86\% & 3.02\% & 94.12\% & 92.04\% \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison between Ordered and Unordered Regression Models for Power Law Distribution.