Complexes of tournaments, directionality filtrations and persistent homology (Q2240096)

The directed flag complex is a natural simplicial space constructed out of a directed graph (digraph). Its \(n\)-simplices are directed \((n+1)\)-cliques of the digraph, i.e. cliques whose vertices are linearly ordered as dictated by the edge directions. However, this construction raises two problems: while edge orientation dictates which cliques are used in the construction of the complex, once the construction is done, it plays no further role in computations; the directed flag complex does not give a proper topological representation to cliques that are not directed, i.e. those cliques whose vertices are not linearly ordered via the orientation of their edges. The leading idea of this article is to construct a complex out of all possible cliques in the digraph, while preserving partial information that is determined by edge directionality. The construction is that of tournaments. For a non-negative integer \(n\), an \(n\)-tournament is a digraph with no reciprocal edges whose underlying undirected graph is an \(n\)-clique. The paper introduces transitive, semi-regular, and regular tournaments. Tournaments can be considered as standard simplices, since an induced subgraph of a tournament is also a tournament. The paper then constructs a natural family of complexes built out of tournaments, refered to as tournaplexes. A tournaplex is a collection \(X\) of tournaments, such that all subtournaments are also in \(X\). If \(G\) is a digraph, the flag tournaplex associated to \(G\) is the tournaplex \(tFl(G)\), whose \(n\)-simplices are the subgraphs of \(G\) that are \((n + 1)\)-tournaments. The directed flag complex of a digraph, or any ordered simplicial complex is in particular a tournaplex. Various directionality invariants of tournaments are introduced. These directionalities give filtrations, i.e. weight functions on simplices. The paper combines different directionalities to produce bi-filtered persistence modules. This is used to show that there are example digraphs that are not distinguishable by one directionality filtration, but are when bi-filtered. The bi-filtration computes the pointwise homotopy types of the flag tournaplexes. Some upper bounds on values of the directionalities are derived. Distributions of tournaments by directionality in various sample networks are also investigated. As a further application, directionality is used to construct featurisations of different classes of digraphs, the Erdös-Renyi and BlueBrain networks, and it is shown that this approach has better distinguishing capabilities in \(k\)-means clustering experiment as compared to Betti numbers of directed flag complexes.