# Computing Persistent Homology of Directed Flag Complexes
## 2 Results
### Sample Computations
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Dataset** & **Vertices** & **Edges** & **Density** & **Flagser-Count** & **Flagser Homology** \\ \hline BE & 43 & 336 & 18.172 & 0.01 s, & 3.32 MB & 0.08 s, & 3.81 MB \\ GP & 23.6 K & 39.2 K & 0.007 & 0.50 s, & 564.40 MB & 2.09 s, & 569.54 MB \\ IN & 410 & 2765 & 1.644 & 0.04 s, & 3.68 MB & 1.27 s, & 9.13 MB \\ JA * & 198 & 2742 & 6.994 & 49.63 s, & 3.57 MB & 10 h 44 min 3.00 s, & 75.79 GB \\ MQ & 62 & 1187 & 30.879 & 0.09 s, & 3.44 MB & 9.41 s, & 50.22 MB \\ PR & 2239 & 6452 & 0.129 & 0.04 s, & 8.63 MB & 0.07 s, & 9.17 MB \\ FN & 40 & 760 & 47.500 & 2 min 23.26 s, & 3.46 MB & Unfinished in 24 h \\ BB \({}^{\dagger,*}\) & 31.3 K & 7.8 M & 0.793 & 23.76 s, & 1.08 GB & 12 h 15 min 3.00 s, & 52.96 GB \\ BA & 280 & 1911 & 2.437 & 0.00 s, & 3.52 MB & 0.03 s, & 3.84 MB \\ CE & 279 & 2194 & 2.819 & 0.02 s, & 3.55 MB & 0.12 s, & 4.55 KB \\ ER \({}^{\dagger}\) & 31.3 K & 7.9 M & 0.804 & 15.06 s, & 1.08 GB & 1 h 30 min 51.00 s, & 4.98 GB \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Performance of Flagser on a variety of datasets: BE = Windsurfers, GP = Google+, IN = Infectious, JA = Jazz, MQ = Macques, PR = Protein, FN = 19 th step of the Rips filtration of the 40-cycle graph, BB = Blue Brain Project neocortical column, BA = Barabasi–Albert graph, CE = C-Elegans, ER = Erdős-Renyi graph. In all cases density is given as connection probability as percentage. Dataset\({}^{\dagger}\) means that the Approximate function of Flagser was used with approximation parameter 100,000. Dataset\({}^{*}\) means that the homology computation was made on a single core of an HPC cluster. \begin{table}
\begin{tabular}{c c} \hline \hline
**Dataset** & **Persistence** \\ \hline BE & 0.09 s, & 3.91 MB \\ MQ & 11.47 s, & 69.54 MB \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Performance of Flagser computing persistence. The set FN is again an example of how large dimensionality affects computation time. In this case one knows by general theory [14] that the resulting flag complex is a model for the 19-sphere, and so the nontrivial Betti numbers occur only in dimensions 0 and 19, and they are 1 in both. However, due to the size of the complex (\(2^{20}\) 19-simplices and nearly 200 million 9-simplices) we were not able to obtain a homology computation within 24 h.  
In Table 1 two of the computations (see \(\dagger\)) were done by Flagser with Approximation parameter 100,000 (the code stops reducing a column after 100,000 steps). Two computation (see \(*\)) were made on a single core of an HPC cluster to satisfy the high memory requirement. Next, we tested the performance of Flagser with respect to several values of the Approximate parameter. We performed the computation on two graphs: (a) a Blue Brain Project neocortical column reconstruction, denoted above by BB (Tables 3 and 4), and an Erdos-Renyi graph with the same number of vertices and connection probability (Tables 5 and 6). These computations were carried out on a single core of an HPC cluster. Consider for example \(\beta_{4}\). By Tables 3 and 4 the true value is \(\beta_{4}=9821\), since in that case no columns are skipped in \(\delta_{3}\) and \(\delta_{4}\). Thus perfect accuracy is achieved with Approximate parameter 10,000. However, with Approximate parameters 1000 and 100 one has a theoretical error of 42 and 6414 respectively, whereas the actual error is 1 and 77 respectively. In the case of \(\beta_{2}\) we do not know the actual answer. However, since the total number skipped with Approximate parameter 100,000 is 664,884, and the approximate value computed for \(\beta_{2}\) is 14,992,658, the calculation is accurate within less than \(\pm 5\%\). Similarly, \(\beta_{1}\) is computed to be 15,438 with 27 skipped columns, which stands for an accuracy at least as good as \(\pm 0.2\%\).