# Computing Persistent Homology of Directed Flag Complexes
## 2 Results
### Comparisons  
We end this section by comparing the performance of Flagser in homology computations to that of Gudhi, which is recognised as another state of the art computational software package. In doing so we are forced to restrict attention to undirected graphs, since Gudhi is designed to work only with simplicial complexes. In addition, while Flagser takes a directed graph as input and produces the complex in unison with the computation of homology, Gudhi must be given the complex as its input on which it performs its computation. Thus we combine Gudhi with the python package NetworkX which contains state of the art clique finding algorithms for undirected graphs. More specifically, we apply the find_cliques method of NetworkX to get the maximal cliques of the graph and insert these into a Gudhi SimplexTree, and then compute the homology using Gudhi  
Figure 4: Four large datasets taken from the Koblenz Network Collection [11]. (**a**) Social network of YouTube users and their friendship connections, (**b**) friendship data of Facebook users, (**c**) road network of the State of Texas, a node is an intersection between roads or road endpoint and edges are road segments and (**d**) Road network of the State of California. All computations were carried out on an HPC cluster using 256 cores. Furthermore, as NetworkX does not allow for parallel enumeration of cliques, for a fair comparison we only enable Flagser to use a single core. In Table 7 we compare the run time of Gudhi+NetworkX with Flagser. We can see that for small examples such as C. Elegans and BBP layer two the times and memory usage are fairly similar, although Gudhi+NetworkX is a bit faster on BBP layer two. We can also see that Gudhi+NetworkX was faster on the PGP graph, with Flagser not finishing without the max dimension option. Although for this graph we can see that Gudhi+NetworkX required 92 GB of memory, whereas using max dimension with Flagser only required 5.4 GB. For the OpenFlights and SimpleWiki graphs neither Gudhi+NetworkX nor Flagser finished. However, if we use the max dimension option with Flagser we can compute the homology of OpenFlights (up to dimension 6) in under four hours using only 5.2 GB of memory. Similarly, for SimpleWiki if we use both the Approximate and max dimension option, then we can get results in under 24 h, on a graph with over 100k vertices. To provide a more complete picture, we recorded in Table 8 the actual number of columns skipped in each of the computations in Table 7. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Dataset** & **Vertex Count** & **Edge Count** & **Gudhi+NetworkX** & **Flagser** \\ \hline C. Elegans & 279 & 2194 & 1.229 s, 585 MB & 0.705 s, 589 MB \\ BBP Layer 2 & 3416 & 132,309 & 11 s, 919 MB & 145 s, 745 MB \\ BBP Layer 5 & 6114 & 756,107 & DNF & DNF \\ PGP & 10,680 & 24,316 & 3 h 6 min 20 s, 92 GB & 3 h 25 min 46 s, 5.4 GB (MD = 6) \\ OpenFlights & 2939 & 19,256 & DNF & 3 h 45 min 18 s, 5.2 GB (MD = 6) \\ SimpleWiki & 100,312 & 824,968 & DNF & DNF \\ \hline
**Dataset** & **Flagser (Approx. 100,000)** & **Betti Numbers** & **Approx. Betti Numbers** \\ \hline C. Elegans & 0.701 s, 524 MB & [1, 162, 83] & [1, 162, 83] \\ BBP Layer 2 & 129 s, 612 MB & [1, 5290, 106,360, 5] & [1, 5288, 106,381, 5] \\ BBP Layer 5 & 13 h 4 min 45 s, 14 GB & Unknown & [1, 1222, 1427,597, 1133] \\ PGP & 3 h 30 min 32 s, 5.3 B (MD = 6) & [1, 1093, 22, 1] & [1, 1093, 22, 1, 0, 0, 0] \\ OpenFlights & 3 h 37 min 19 s, 5.3 GB (MD = 6) & [24,354, 310, 107, 53, 2, 2,0] & [24,354, 309, 108, 53, 4, 2, 0] \\ SimpleWiki & 15 h 7 min 41 s, 21.0 GB (MD = 6) & Unknown & [304, 125,571, 45,306, 31,866, 10,486, 319, 6] \\ \hline \hline \end{tabular}
\end{table} 
Table 7: A comparison of the run times of Flagser and Gudhi+NetworkX to compute the homology of the undirected flag complex of six undirected graphs. Where DNF denotes the computation did not finish in under 24 h, Approx.