Hochschild homology, and a persistent approach via connectivity digraphs

Directed graphs, or shortly digraphs, organise a multitude of mathematical objects and physical phenomena; in particular, where an inherent directionality plays a considerable rôle. Prominent examples motivating this paper come from structural brain networks, i.e., (directed) networks modelling the synaptic connectivity in the brain; here the pre- and post-synaptic signal propagation induces directions between neurons. This type of application in neuroscience has particularly ignited the interest in applied topology and topological data analysis (TDA), together with the subsequent development of computational tools (Lütgehetmann et al. 2020; Reimann et al. 2017). For an application in classifying network (brain) dynamics, see the recent work (Conceição et al. 2022). One of the main techniques adopted in TDA is persistent homology (PH), which has been employed not just in neuroscience and neuroimaging (Caputi et al. 2021b; Chung et al. 2014; Khalid et al. 2014; Kuang et al. 2019; Lee et al. 2011), but also in fields like finance (Gidea 2017), fingerprint classification (Giansiracusa et al. 2019), and image classification (Dey et al. 2017), to name a few.

In applications, the classical persistent homology pipeline takes as input a filtered family of undirected graphs. Having in mind the aforementioned examples involving families of digraphs instead, we are interested in persistent homology pipelines for directed graphs; however, in order to extend the classical pipeline to directed frameworks, one needs suitable (co)homology theories of directed graphs. The main goal of this paper is to go beyond structural limitations of existing (undirected) approaches. To do so, we introduce new connectivity frameworks, aiming to capture more combinatorial and homotopical invariants of digraphs, as we now shall describe.

In a primal approach, the persistent homology pipeline for directed graphs would be the following: one starts by constructing suitable simplicial complexes (the directed flag complexesMasulli and Villa 2016; Reimann et al. 2017) associated to the digraphs, computes (most often, homological) features of the simplicial complexes, and finally uses these, or derived features, for subsequent network analysis. Implementations are usually possible, thanks to existing software and algorithms allowing homological computations; e.g., Flagser (Lütgehetmann et al. 2020) has a persistence implementation with directed flag complexes. Even if the simplices in directed flag complexes are constructed using the coherently oriented cliques in the digraphs, the calculation of the associated homology groups reduces to simplicial homology. This has the effect that the associated topological invariants forget some information carried in the directionality of the edges. Besides the directed flag complex approach, many other homology theories of digraphs have been recently used in applications. With the hope that the interested reader might find useful a recollection of some prominent homology theories of digraphs, in Sect. 2 we provide a review of recent advancements. Among others, we give an overview of the recently developed path homology (Grigor’yan et al. 2020)—see Sect. 2.2, and also Chaplin (2022) for a comparison with the directed flag complex of random graphs. A third approach uses Hochschild homology (HH), a homology theory of associative algebras introduced by Hochschild (1945)—cf. Sect. 2.3. There is a standard and coherent way of associating to a directed graph an associative algebra, called the path algebra. Then, application of Hochschild homology to path algebras of digraphs provides additional homological invariants. We refer to Sect. 2.4 for an exposition of other related homological constructions.

In Sect. 3.2, we show that all the described homological approaches cannot tell apart simple examples of non-isomorphic digraphs. This then begs the question about what an appropriate homology theory for digraphs should be, and how to incorporate the directed combinatorics in the theory and applications. Hochschild homology of path algebras is able to capture part of the combinatorial information. Path algebras, in fact, naturally arise from the combinatorics of the directed paths in the digraphs, and Hochschild homology is able to coherently capture such information. If the digraph has an oriented cycle, the path algebra is automatically infinite-dimensional. In the case of acyclic digraphs instead, the dimensions of the Hochschild homology groups, seen as vector spaces over a base field, can be laid down in a simple combinatorial formula. However, also the Hochschild homology of digraphs has some shortcomings. First, the digraph is assumed to be acyclic, which rarely is the case in real networks. Second, the Hochschild homology groups vanish beyond degree 1, and one retrieves no information beyond dimension 1 of the digraph itself.

To remedy the issues raised above, we propose in this paper the following approach: a persistent homology framework applied to a filtered family of digraphs taking into account higher orders of intrinsic connectivities. The main points of the paper follow the scheme below:

From digraphs to connectivity digraphs With the twofold aim of providing and extending persistent homology pipelines to higher degrees, and of capturing combinatorial information intrinsic in the directed structure of directed graphs, we introduce the notion of a connectivity digraph—cf. Definition 3.2. For a digraph \({\mathcal {G}}\), a connectivity graph associated to \({\mathcal {G}}\) is a graph, possibly directed, constructed by using the combinatorics of \({\mathcal {G}}\). For example, connectivity graphs can be described by edges, paths, sets of edges, or by cliques, together with their incidence relations. In Sect. 3 we present two new connectivity structures for simplices. The directed q-analysis extended from the work of Atkin (1972) connects simplices \(\sigma \) and \(\tau \), both of dimension \(\ge q\), if there is a q-dimensional face \(\alpha \) such that \(\widehat{d_i}(\sigma ) \hookleftarrow \alpha \hookrightarrow \widehat{d_j}(\tau )\), where \(\widehat{d_i}\) is an extended face map (see Definition 3.12). The n-path digraph connects n-simplices \(\sigma \) and \(\tau \) if there is an \((n-1)\)-simplex \(\alpha \) such that \(d_i(\sigma ) = \alpha = d_j(\tau )\) with \(i < j\), where \(d_i\) is the standard face map. Both the above connectivity relations define connectivity digraphs.

Hochschild homology for acyclic graphs Application of homologies (simplicial homology, path homology, Hochschild homology) to connectivity digraphs extends the family of homological invariants of digraphs to each \(n\in {\textbf{N}}\). In particular, applying Hochschild homology on connectivity digraphs enables us to admit Hochschild homology groups from degree 1 to n, where n now refers to the dimension of simplices appearing in our connectivity digraphs. A convenient computation of the dimension of Hochschild homology only applies when restricting to acyclic digraphs. In general, this fails to be true, also for our connectivity digraphs. To be able to compute Hochschild-related invariants for general digraphs, we define the Hochschild characteristic (Definition 2.29) which adds to the acyclic formula the component coming from the vector space generated by the simple cycles in the digraph.

Stable persistent Hochschild homology In the case of acyclic digraphs the transformation from the category of digraphs, through connectivity structures, into finite vector spaces via Hochschild homology is functorial. Then, for a given filtration of digraphs, one can apply the usual pipeline to get persistent Hochschild homology groups of digraphs. The categorical framework developed by Bergomi and Vertechi (2020) provides immediately the needed abstract stability theorems. For a filtration \({\mathcal {F}}\) in the category \(\textbf{Digraph}_0\) of digraphs without oriented cycles, the persistent Hochschild pipeline can be illustrated as the following composition of functors:

where \({\mathcal {C}}\) is any functorial construction of connectivity digraphs—cf. Sect. 4.1 and 4.2. In Sect. 4.3, we apply this procedure to a real network, namely the neural network of the C. elegans.

Computational HH and K-theory into applied topology toolbox As far as the authors know, this work is the first in bringing invariants from Hochschild homology into the realm of TDA, to be used as featurisations of common data objects. Our implementation of the above pipeline and computations on the C. elegans indeed demonstrate the applicability of our approach to real-world directed networks. Natural extensions would be using cyclic homology theories and K-theoretic methods. Previous work has focused on computing the K-theory of the category of zig-zag persistence modules (Grady and Schenfisch 2021). In a subsequent work we plan to investigate the extension in the K-theoretic directions as well.

We hope with this work to raise the interest of current developments in applied topology and persistence to focus more on trying to bring unexplored tools from theoretical algebraic topology and K-theory into the applied setting. Based on our work, we believe that a following recipe is useful. First, a fruitful combination of data and invariants needs to be found. For us, this is the combinatorics of (connectivity) digraphs and the path algebras they generate. Standard simplicial persistence is made for finite metric spaces, which we feel is not a natural pairing for digraphs as combinatorial objects without any regard on metric issues. Second, the invariant needs to be computable. In our case, this comes from the known combinatorial formula for the dimensions of Hochschild homologies. Going further, one needs to focus algebraic derivations on proving similar results when these are not yet existing. Third, the main lesson from persistence theory are the stability results. Any new tool in the applied topology toolbox should take into account that small variations in the input data need to be bounded at the level of algebraic invariants and featurisations. As mentioned, our pipeline satisfies certain stability guarantees.

We finish with some perspective on the apparent simplicity of digraphs. Even though graphs and digraphs are simple objects to describe and many concepts in graph theory are rather easy and intuitive to handle, it is the immense possibilities of putting together vertices and edges that gives rise to the actual complexity of graphs/digraphs. One then needs to find an appropriate balance between the objects described and complexity and information content of the invariants attached to them. As a fourth point in the recipe of the previous paragraph, in applications some level of interpretability of the invariants is desired. In standard persistence it is easy to give a geometric meaning to the generators of a barcode. In the case of Hochschild homology it is still maintainable to understand how the information of directed paths is captured. The question of interpretability is of course conditioned on the application domain. For example, in medical applications the outcomes of TDA analyses should have some meaning to, say, prognosis and diagnosis. In machine learning applications topological/algebraic invariants can be accepted more as black box featurisations.

1.1 Conventions

Calligraphic font, as \({\mathcal {G}}\), is used to denote finite graphs (both directed and undirected). All base rings are assumed to be unital and commutative, and algebras are assumed to be unital and associative. Unless otherwise stated, R denotes a ring, \({\textbf{K}}\) is an algebraically closed field, A is a unital associative R-algebra, V is a vector space over \({\textbf{K}}\), and all tensor products \(\otimes \) are assumed to be over the base ring R or base field \({\textbf{K}}\). General references for graph theory, category theory, and algebraic topology are West (2005), MacLane (1971), and Hatcher (2000), respectively.

In this section we review and fix some basic notions related to graphs and simplicial complexes, needed in the follow-up.

2.1 The category of digraphs

A graph is pair \({\mathcal {G}}= (V,E)\) consisting of a set of vertices V and a relation \(E \subseteq [V]^2\). The relation E is the set of edges between vertices and we denote the edges by pairs \(\{v,w\}\). We are interested in graphs with oriented edges:

Definition 1.1

A directed graph, or a digraph, is pair \({\mathcal {G}}= (V,E)\) consisting of a set of vertices V and a subset \(E \subseteq (V \times V)/\Delta _V\), where \(\Delta _V = \{(v,v) \, | \, v \in V\}\). The subset E is the set of directed edges and we denote edges by ordered pairs (v, w).

In this work, unless otherwise specified, graphs and digraphs will always be finite, hence the sets V and E are finite. Note that the definition above defines simple (di)graphs without loops: there are no edges of the form \(\{v,v\}\) nor (v, v) and there is only one edge between any pair of vertices. In the case of digraphs, edges are unique ordered pairs (v, w), and we allow reciprocal edges (v, w) and (w, v) in E. We use the same symbol \({\mathcal {G}}\) for denoting both an (undirected) graph and a digraph. In the rest of the paper we will mainly deal with digraphs, and we will always make clear whether we are referring to a graph or a directed graph.

Definition 1.2

A graph is complete if for every pair of vertices v and w there is an edge \(\{v,w\}\). A digraph is complete if for every pair of vertices v and w there are both edges (v, w) and (w, v). A k-clique of \({\mathcal {G}}\) is a complete subgraph of \({\mathcal {G}}\) on k vertices.

Directed graphs come equipped with source and target maps \(s,t:E\rightarrow V\). For an edge \(e=(v,w)\), the function s maps e to its source, \(s(e)=v\), and t to its target, \(t(e)=w\). Sometimes, when we want to specify the source and target maps, we denote a digraph as \({\mathcal {G}}=(V,E,s,t)\).

Graphs and digraphs have natural notions of morphisms between them; we spell it out in the case of digraphs.

Definition 1.3

A morphism of digraphs from \({\mathcal {G}}_1 = (V_1,E_1)\) to \({\mathcal {G}}_2 = (V_2,E_2)\) is a function

on the vertices such that \((\phi (v),\phi (w))\in E_2\) for every (v, w) belonging to \( E_1\).

Observe that, by Definition 1.3, a morphism of digraphs sends directed edges to directed edges and it does not allow to collapse them. One can also consider functions \(\phi :V_1\rightarrow V_2\) on the vertices such that either \(\phi (v)=\phi (w)\) or \((\phi (v),\phi (w))\in E_2\); we refer to these maps as maps of digraphs. Finite digraphs and edge preserving morphisms of digraphs form a category that we denote by \(\textbf{Digraph}\). By \(\textbf{Digraph}_+\) we denote the category of finite digraphs with possible self-loops on vertices, and maps of digraphs.

Remark 1.4

A morphism of digraphs from \({\mathcal {G}}_1\) to \({\mathcal {G}}_2\) sends complete subgraphs of \({\mathcal {G}}_1\) to complete subgraphs of \({\mathcal {G}}_2\), hence cliques to cliques. Indeed, otherwise a morphism would collapse at least one of the edges in the clique, which is not allowed.

One can consider also more restrictive morphisms, namely morphisms of digraphs that are also injective (as functions of vertices). We will refer to these morphisms as regular morphims of digraphs and denote the resulting category of digraphs (possibly with loops) and regular morphisms by \(\textbf{RegDigraph}\).

Remark 1.5

Both the categories \(\textbf{Digraph}\) and \(\textbf{RegDigraph}\) have an initial object^{Footnote 1}\(\varnothing \), the empty digraph. Note that this is not a terminal object.

The coherently oriented cyclic digraph \(C_n\)

Full size image

An oriented cycle in a directed graph \({\mathcal {G}}\) is an embedding into \({\mathcal {G}}\) of the coherently oriented cyclic digraph \(C_n\) on n vertices—cf. Fig. . In the follow-up, we might need to work with categories of digraphs without oriented cycles; we use the following notation:

Notation 1.6

We denote by \(\mathbf {Digraph_0}\) the subcategory of \(\textbf{Digraph}\) consisting of finite directed graphs without oriented cycles.

A standard construction in graph theory is the so called edge graph, or line graph, \({\mathcal {L}}({\mathcal {G}})\) of a graph \({\mathcal {G}}\). This is defined as the graph consisting of all the edges of \({\mathcal {G}}\) as vertices, with connections described by the incidence relations. The construction generalizes to the case of digraphs—see, for instance, Harary and Norman (1960):

Definition 1.7

The line digraph of a directed graph \({\mathcal {G}}=(V,E,s,t)\) is the directed graph \({\mathcal {L}}({\mathcal {G}})\) whose vertices are the edges of \({\mathcal {G}}\) and two vertices p and q in \({\mathcal {L}}({\mathcal {G}})\) corresponding to the edges \(e_p=(s(e_p), t(e_p))\) and \(e_q=(s(e_q),t(e_q))\) in \({\mathcal {G}}\) are connected by a directed edge \((p,q)\in E({\mathcal {L}}({\mathcal {G}}))\) if \(t(e_p)=s(e_q)\).

Associating a line (di)graph to a (di)graph is coherent with respect to morphisms:

Remark 1.8

There is a functor

which sends a digraph \({\mathcal {G}}\) to its line digraph \({\mathcal {L}}({\mathcal {G}})\). First, note that the line digraph \({\mathcal {L}}({\mathcal {G}})\) of a digraph \({\mathcal {G}}\) is the empty digraph \(\varnothing \) if, and only if, \({\mathcal {G}}\) has no edges. As by Remark 1.5, \(\varnothing \) is an initial but not a terminal object in the category \(\textbf{Digraph}\), the functoriality may fail for morphisms \(\phi :{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\), where \({\mathcal {G}}_2\) has no edges. On the other hand, a morphism of digraphs sends edges to edges and collapsing is not allowed; therefore, either both \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\) have no edges—hence, the induced morphism between the associated line digraphs is the trivial morphism \(\varnothing \rightarrow \varnothing \)—or \(\phi \) induces a morphism of digraphs \({\mathcal {L}}(\phi ):{\mathcal {L}}({\mathcal {G}}_1)\rightarrow {\mathcal {L}}({\mathcal {G}}_2)\) between the associated (non-empty) line digraphs. It is now straightforward to check that compositions and identities are preserved; hence, \({\mathcal {L}}\) is a functor.

We will use a standard procedure for obtaining directed acyclic graph out of a digraph.

Definition 1.9

A strongly connected component in a digraph \({\mathcal {G}}\) is an induced subgraph \({\mathcal {G}}'\) such that for any two vertices x and y in \({\mathcal {G}}'\) there are paths \(x \rightarrow y\) and \(y \rightarrow x\) in \({\mathcal {G}}'\).

The strongly connected components are the equivalence classes of the relation of being strongly connected on the vertices of \({\mathcal {G}}\), i.e. having directed paths between any ordered pair of vertices. The ensuing partition then enables to construct the quotient graph without directed cycles.

Definition 1.10

The condensation \(c({\mathcal {G}})\) of digraph \({\mathcal {G}}\) has as its vertices the strongly connected components of \({\mathcal {G}}\). Two vertices X and Y have a directed edge (X, Y) in \(c({\mathcal {G}})\) if there is an edge (x, y) in \({\mathcal {G}}\) for some \(x \in X\) and \(y \in Y\).

Remark 1.11

The condensation \(c({\mathcal {G}})\) of a digraph \({\mathcal {G}}\) does not have oriented cycles.

In particular, if \({\mathcal {G}}\) has the structure of a preorder, i.e. a reflexive and transitive relation, the condensation is a canonical way of obtaining its underlying partial order (Schröder 2016, Proposition 8.13). Observe that taking the condensation of a digraph is not functorial; in fact, it may lead to maps \(G\rightarrow *\), where \(*\) is the one-point graph. However, in the theory of Alexandroff and finite topological spaces preorders and partial orders are in bijection with topological spaces and spaces with \(T_0\) separation, respectively. In this context, the condensation is a homotopy equivalence (Barmak 2011).

2.2 Simplicial complexes and homology theories

We recall here the definition of simplicial complexes;

Definition 1.12

An (abstract) simplicial complex on a vertex set V is a collection K of non-empty finite subsets \(\sigma \subseteq V\) that is closed under taking non-empty subsets: if \(\sigma \in K\) and \(\tau \subseteq \sigma \) is non-empty then \(\tau \in K\). The subsets are called simplices of K.

The following list records notations related to simplices and simplicial complexes used in this paper.

Analogously to morphisms of graphs, we can define morphisms of simplicial complexes:

Definition 1.13

A simplicial map \(f:K_1\rightarrow K_2\) between simplicial complexes \(K_1\) and \(K_2\) is a function on the vertices \(f:V(K_1)\rightarrow V(K_2)\) such that \(f(\sigma )\in K_2\) is a simplex for every simplex \(\sigma \) of \(K_1\).

(Abstract) simplicial complexes and simplicial maps form the category of simplicial complexes, that we denote by \(\textbf{SCpx}\). In this work we focus on homological invariants of directed graphs, and more precisely, on homology groups of digraphs. Homology groups are topological invariants of simplicial complexes. We assume that the reader is familiar with homology theories and we refer to Hatcher (2000), Munkres (1984) for comprehensive introductions. For setting the notations we briefly sketch here the main definition. We fix a commutative ring R.

Definition 1.14

A chain complex \((C,\partial )\) is a sequence \(C=(C_n)_{n\in {\textbf{N}}}\) of R-modules with a boundary operator \(\partial \) consisting of linear maps \(\partial =(\partial _n:C_{n+1}\rightarrow C_{n})\) such that \(\partial _{n}\circ \partial _{n+1}=0\) for all n.

A morphism of chain complexes \(f:(C,\partial )\rightarrow (C',\partial ')\) is a sequence of linear maps \(f_n:C_n\rightarrow C_n'\) with the commutation relations \(f_n \circ \partial _n = \partial _n' \circ f_{n+1}\). Chain complexes and morphisms of chain complexes over R form a category \(\textbf{Ch}(R)\), or more concisely \(\textbf{Ch}\). For a simplicial complex K and a commutative ring R, there is a standard way to construct a chain complex \((C,\partial )\) by considering, for each \(n\in {\textbf{N}}\), the free R-module generated by the n-simplices of K. The construction gives a functor from the category \(\textbf{SCpx}\) of simpicial complexes to the category \(\textbf{Ch}\). Furthermore, for a chain complex \((C,\partial )\), the degree n homology \({\textrm{H}}_n(C)\) of \((C,\partial )\) is defined as the quotient

which is well-defined as \(\text {im}(\partial _{n+1})\) is contained in \(\ker (\partial _n)\) by the identity \(\partial _{n}\circ \partial _{n+1}=0\). If we want to indicate the coefficients R over which we are computing homology we write \({\textrm{H}}_n(C;R)\). The construction gives functors from the category of chain complexes \(\textbf{Ch}\) to the category \(\textbf{Mod}_R\) of R-modules; hence, by composition, funtors from the category \(\textbf{SCpx}\) to \(\textbf{Mod}_R\). In the next section we briefly recall how to construct, starting with a digraph, suitable simplicial complexes (flag complexes or path complexes) and homology groups of digraphs.

In this section we survey some of the most prominent homology theories of directed graphs. We start in Sect. 2.1 by recalling the definition of flag complexes and associated simplicial homology, then in Sect. 2.2 we review the path complexes and path homology, as introduced by Grigor’yan et al. (2020). In Sect. 2.3, we provide a more detailed account on the Hochschild homology of a digraph, as of more relevance to us. Finally, in Sect. 2.4, we sketch some variations to these constructions, as has appeared in the literature.

3.1 Homology of flag complexes

Homology groups of undirected graphs can be defined as the simplicial homology groups of their underlying topological spaces; in fact, graphs can be seen as 1-dimensional simplicial complexes, and one can directly apply the approach of Sect. 1.2. We first start with describing this naive approach, and then we see how to generalize it by means of the so-called flag complexes.

For a digraph \({\mathcal {G}}=(E,V)\) and a fixed commutative ring R, consider the chain complex

where \(\langle E\rangle _R\) is the free R-module generated by the edges E and \(\langle V\rangle _R\) is the free R-module generated by the vertices V of \({\mathcal {G}}\). The boundary maps \(\partial _i\) are all 0, except for \(\partial _1\); this acts on the basis edges in \(\langle E\rangle _R\) as

and is extended to the whole R-module \(\langle E\rangle _R\) by R-linearity. The homology groups of a digraph defined this way are usually referred to as the ordinary homology groups of graphs.

Remark 2.1

The ordinary homology groups of graphs are trivial in every degree \(i\ge 2\).

The 0-th homology group of \({\mathcal {G}}\) describes the set of connected components. The 1-st homology group is isomorphic to the kernel of the only non-trivial map \(\partial _1\), and counts the cycles of \({\mathcal {G}}\); its rank can be entirely described in terms of numbers of vertices, edges and connected components of the digraph \({\mathcal {G}}\)—see for instance (Diestel 2010, Theorem 1.9.6). A prominent approach to generate higher dimensional homology groups is to construct, out of a graph \({\mathcal {G}}\), the so-called flag (also known as clique) complexes (Aharoni et al. 2005; Chen et al. 2001; Ivashchenko 1994); these provide natural invariants of graphs and have been generalized to digraphs (Masulli and Villa 2016; Reimann et al. 2017), as we now recall.

We first need to introduce the ordered simplicial complexes. A set S, endowed with a linear order of its elements, will be called an ordered set.

Definition 2.2

An ordered simplicial complex \(\Sigma \) on a vertex set V is a non-empty family of finite ordered subsets \(\sigma \subseteq V\) with the property that, if \(\sigma \) belongs to \(\Sigma \) then every ordered subset \(\tau \) of \(\sigma \) (ordered with the natural order induced by \(\sigma \)) belongs to \(\Sigma \).

When dealing with directed graphs, we need ordered cliques (as opposed to unordered cliques—cf. Definition 1.2.

Definition 2.3

An ordered k-clique of a directed graph \({\mathcal {G}}\) is a totally ordered k-tuple \((v_1,...,v_k)\) of vertices of \({\mathcal {G}}\) with the property that, for every \(i < j\), the pair \((v_i,v_j)\) is an ordered edge of \({\mathcal {G}}\).

We can now extend the construction of flag complexes to directed graphs.

Definition 2.4

Let \({\mathcal {G}}=(V,E)\) be a directed graph. The directed flag complex of \({\mathcal {G}}\) is the ordered simplicial complex \({\textrm{dFl}}({\mathcal {G}})\) on V whose k-simplices are all the ordered \((k+1)\)-cliques of \({\mathcal {G}}\).

We can again construct a chain complex. Let \(C_n({\textrm{dFl}}({\mathcal {G}});R)\) be the R-module freely generated by all the n-simplices of \({\textrm{dFl}}({\mathcal {G}})\). There are well-defined face maps

for \(j=0,\dots ,n\). The j-th face map \(d_j\), as an operator applied to the simplex \((v_0,\dots ,v_n)\) in \(C_n({\textrm{dFl}}({\mathcal {G}});R)\) is defined by cancelling the j-th vertex:

Face maps uniquely identify the faces of a simplex. In fact, let \(\sigma =(v_0,\dots ,v_n)\) be an n-simplex of the flag complex \({\textrm{dFl}}({\mathcal {G}})\); then, the faces \(d_j(v_0,\dots ,v_n)\) are \((n-1)\)-simplices of \({\textrm{dFl}}({\mathcal {G}})\). Each face map \(d_j\) uniquely identifies the j-th \((n-1)\)-face of \(\sigma \) as the face opposite to the vertex \(v_j\). For example, if \((v_0,v_1,v_2)\) is an ordered 3-clique in a digraph \({\mathcal {G}}\), represented below as an ordered simplex \(\sigma \) of the associated directed flag complex \({\textrm{dFl}}({\mathcal {G}})\),

then we have \(d_0(\sigma )=(v_1,v_2)\), \(d_1(\sigma )=(v_0,v_2)\) and \(d_2(\sigma )=(v_0,v_1)\).

Remark 2.5

The construction of flag complexes can be promoted to a functor from directed graphs to ordered simplicial complexes. Namely, if \(\phi :{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\) is a morphism of digraphs, then it sends ordered cliques of \({\mathcal {G}}_1\) to ordered cliques of \({\mathcal {G}}_2\). This induces a simplicial morphism \(f_{\phi }:{\textrm{dFl}}({\mathcal {G}}_1)\rightarrow {\textrm{dFl}}({\mathcal {G}}_2)\) between the flag complexes, sending a simplex \(\sigma \in {\textrm{dFl}}({\mathcal {G}}_1)\), hence an ordered clique \((v_0,\dots ,v_k)\) of \({\mathcal {G}}_1\), to the simplex \(f_{\phi }(\sigma )=(\phi (v_0),\dots ,\phi (v_k))\).

The (simplicial) homology groups with coefficients in R of a directed graph \({\mathcal {G}}\) are defined as the homology groups of the associated directed flag complex, and for each \(n\in {\textbf{N}}\) it can be seen as a composition of functors

where \(\textbf{Mod}_R\) is the category of R-modules.

Example 2.6

Fix as base ring the ring of integers \({\textbf{Z}}\). Consider the square-shaped digraph \({\mathcal {G}}\) on the vertices 0, 1, 2, 3 and set of edges described as in the following picture:

As we only have ordered 2-cliques, the associated flag complex is the square itself, i.e. an ordered simplicial complex with four vertices and four edges. It has homology groups

By adding to \({\mathcal {G}}\) also the edge (0, 3), we get the ordered 3-cliques (0, 1, 3) and (0, 2, 3); the corresponding flag complex is then the full square:

The first homology group \({\textrm{H}}_1({\textrm{dFl}}({\mathcal {G}});{\textbf{Z}})\) is now 0, whereas the 0-th homology group describing the number of connected components is again isomorphic to \({\textbf{Z}}\).

Remark 2.7

From Example 2.6 we see that some information from the orientations of the edges is lost. In fact, even though the simplices are constructed from the ordered cliques, the homology groups are defined as the homology groups of the (geometric realization of the) directed flag complex, which forgets some information about the directionalities. As an additional illustrative example, consider the digraphs in Fig. . They have isomorphic ordinary homology groups, as well as isomorphic homology groups of the associated directed flag complexes.

Two possible directed configurations for the pentagon graph

Full size image

Therefore, for constructing homology theories of digraphs more sensitive to the directionalities, one might need to incorporate the directed combinatorics in the definition of the homology groups. This is partially achieved with the homology theories recalled in the next subsections.

3.2 Path homology

Path homology can be considered as a homology theory of directed graphs, explicitly constructed from the edges of the digraphs. It was introduced in Grigor’yan et al. (2013), Grigor’yan et al. (2020), and it has nowadays many developments. We recall its definition, following the first works on the subject.

Definition 2.8

Let V be a finite set. For \(p\in {\textbf{N}}\), an elementary p-path on V is an ordered sequence \(i_0\dots i_p\) of \(p+1\) elements of V.

Let \({\textbf{K}}\) be a field (this assumption may be relaxed, but for the sake of reference, we use here the same assumptions as in Grigor’yan et al. (2013)). The vector space over \({\textbf{K}}\) consisting of formal linear combinations of elementary p-paths is denoted by \(\Lambda _p(V)\), or simply by \(\Lambda _p\). The basis element of \(\Lambda _p(V)\) corresponding to the elementary p-path \(i_0\dots i_p\) is denoted by \(e_{i_0\dots i_p}\) and the elements of \(\Lambda _p(V)\) are called paths. The linear maps \(\partial (e_{i_0\dots i_p}):=\sum _{q=0}^p (-1)^q e_{i_0\dots \widehat{i_q}\dots i_p}\) define the boundary operator \(\partial :\Lambda _p\rightarrow \Lambda _{p-1}\), hence a chain complex (Grigor’yan et al. 2020, Lemma 2.1).

Definition 2.9

(Grigor’yan et al. 2020, Definition 3.1) A path complex over V is a non-empty collection P of elementary paths on V with the property that if \(i_0\dots i_p\) belongs to P, then also \(i_0\dots i_{p-1}\) and \(i_1\dots i_p\) belong to P. The paths in P are called allowed.

For a path complex P on a set V, the vector space \({\mathcal {A}}_p(P)\) spanned by all the allowed p-paths from P is a subspace of \(\Lambda _p\). Define the subspace \(\Omega _p(P)\) of \({\mathcal {A}}_p(P)\) as

The elements of \(\Omega _p(P)\) are called the \(\partial \)-invariant paths of P. Then the boundary operator \(\partial \) restricts to a boundary operator on \(\Omega _p(P)\) (Grigor’yan et al. 2020, Sect. 3.2), and provides a chain complex \((\Omega _n(P),\partial )\).

Definition 2.10

The path homology groups \({\textrm{PH}}_n(P)\) of the path complex P are the homology groups of the chain complex \((\Omega _n(P),\partial )\).

To every directed graph there is an associated path complex (Grigor’yan et al. 2020, Ex. 3.3). If \({\mathcal {G}}=(V,E)\) is a digraph, an elementary p-path \(i_0\dots i_p\) is allowed if \((i_{k-1},i_k)\in E\) for all \(k=1,\dots ,p\). The set of allowed p-paths on \({\mathcal {G}}\) is denoted by \(P_p({\mathcal {G}})\); note that \(P_0({\mathcal {G}})=V\), and \(P_1({\mathcal {G}})=E\). Then, the union \(P({\mathcal {G}}):=\bigcup _n P_n({\mathcal {G}})\) is a path complex. In particular, if \({\mathcal {G}}\) is a digraph, then the path homology of \({\mathcal {G}}\) is defined as the path homology of the path complex \(P({\mathcal {G}})\), after restricting to the \(\partial \)-invariant paths.

Remark 2.11

It has been shown that path homology satisfies nice functorial properties: for a morphism of digraphs \(f:{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\) one gets a homomorphism \(f_*:{\textrm{PH}}_*({\mathcal {G}}_1) \rightarrow {\textrm{PH}}_*({\mathcal {G}}_1)\) between the associated path homology groups (Grigor’yan et al. 2014, Theorem 2.10). Furthermore, it has been shown that path homology satisfies Künneth formulas (Grigor’yan et al. 2017) and analogous properties to the classical Eilenberg-Steenrod axioms (Grigorian et al. 2018).

The following example illustrates a computation of the path homology groups of the same digraph as in Example 2.6.

Example 2.12

We return to the the square-shaped digraph \({\mathcal {G}}=(V,E)\) on the vertices 0, 1, 2, 3 introduced in Example 2.6. The path complex \(P({\mathcal {G}})\) associated to \({\mathcal {G}}\) is the complex with elementary allowed paths as depicted below:

All the other \(P_n\) are empty. As the edge (0, 3) does not belong to \({\mathcal {G}}\), the paths \(e_{013}\) and \(e_{023}\) are not \(\partial \)-invariant. However, the linear combination \(e_{013}-e_{023}\) would be, as

Therefore, if \({\textbf{K}}\) is a field, then \(\Omega _0=\langle e_0,e_1,e_2,e_3\rangle \), \(\Omega _1=\langle e_{01}, e_{02}, e_{13}, e_{23} \rangle \) and \(\Omega _2=\langle e_{013}-e_{023} \rangle \). The associated path homology of \({\mathcal {G}}\) is then \({\textrm{PH}}_0(P({\mathcal {G}}))\cong {\textbf{K}}\) and it is 0 in higher dimensions. This can be shown by direct computation from the chain complex \((\Omega _n(P),\partial )\), or by using the fact that the square digraph is contractible (Grigor’yan et al. 2014, Example 3.13). Observe that if we add the edge (0, 3) to \({\mathcal {G}}\) the spaces \(\Omega _1\) and \(\Omega _2\) become \(\Omega _1=\langle e_{01}, e_{02}, e_{13}, e_{23}, e_{03} \rangle \) and \(\Omega _2=\langle e_{013},e_{023} \rangle \), but the path homology groups do not change.

We conclude this subsection with a note on the computability of path homology. Despite the apparent computational complexity, path homology is amenable to computations; for example, in dimension 2, for digraphs with 4000 vertices and ca. 25K edges (Grigor’yan 2022). The interested reader can find the description and applications of an algorithm computing path homology in higher degrees in Chowdhury et al. (2022) (and in the related references).

3.3 Hochschild homology of path algebras

Hochschild (co-)homology, introduced by Hochschild (1945), is a natural invariant of associative, not necessarily commutative, unital algebras. An investigation of this homology theory is beyond the purposes of this work, and we refer to Loday (1998) for a general and comprehensive overview on the subject. To each digraph \({\mathcal {G}}\), we associate an algebra \(R{\mathcal {G}}\), called the path algebra—see Definition 2.20. The path algebra is associative and, for finite digraphs, also unital. Therefore, Hochschild homology groups of \(R{\mathcal {G}}\) give (algebraic) invariants of digraphs. Goal of this section is to review some properties of Hochschild (co-)homology, and to introduce a new characteristic of digraphs (Definition 2.29).

3.3.1 Hochschild homology

We first recall the definition of Hochschild homology, following (Loday 1998, Sect. 1.1). For a commutative ring R, let A be an associative unital R-algebra; for example, A can be a polynomial algebra over R. For a bimodule^{Footnote 2}M over A, let \(C_n(A,M)\) be the R-module

defined as the tensor product of M and n copies of A (all the tensor products being over R). The boundary operator, classically denoted by b, is the R-linear map \(b:C_n(A,M)\rightarrow C_{n-1}(A,M)\) defined as follows:

In the formula, for simplicity of notation, we have dropped the tensor products. The map b is a boundary operator (Loday 1998, Lemma 1.1.2) and the pair \((C_*(A,M),b)\) is a chain complex, called the Hochschild complex.

Definition 2.13

The Hochschild homology groups \({\textrm{HH}}_*(A,M)\) of an associative unital algebra A with coefficients in a bimodule M are the homology groups of the Hochschild complex.

When M is the algebra A itself, we use a simpler notation:

Notation 2.14

The Hochschild homology groups of an associative unital algebra A with coefficients in A are denoted by \({\textrm{HH}}_*(A)\).

For illustration, we provide some elementary computations; for further details see Loday (1998).

Example 2.15

Let \(M=A=R\) be a commutative ring. Then, we have

In fact, as tensor products are computed over R and \(R\otimes _R R\cong R\), the chain complex \(C_*(R,R)\) is a copy of R in each degree, and the boundary operator b is either the identity or the zero map, depending on the parity of n. The computation follows.

Example 2.16

Let \(M=A\) be an associative algebra. Then,

where [A, A] denotes the commutator submodule generated by all the \([a,a']=aa'-a'a\). In fact, for \(a\otimes a'\in C_1(A,A)\), we have \(b(a\otimes a')=aa'-a'a\). In particular, if A is commutative, then we obtain \({\textrm{HH}}_0(A)\cong A\), and for A non-commutative \({\textrm{HH}}_0(A)\) coincides with its center.

We recall that if A is unital and commutative, then the module of Kähler differentials \(\Omega ^1(A)\) is the A-module generated by all the formal differentials da, with \(a\in A\), which are R-linear, i.e., \(d(\lambda a + \mu b)=\lambda da +\mu db\) for all \(a,b\in A\) and \(\lambda ,\mu \in R\), and satisfy the additional product condition \(d(ab)=a db+b da\) for all \(a,b\in A\). Then the first Hochschild homology group of A is isomorphic to \(\Omega ^1(A)\) over the ring R (Loday 1998, Definition 1.1.9 and Proposition 1.1.10). Analogously, in higher degrees, the n-th Hochschild homology \({\textrm{HH}}_n(A)\) of A is related to the module of n-forms (Loday 1998, Sect. 1.3).

Example 2.17

Let \(A={\textbf{K}}[X]\) be the polynomial algebra over a field \({\textbf{K}}\). As A is a commutative algebra, then \({\textrm{HH}}_0(A)\cong A\). The first Hochschild homology group is isomorphic to the ideal (X) of A. In fact, by Loday (1998, Proposition 1.1.10) it is isomorphic to the module of Kähler differentials \(\Omega ^1(A)\), and this latter is generated by X. All its higher Hochschild homology groups are zero.

Remark 2.18

Note that the Hochschild homology groups \({\textrm{HH}}_*(A,M)\) depend on the choice of the ground ring. Non-isomorphic ground rings can lead to different computations—see for example Loday (1998, Sect. 1.1.18).

A dual cohomological theory can be easily derived. In fact, the Hochschild cohomology groups \({\textrm{HH}}^*(A,M)\) of an associative algebra A with coefficients in M can be defined as the homology groups of the cochain complex \({\textrm{Hom}}_R(C_n(A,M))={\textrm{Hom}}_R(A^{\otimes n},M)\)—cf. Happel (1989), Loday (1998).

Remark 2.19

The Hochschild homology construction is functorial in both the bimodule M and the algebra A, and for \(M=A\), Hochschild homology is a covariant functor from the category of associative R-algebras to the category of R-modules (Loday 1998, Sect. 1.1.4). More precisely, a bimodule homomorphism \(f:M\rightarrow M'\) induces a map

in Hochschild homology by sending the element \((m,a_1,\dots , a_n)\in C_n(A,M)\) to the element \((f(m),a_1,\dots , a_n)\in C_n(A,M')\); the differential b clearly commutes with it and induces the required homomorphism of homology groups. Similarly, if \(M=A\) and \(g :A\rightarrow A'\) is an R-algebra homomorphism, then g extends to the tensor products giving a map \((a_0,\dots ,a_n)\mapsto (g(a_0),\dots , g(a_n))\) and providing a morphism of chain complexes \(C_*(A,A)\rightarrow C_*(A',A')\); hence, a homomorphism of Hochschild homology groups.

We note here that the functoriality with respect to R-algebra homomorphisms does not extend to Hochschild cohomology—see, for instance, Loday (1998, Sect. 1.5.5). This lack of functoriality is the reason why we will focus on Hochschild homology, rather than cohomology.

3.3.2 Hochschild homology of path algebras

In this subsection we apply Hochschild homology to certain algebras associated to digraphs. All results and proofs provided here are classical, and we claim no originality. For computational purposes, we also restrict to the case in which the base ring R is an (algebraically closed) field \({\textbf{K}}\); we can think of \({\textbf{K}}\) as the field of complex numbers.

Let \({\mathcal {G}}=(V,E,s,t)\) be a (finite) directed graph. By a path in \({\mathcal {G}}\) we mean a sequence \(\gamma =(e_1,\dots ,e_n)\) of composable edges \(e_i\) in \({\mathcal {G}}\) such that \(s(e_{i+1})=t(e_i)\). The number n is the length of the path. For any vertex v of \({\mathcal {G}}\), we also consider the trivial path \(e_v\) of length 0 at the vertex v.

Definition 2.20

The path algebra \({\textbf{K}}{\mathcal {G}}\) associated to the digraph \({\mathcal {G}}\) is the \({\textbf{K}}\)-vector space with a basis consisting of all possible paths in \({\mathcal {G}}\), and the multiplication being defined on two basis paths \(\gamma = (e_1,\dots ,e_n)\), \(\gamma ' = (e'_1,\dots ,e'_p)\) by the formula

The following lemma is easily derived from the definition:

Lemma 2.21

The path algebra \({\textbf{K}}{\mathcal {G}}\) associated to a digraph \({\mathcal {G}}\) is an associative algebra over \({\textbf{K}}\), and has a unit if the digraph is finite.

Proof

Let \(\gamma , \gamma ', \gamma ''\) be paths in \({\mathcal {G}}\). Then, by definition of product of paths, both \((\gamma \gamma ')\gamma ''\) and \(\gamma (\gamma '\gamma '')\) are given as concatenation of paths if they are all compatible, and are both 0 otherwise (by bilinearity). Since the algebra \({\textbf{K}}{\mathcal {G}}\) is defined as a vector space generated by the possible paths in \({\mathcal {G}}\), this is enough to show its associativity.

If the digraph \({\mathcal {G}}\) is finite, then the element

is a unit. In fact, if \(\gamma = (e_1,\dots ,e_n)\) is a path of \({\mathcal {G}}\), then \(e_{s(e_1)}\gamma =\gamma \) and \(\gamma e_{t(e_n)}=\gamma \), where \(e_{s(e_1)}\) and \(e_{t(e_n)}\) are the constant paths at \(s(e_1)\) and \(t(e_n)\), respectively. All the other products with paths of type \(e_v\), for v a vertex of \({\mathcal {G}}\), are zero; hence we have \(e\gamma = e_{s(e_1)}\gamma =\gamma \), and \(\gamma e=\gamma e_{t{e_n}}=\gamma \). \(\square \)

The path algebra \({\textbf{K}}{\mathcal {G}}\) is generated (as an algebra over \({\textbf{K}}\)) by all the paths of length at most 1, and the unit is the sum of all trivial paths. More precisely, it has the structure of a graded vector space with grading induced by the length of paths (Brion 2012). Observe that all trivial paths \(e_v\), with \(v\in V({\mathcal {G}})\), are idempotents of \({\textbf{K}}{\mathcal {G}}\), as \((e_v)^2=e_v e_v=e_v\). Furthermore, if v and w are distinct vertices of \({\mathcal {G}}\), then \(e_v e_w=0\).

We will be interested in digraphs without oriented cycles. In fact, we have the following:

Proposition 2.22

The path algebra \({\textbf{K}}{\mathcal {G}}\) is of finite dimension,^{Footnote 3} if and only if \({\mathcal {G}}\) is finite, connected, and has no oriented cycles.

Proof

The path algebra \({\textbf{K}}{\mathcal {G}}\) is generated by the paths of length at most one, this number being bounded by the number of all vertices and edges of \({\mathcal {G}}\).

To prove the statement, it is enough to show that the number of paths of \({\mathcal {G}}\) is finite if and only if \({\mathcal {G}}\) is finite and has no oriented cycles. Assume first that \({\mathcal {G}}\) is finite without oriented cycles. Then the number of paths of length l in \({\mathcal {G}}\) is bounded by \(|E({\mathcal {G}})|^l\). If the number of paths of \({\mathcal {G}}\) is infinite, then there is a path of arbitrary large length. In particular, there exists a path \(\gamma \) with length greater than the number of vertices of \({\mathcal {G}}\). This leads to a contradiction, because there exists a vertex v of \({\mathcal {G}}\) encountered twice by \(\gamma \), hence an oriented cycle. Conversely, any infinite connected graph has infinitely many paths; if the graph \({\mathcal {G}}\) is finite, but it contains at least an oriented cycle \(\gamma \), then we can generate infinitely many paths by iterative compositions of such \(\gamma \) with itself. \(\square \)

The linear n-graph \(I_n\)

Full size image

We proceed with some elementary examples of path algebras:

Example 2.23

The simplest graphs to consider are given by the graph \({\mathcal {G}}_0\) with a single vertex v, the directed graph \({\mathcal {G}}_1\) with a vertex v and a loop e at v, and the digraph \({\mathcal {G}}_2\) with two vertices \(v_0,v_1\) and a directed edge \(e_1=(v_0,v_1)\) between them. The associated path algebras are given by the base field \({\textbf{K}}\), the polynomial ring \({\textbf{K}}[X]\), and by the ring of upper triangular \((2\times 2)\)-matrices. More generally, if \(I_n\) is the graph illustrated in Fig. , then the path algebra \({\textbf{K}}I_n\) is isomorphic to the ring of upper triangular \((n\times n)\)-matrices. An isomorphism can be described by sending the trivial path \(e_{v_i}\) to the entry (i, i), and edge \((v_i,v_{i+1})\) to the entry \((i,i+1)\).

Observe that the map assigning to a digraph its path algebra is functorial:

Remark 2.24

The assignment \({\mathcal {G}}\mapsto {\textbf{K}}{\mathcal {G}}\) associating the path algebra \({\textbf{K}}{\mathcal {G}}\) to a digraph \({\mathcal {G}}\) extends to a functor from the category of directed graphs to the category \({\textbf{K}}\text {-}\textbf{Alg}\) of associative \({\textbf{K}}\)-algebras. To see this, observe that a morphism of digraphs sends paths to paths, thus induces a \({\textbf{K}}\)-linear map between the vector spaces, and preserves the composition of paths. As a consequence, the induced map between the associated path algebras uniquely extends by linearity to a \({\textbf{K}}\)-algebra homomorphism. Hochschild homology of associative path algebras is functorial—see Remark 2.19. Then, the composition

describes the Hochschild homology of the path algebra of a (finite) digraph as a functor on the category \(\textbf{Digraph}\) with values in the category \(\textbf{Vect}\) of vector spaces over \({\textbf{K}}\).

Computations of Hochschild (co-)homology groups may be difficult for arbitrary associative algebras, but when A is the path algebra \({\textbf{K}}{\mathcal {G}}\) of a directed graph, computations are easier and reflect the combinatorial properties of the digraph \({\mathcal {G}}\). First, it is a standard fact that the path algebra associated to a digraph is a hereditary algebra, i.e., all submodules of its projective modules are projective. In fact, modules over a path algebra have a standard resolution of length 1 (Brion 2012, Proposition 1.4.1), and as a consequence the Hochschild homology groups \({\textrm{HH}}_*(A)\) of the path algebra A vanish in degree \(\ge 2\). In degrees 0 and 1, the computation is due to Happel (1989) (see also Redondo 2001, Proposition 4.4):

Theorem 2.25

If \({\mathcal {G}}=(V({\mathcal {G}}),E({\mathcal {G}}),s,t)\) is a connected directed graph without oriented cycles and \({\textbf{K}}\) is an algebraically closed field, then

where \(A={\textbf{K}}{\mathcal {G}}\) is the path algebra of \({\mathcal {G}}\), \(n=|V({\mathcal {G}})|\) is the number of vertices of \({\mathcal {G}}\) and \(e_{t(e)}A e_{s(e)}\) is the subspace of A generated by all the possible paths from s(e) to t(e) in \({\mathcal {G}}\).

In general, for infinite digraphs, or digraphs admitting cycles, this computation can not be used and the first Hochschild homology group is of infinite rank.

Example 2.26

Let \({\mathcal {G}}\) be the digraph with a vertex v and the single directed edge (a loop) (v, v). The path algebra \({\textbf{K}}{\mathcal {G}}\) is isomorphic to the polynomial algebra \({\textbf{K}}[X]\). This is a commutative algebra over \({\textbf{K}}\), hence by Example 2.17, we get

which is not finite over \({\textbf{K}}\).

In concrete applications, one avoids the case of digraphs with paths of infinite length by restricting to some special classes of acyclic directed subgraphs. In such restricted context, we observe that Hochschild homology can be seen as a functor with values in the category of (graded) vector spaces of finite dimension:

Remark 2.27

Theorem 2.25 implies that, when restricting to digraphs without oriented cycles, the associated Hochschild (co-)homology groups are vector spaces of finite dimension. Let \(\textbf{Digraph}_0\) be the subcategory of \(\textbf{Digraph}\) consisting of finite digraphs without oriented cycles and induced morphisms of digraphs. Then, the composition in Eq. (4) induces the composition of functors

where now the target category \(\textbf{FinVect}\) is the category of finite-dimensional vector spaces over \({\textbf{K}}\).

We give a concrete example:

Example 2.28

Let \(\phi :{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\) be the regular morphism of digraphs illustrated in Fig. , and defined by sending \(v_i\) to the vertex \(w_i\), for \(i=0,1,2\). The morphism \(\phi \) sends paths of \({\mathcal {G}}_1\) to paths of \({\mathcal {G}}_2\) of the same length, thus inducing by \({\textbf{K}}\)-linearity an homomorphism of vector spaces \(\phi _*:{\textbf{K}}{\mathcal {G}}_1\rightarrow {\textbf{K}}{\mathcal {G}}_2\). In terms of basis elements, the trivial path \(e_{v_i}\) is sent to the trivial path \(e_{w_i}\), whereas the basis elements corresponding to the 1-paths \((v_0,v_1)\), \((v_0,v_2)\), and \((v_1,v_2)\) are sent to those of \({\textbf{K}}{\mathcal {G}}_2\) corresponding to \((w_0,w_1)\), \((w_0,w_2)\), and \((w_1,w_2)\). The tensor product operations are clearly compatible. As in Remark 2.27, we get morphisms

hence induced maps between the Hochschild (co-)chain complexes. By applying the functors \({\textrm{Hom}}(-,{\textbf{K}}{\mathcal {G}}_{-})\) to the minimal projective resolutions of \({\textbf{K}}{\mathcal {G}}_1\) and \({\textbf{K}}{\mathcal {G}}_2\), we get a diagram of short exact sequences (for such a computation, see Happel 1989)

where the maps are induced by identification of paths of length 0 (central map) and of the paths \((v_0,v_1)\), \((v_0,v_2)\), \((v_1,v_2)\), and \((v_0,v_1,v_2)\) with the respective ones in \({\mathcal {G}}_2\) (rightmost map).

Regular morphism of digraphs \(\phi (v_i)=w_i\)

Full size image

Focusing on the first Hochschild homology groups \({\textrm{HH}}_1({\textbf{K}}{\mathcal {G}}_1)\cong {\textbf{K}}^2\) and \( {\textrm{HH}}_1({\textbf{K}}{\mathcal {G}}_2)\cong {\textbf{K}}^5\), this roughly describes the functoriality of Hochschild homology by means of the paths in the digraphs; the first Hochschild homology groups being obtained as alternating sums of the vector spaces appearing in the horizontal diagrams of the short exact sequences.

In general, descriptions of the Hochschild homology groups are not easy. In this work, we use the computation of Theorem 2.25 as handleable—considering in the summation only simple paths. In order not to loose the information captured by the number of cycles, we will also consider the following characteristic measure:

Definition 2.29

Let \({\mathcal {G}}=(V({\mathcal {G}}),E({\mathcal {G}}),s,t)\) be a digraph, and \(A={\textbf{K}}{\mathcal {G}}\) the path algebra of \({\mathcal {G}}\) over a field \({\textbf{K}}\). The Hochschild characteristic of \({\mathcal {G}}\) is defined as

where \(n=|V({\mathcal {G}})|\), the sum over \(e\in E({\mathcal {G}})\) only counts simple paths, and \(C({\mathcal {G}})\) is the number of simple oriented cycles in \({\mathcal {G}}\), i.e. cycles with only the first and last vertices being equal.

Note that the Hochschild characteristic agrees with the Euler characteristic of the Hochschild chain complex associated to the path algebra \({\textbf{K}}{\mathcal {G}}\), if \({\mathcal {G}}\) has no oriented cycles and \({\textbf{K}}\) is algebraically closed. The definition of Hochschild characteristic extends then to any field. We conclude with some illustrative examples.

Example 2.30

Consider the coherently oriented cyclic graph \(C_n\), for \(n\ge 2\), and the linear n-graph \(I_n\)—see Figs. 1 and 3, respectively. Then, we get \({\mathcal {X}}_{{\textrm{HH}}}(C_n)={\mathcal {X}}_{{\textrm{HH}}}(I_n)=1\). From the point of view of the Hochschild characteristic, linear graphs and cycles are not distinguishable.

More generally, observe that a connected digraph whose underlying graph is isomorphic to a linear graph has always Hochschild characteristic 1. Likewise, if the digraph is a polygon, or it differs from a polygon only for one edge (such edge having the opposite orientation). All other digraphs whose underlying unoriented graph is isomorphic to a cyclic graph have Hochschild characteristic 0. Therefore, the following holds:

Proposition 2.31

Let \({\mathcal {G}}\) be a (simple) connected digraph. Then,

• if its underlying unoriented graph is isomorphic to a linear graph, then its Hochschild characteristic is 1;

• if its underlying unoriented graph is isomorphic to a polygonal graph, then its Hochschild characteristic is either 0 or 1.

Example 2.32

We apply the Hochschild homology computation of Theorem 2.25 to the square digraph \({\mathcal {G}}\) of Examples 2.6 and 2.12. The Hochschild homology group in degree 0 is isomorphic to \({\textbf{K}}\), whereas the dimension of \( {\textrm{HH}}_1({\textbf{K}}{\mathcal {G}})\) is 1. The computation in degree 1 changes if we add to \({\mathcal {G}}\) the edge (0, 3), giving \(\dim _{{\textbf{K}}} {\textrm{HH}}_1({\textbf{K}}{\mathcal {G}})=4\). As a consequence, the Hochschild characteristics of the two graphs are 0 and \(-3\). Observe that if we consider the cycle with a diagonal (rather than the square with a diagonal) we get Hochschild characteristics equal to 0 (with the edge \((v_0,v_2)\) decreasing it).

We remark here that the computation of the Hochschild characteristics requires counting all simple cycles in the digraph. This is exponential, and, consequently, computations for large digraphs are rather demanding.

3.4 A view towards other approaches

We conclude this survey section by reviewing some generalizations and other approaches to (co-)homology theories of digraphs; the literature on the subject is very rich, and this survey is far from being exhaustive.

• A generalization of the homology of directed graphs as the homology of the associated flag complex (see Sect. 2.1) is given by the homology of the so-called flag tournaplex (Govc et al. 2021). In fact, when a directed graph has no reciprocal edges the associated flag tournaplex is isomorphic to the flag complex of the underlying undirected graph. The flag tournaplex of a digraph has been employed as a classifier in Govc et al. (2021), combined with directionality invariants and persistent homology methods.

• The theory of path homology for digraphs, as developed in Grigor’yan et al. (2020), has been further extended to multigraphs and quivers (Grigor’yan et al. 2018) or to more general path algebras, e.g., to the realm of differential algebras (Ren and Wang 2021). It has also a cohomological counterpart (Grigorian et al. 2015). This has also been extended to a persistent path homology approach—see for instance Dey et al. (2022).

• Hochschild homology can be endowed with an additional differential of degree 1, usually denoted by B, turning it into a mixed complex (Kassel 1987). The additional differential B leads to the construction of the so-called cyclic homology, and to its variations negative cyclic homology and periodic cyclic homology of algebras—see also Loday (1998). Therefore, application of such homology theories to the path algebra of a digraph may lead to other invariants, extending the approach surveyed in Sect. 2.3.2.

• Ordinary homology groups of digraphs, and the Hochschild homology groups of the associated path algebras, have natural generalizations to the categorical framework. One way to do so is by replacing the path algebra of Definition 2.20 with a suitable (freely generated) category \(\textbf{Path}({\mathcal {G}})\), called the path category—see also the discussion below. In a similar fashion, instead of constructing the path algebra or the path category, one can associate to a directed graph other mathematical objects, for example the so-called path posets \(P({\mathcal {G}})\). First introduced by Turner and Wagner (2012), the path poset has been recently used to define new combinatorial cohomologies of digraphs (Caputi et al. 2021a, 2022c), and that can be generalized to arbitrary monotone properties of graphs (Caputi et al. 2022b). This approach seems to be related to other topological/combinatorial invariants of simplicial complexes (Caputi et al. 2022a).

• Among other approaches, sheaf homology has been used with some applications to the Max-Flow Min-Cut theorem (Krishnan 2014), as well as a directed approach to algebraic topology built upon cohomology of small categories with coefficients in natural systems as in Baues and Wirsching (1985) and Dubut et al. (2015) and in the references therein.

We can illustrate these various approaches in the following (non-commutative) diagram

where we synthetically show the construction of homology theories of digraphs as representations of the category \(\textbf{DiGraph} \). Note that path homology does not appear in the picture because it is not yet known if it factors through simplicial complexes/algebras/posets/categories.

We wish to spend a few more words on the path category and related homology theories, as these are close to the Hochschild homology of path algebras. The path category \(\textbf{Path}({\mathcal {G}})\) associated to a directed graph \({\mathcal {G}}\) is the category freely generated by the paths of \({\mathcal {G}}\). There is a forgetful functor from the category \(\textbf{Cat}\) of small categories and functors to the category of quivers (thought of as directed graphs with loops and multiple edges). Such forgetful functor has a left adjoint, the functor sending a quiver to the free category on that quiver (see e.g., MacLane 1971, Sect. II.7). As each directed graph is, in particular, also a quiver, one gets a functor

from the category of digraphs to the category of small categories. It is easy to see that \({\textrm{Free}}({\mathcal {G}})\) is in fact the path category \(\textbf{Path}({\mathcal {G}})\). Then, the functor in (5) allows one to use homology theories of categories for obtaining new invariants of digraphs. The naive idea of directly computing the homology groups of the category \(\textbf{Path}({\mathcal {G}})\) (with constant coefficients), would not give new information due to the following (see Citterio 2001, Ex. 4.3):

Proposition 2.33

The classifying space \(|{N}(\textbf{Path}({\mathcal {G}}))|\) of the path category of a directed graph \({\mathcal {G}}\) has the homotopy type of the geometric realization \(|{\mathcal {G}}|\) of the digraph \({\mathcal {G}}\).

However, more interesting homology theories arise when considering the homology of categories with coefficients in functors (Gabriel and Zisman 1967, App. 2). In this framework, one considers the homology groups of \(\textbf{Path}({\mathcal {G}})\) with twisted coefficients in the same spirit as in usual homology of topological spaces but with local coefficients (see also Quillen 1973, Sect. 1). Remarkably, this point of view has been used in node embedding and community detection problems (Kaul and Tamaki 2020).

As outlined in Sect. 2, homology theories of digraphs are flexible and versatile tools, able to capture various topological information from the input graphs. However, as we will show with examples in Sect. 3.2, these homology theories might miss some combinatorial information inherent in the digraph structure. Therefore, with the aim of capturing both the topology and combinatorics of digraphs, in this section we will study some special cases of connectivity digraphs, i.e., digraphs constructed by using some combinatorial information of \({\mathcal {G}}\). For example, connectivity digraphs can be described by edges, paths, sets of edges, or cliques, together with their incidence relations.

We will focus on two closely related simplicial connectivity approaches and show that they capture the combinatorial information described by edges and ordered cliques in a digraph. The first one, developed by the second author in Riihimäki (2023) and briefly recalled in Sect. 3.3, generalizes the classical q-connectivity analysis (Atkin 1972, 1974) to the context of ordered simplicial complexes. This construction is based on ordered cliques sharing q-faces respecting a chosen directionality condition. The connectivity digraphs constructed have the additional structure of a preordered set (Definition 3.13). Then in Sect. 3.4, we investigate the particular case of connectivity digraphs built with ordered cliques and codimension 1 incidence relations. The connectivity digraph structure is induced from a total order of simplicial face maps. This choice is shown to generalize the notion of line digraphs (going from the combinatorics of edges to the combinatorics of higher simplices), giving what we call here the n-path digraphs—cf. Definition 3.20.

4.1 Connectivity digraphs

Goal of this subsection is to introduce the concept of connectivity digraphs. For a digraph \({\mathcal {G}}\), a connectivity digraph associated to \({\mathcal {G}}\) is meant to encapsulate some combinatorial information of \({\mathcal {G}}\). In order to make it formal, we start with the notion of a connectivity structure.

Definition 3.1

A connectivity structure is a triple \(({\mathcal {G}},{\mathfrak {F}}, {A})\) consisting of a digraph \({\mathcal {G}}\), and a non-empty family \({\mathfrak {F}}\) of subgraphs of \({\mathcal {G}}\) together with a \(\{0,1\}\)-valued function \(A:{\mathfrak {F}}\times {\mathfrak {F}}\rightarrow \{0,1\}\).

Note that there are no additional requirements on the map A; roughly, a connectivity structure is a way to encode the connectivity properties of families of subsets of \({\mathcal {G}}\), all at once. For a given connectivity structure \(({\mathcal {G}},{\mathfrak {F}}, {A})\) there is an associated well-defined digraph \(E_{{\mathfrak {F}}}{\mathcal {G}}\) (possibly with self-loops) constructed as follows: the set of vertices of \(E_{{\mathfrak {F}}}{\mathcal {G}}\) is the family \({\mathfrak {F}}\), and for \(H_1\), \(H_2\) in \({\mathfrak {F}}\), there is a directed edge \((H_1,H_2)\) in \(E_{{\mathfrak {F}}}{\mathcal {G}}\) if and only if \(A(H_1,H_2)=1\). We can now give the formal definition of connectivity digraphs.

Definition 3.2

A connectivity digraph is the directed graph \(E_{{\mathfrak {F}}}{\mathcal {G}}\) associated to a connectivity structure \(({\mathcal {G}},{\mathfrak {F}}, {A})\). A morphism of connectivity structures \(({\mathcal {G}},{\mathfrak {F}}, {A})\rightarrow ({\mathcal {G}}',{\mathfrak {F}}', {A}')\) is a morphism of digraphs \(\Phi :{\mathcal {G}}\rightarrow {\mathcal {G}}'\) inducing a function \(\phi :{\mathfrak {F}}\rightarrow {\mathfrak {F}}'\) such that \(A(H_1,H_2)=1\) implies \(A'(\phi (H_1),\phi (H_2))=1\).

Before proceeding further, we provide some examples of connectivity structures and associated connectivity digraphs.

Example 3.3

Let \({\mathcal {G}}\) be a digraph and let \({\mathfrak {F}}=\{{\mathcal {G}}\}\) be the family consisting of the graph \({\mathcal {G}}\) itself. Then, depending on A, \(E_{{\mathfrak {F}}}{\mathcal {G}}\) can either be the graph with a single vertex and no edges, or the digraph with a vertex and a single self-loop. On the other hand, if \({\mathfrak {F}}=V({\mathcal {G}})\) consists of the vertices of \({\mathcal {G}}\), and we set \(A(v,w)=1\) if and only if \((v,w)\in E({\mathcal {G}})\), then \(E_{{\mathfrak {F}}}{\mathcal {G}}\cong {\mathcal {G}}\).

Example 3.4

Let \({\mathcal {G}}\) be a digraph and let \({\mathfrak {F}}=E({\mathcal {G}})\) be the family consisting of all the edges of \({\mathcal {G}}\). Set \(A(e,f)=1\) if and only if \(t(e)=s(f)\). Then, \(E_{{\mathfrak {F}}}{\mathcal {G}}\cong {\mathcal {L}}{\mathcal {G}}\) and the associated connectivity digraph is isomorphic to the line digraph. We will investigate this example in detail in the next subsections. On the contrary, if we set \(A(e,f)=1\) if and only if \(t(e)\ne s(f)\), then the associated connectivity digraph is sometimes called the complement of \({\mathcal {L}}{\mathcal {G}}\).

Example 3.5

Let \({\mathcal {G}}\) be a digraph and let \({\mathfrak {F}}=S({\mathcal {G}})\) be the family consisting of all the strongly connected components of \({\mathcal {G}}\). Set \(A(S,T)=1\) if and only if there exists an edge e of \({\mathcal {G}}\) such that \(s(e)\in S\) and \(t(e)\in T(e)\). Then, \(E_{{\mathfrak {F}}}{\mathcal {G}}\cong {\mathcal {C}}{\mathcal {G}}\) yields nothing but the condensation of \({\mathcal {G}}\).

Example 3.6

Let \({\mathcal {G}}\) be a digraph and let \({\mathfrak {F}}=\{\text {all the subgraphs of}~{\mathcal {G}}\}\). Set \(A(s,t)=1\) if and only if s is strictly contained in t. Then, the connectivity digraph \(E_{{\mathfrak {F}}}{\mathcal {G}}\) yields, up to orientation, the Hasse diagram of \({\mathcal {G}}\).

Connectivity structures and morphisms of connectivity structures form a category where compositions are induced by compositions of morphisms of digraphs. It is also easy to see that the map which associates to a connectivity structure \(({\mathcal {G}},{\mathfrak {F}}, {A})\) the connectivity digraph \(E_{{\mathfrak {F}}}{\mathcal {G}}\) is functorial with respect to morphisms of connectivity structures.

The context of connectivity structures is quite general. Different connectivity structures can encode various combinatorial information of digraphs. Our main motivation for introducing connectivity structures is that the associated connectivity digraphs provide domains for the homology theories described in Sect. 2, and then one can extend the class of digraph invariants.

We remark here that a definition similar to Definition 3.2 has previously appeared in Grigor’yanet al. (2018, Sect. 6) in the form of a connectivity multigraph of a CW-complex, and meant to extend Atkin’s connectivity graphs (see Sect. 3.3): the vertices of the multigraph are the n-cells and two vertices are adjacent if the corresponding cells share a face. This graph is given the structure of a directed graph by first numbering all the cells, and then using this enumeration for describing the directions of the edges. Our construction of connectivity digraphs, and our two main examples of simplicial connectivities provided in Sects. 3.3 and 3.4, do not require a predetermined enumeration of the vertices, making the definition of connectivity digraphs more intrinsic. We also give a more immediate recipe for connectivity digraphs; in fact, Definition 3.1 essentially provides the adjacency matrices.

4.2 Motivating examples

We start by motivating our combinatorial constructions, provided in Sects. 3.3 and 3.4, with some examples. Specifically we construct non-isomorphic digraphs, such that all the homology theories introduced in Sect. 2 fail to distinguish them. Then, we will see that the same homology theories, applied to the connectivity digraphs, are able to distinguish them—see Examples 3.15, 3.34, and 3.35, proving that encoding the combinatorics is quite helpful.

Example 3.7

Consider the following directed graphs:

The two digraphs are not isomorphic. For example, the total degree of the vertex 2 in \({\mathcal {G}}_1\) is 4 with out-degree 1, but there are no vertices of out-degree 1 and total degree 4 in \({\mathcal {G}}_2\). First, observe that the directed flag complexes associated to \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\) are both contractible. Hence, the associated simplicial homology groups are isomorphic.

Following Sect. 2.2, we find the \(\partial \)-invariant paths for \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\): \(\Omega _2({\mathcal {G}}_1)=\{e_{012}, e_{312}, e_{324}\}\) and \(\Omega _3({\mathcal {G}}_1)=\varnothing \), and \(\Omega _2({\mathcal {G}}_2)=\{e_{012}, e_{123}, e_{243}, e_{013}-e_{023}\}\) and \(\Omega _3({\mathcal {G}}_2)=\{e_{0123}\}\), and all the other \(\Omega _n\), with \(n\ge 3\), are empty. The \(\Omega _1\) and \(\Omega _0\) are always spanned by the edges and vertices, respectively. Therefore, we get the chain complexes:

The homology groups of these chain complexes are both trivial and concentrated in degree 0, with the only non-trivial path homology groups \({\textrm{PH}}_0(P({\mathcal {G}}_1))\cong {\textbf{K}}\cong {\textrm{PH}}_0(P({\mathcal {G}}_2))\).

In the case of the Hochschild homology of the path algebras, as both graphs are acyclic, we can use Theorem 2.25. This gives us isomorphic \({\textbf{K}}\)-vector spaces in all degrees (with both \(\dim _{{\textbf{K}}} {\textrm{HH}}_1({\textbf{K}}{\mathcal {G}}_1)\) and \(\dim _{{\textbf{K}}} {\textrm{HH}}_1({\textbf{K}}{\mathcal {G}}_2)\) equal to 7).

Remarkably, the same homology theories can distinguish the associated line digraphs—the line digraphs having 2 and 1 connected components, respectively; as shown in the following illustration of the associated line digraphs:

This suggests that the directed combinatorics plays an important role. We give another example:

Example 3.8

Consider the following digraphs with reciprocal edges:

The associated directed flag complexes in both cases are topologically 2-spheres, hence their homology groups are isomorphic. A computation similar to the one in the previous example shows that the associated path homologies are also isomorphic. The Hochschild homology groups of the path algebras associated to the graphs \({\mathcal {S}}_1\) and \({\mathcal {S}}_2\) are also isomorphic (in degree 1 of infinite dimension over \({\textbf{K}}\), both digraphs having oriented cycle). Here follow the associated line digraphs:

Motivated by these examples, we proceed with investigating two examples of (simplicial) connectivity digraphs.

4.3 q-connectivity

Our first connectivity structure is an extension of Atkin’s Q-analysis (Atkin 1972) as developed in Riihimäki (2023). We briefly summarise this theory as needed for the purposes of this paper, and guide the reader to the previous references for more in-depth expositions. The essential idea in Atkin’s work is the generalisation of edge path connectivity of a simplicial complex to sequences of connected simplices through sharing of faces of certain dimension. Atkin was particularly motivated by the classic work of Dowker (1952): to any relation one can associate two simplicial complexes, nowadays known as Dowker complexes, but the homology groups of these complexes are isomorphic. Atkin’s insight was to associate to a simplicial complex his Q-analysis, which turns out to differentiate between the two Dowker complexes of a relation.

Definition 3.9

Let K be a simplicial complex. Two simplices \(\sigma \) and \(\tau \) of K are q-near, if they share a q-face. Two simplices \(\sigma \) and \(\tau \) of K are q-connected, if there is a sequence of simplices in K,

such that any two consecutive ones are q-near. The sequence of simplices is called a q-connection between \(\sigma \) and \(\tau \).

Similarly to the property of being path connected, we say that the complex K is q-connected if any two simplices in K of dimension greater than or equal to q are q-connected. The notion of q-connectivity is an equivalence relation on the set \(K_q\) of simplices of dimension q and higher, for \(0 \le q \le \dim (K)\).

The aim of Q-analysis is to associate a simplicial complex with its q-connectivity equivalence classes, or its q-connected components. Note that if a simplex \(\sigma \) is maximal in K with respect to inclusion and \(\text {dim}(\sigma ) = q\), then \(\sigma \) is q-connected only to itself; hence every maximal q-simplex generates its own equivalence class. For each q the equivalence classes encode the connectivity information of the q-upper skeleton of K. A related notion was introduced in Palla et al. (2005) to study community structures in networks.

Definition 3.10

Let \({\mathcal {G}}\) be a graph and \(n \ge 2\) a natural number. Two n-cliques in \({\mathcal {G}}\) are connected if there is a sequence of n-cliques of \({\mathcal {G}}\) such that any two consecutive cliques share \(n-1\) vertices. A n-clique community of \({\mathcal {G}}\) is a maximal set of pairwise connected n-cliques.

The n-cliques of a graph are in correspondence with the \((n-1)\)-simplices in the associated flag complex. The n-clique communities are obtained from the Q-analytical information of the flag complex. Note that we can put the n-cliques as vertices of a graph with edges between vertices if the associated cliques share \(n-1\) vertices. This leads us to define our first connectivity graph.

Definition 3.11

The q-graph of a simplicial complex K has as its vertices the simplices in \(K_q\) and edges between pairs of q-near simplices.

Standard Q-analysis as outlined above fails to take into account directionality in the case of digraphs and directed flag complexes. Consider the cycle and star digraphs in the figure below. As undirected graphs, or 1-dimensional simplicial complexes, they are indistinguishable by q-connectivity information: both contain one component so they are 0-connected, and the maximal 1-simplices each form their own 1-connected components in both cases.

We therefore introduce a refined version of Q-analysis that is sensitive to the directionality of simplices, or directed cliques in directed graphs. We do this by imposing directions through face maps.

Definition 3.12

Let \(\sigma \) be an n-simplex. We denote by \(\widehat{d_i}\) the face map

The face map \(\widehat{d_i}\) now makes sense in any dimension since it always removes the vertex at position \(\text {min}\{i,\text {dim}(v)\}\). The reason to modify the standard face map in this fashion is due to the fact that q-connectivity looks at all the simplices of dimension q and higher.

Definition 3.13

For an ordered simplicial complex K, let \((\sigma ,\tau )\) be an ordered pair of simplices \(\sigma \in K_s\) and \(\tau \in K_t\), where \(s,t \ge q\). Let \((\widehat{d_i},\widehat{d_j})\) be an ordered pair of the i- and j-face maps. Then \((\sigma ,\tau )\) is q-near along \((\widehat{d_i},\widehat{d_j})\) if either of the following conditions is true:

1. 1.

   \(\sigma \hookrightarrow \tau ,\)

2. 2.

   \(\widehat{d_i}(\sigma ) \hookleftarrow \alpha \hookrightarrow \widehat{d_j}(\tau ),\) for some q-simplex \(\alpha \in K\).

The ordered pair \((\sigma ,\tau )\) of simplices of K is q-connected along \((\widehat{d_i},\widehat{d_j})\) if there is a sequence of simplices in K,

such that any two consecutive ones are q-near along \((\widehat{d_i},\widehat{d_j})\). The sequence of simplices is called a q-connection along \((\widehat{d_i},\widehat{d_j})\) between \(\sigma \) and \(\tau \). We simply write this connection as \((\sigma \alpha _1 \alpha _2 \dots \alpha _n \tau )\).

We will call the above connection \((q,\widehat{d_i},\widehat{d_j})\)-connection, when the choices of q and directions \(\widehat{d_i}\) and \(\widehat{d_j}\) are made, and similarly we say \((q,\widehat{d_i},\widehat{d_j})\)-near.

The directed \((q,\widehat{d_i},\widehat{d_j})\)-connectivity is a preorder on the set of directed cliques \(K_q\). By the classical Alexandroff correspondence, preorders and topological spaces are in bijection (Barmak 2011). The \((q,\widehat{d_i},\widehat{d_j})\)-preorders thus endow a directed graph with a collection of new topological spaces. Up to homotopy it is enough to study partial orders obtained by condensing the preorders (Definition 1.10 and the discussion after). The homotopy types of partial orders can then be studied through their order complexes, i.e. taking the nerve.

As our main connectivity digraph stemming from q-connectivity we take the \((q,\widehat{d_i},\widehat{d_j})\)-nearness digraph in \(\textbf{Digraph}_+\) of the \((q,\widehat{d_i},\widehat{d_j})\)-connectivity preorder. For visualisation purposes we use the Hasse diagram form, i.e. we do not draw the self-loops on vertices.

Definition 3.14

For an ordered simplicial complex K the vertices in the \((q,\widehat{d_i},\widehat{d_j})\)-digraph, or simply q-digraph, are the simplices in \(K_q\), and for two vertices \(\sigma \) and \(\tau \) there is a directed edge \((\sigma ,\tau )\) when the pair \((\sigma ,\tau )\) is \((q,\widehat{d_i},\widehat{d_j})\)-near.

As an illustrative example we see that our new connectivity digraph can be used to distinguish prior Example 3.8; we refer the reader to Riihimäki (2023) for a more detailed investigations of these connectivity digraphs.

Example 3.15

The full \((1,\widehat{d_1},\widehat{d_2})\)-digraphs of the 2-spheres in Example 3.8 are shown below. We use simplified notation where a simplex \((v_0,v_1,\dots ,v_n)\) is denoted by \((v_0 v_1\cdots v_n)\).

The connectivity digraphs are different between the spheres. Passing to condensations and order complexes of the associated \((1,\widehat{d_1},\widehat{d_2})\)-preorders, the homotopy type of the left sphere is a wedge of circles \(S^1 \vee S^1\), while that of the right sphere is \(S^1\). The q-connectivity therefore assigns the underlying digraphs with new homotopy types that distinguish them.

In the next section we study our second example of a connectivity digraph, and show that it extends to an endofunctor on acyclic digraphs. The next example shows that the \((q,\widehat{d_i},\widehat{d_j})\)-digraph construction can not induce an endofunctor on acyclic digraphs, as it might yield digraphs with oriented cycles and self-loops.

Example 3.16

Consider the digraphs below and the morphism \(\phi :{\mathcal {G}}_1 \rightarrow {\mathcal {G}}_2\) defined on vertices as \(0 \mapsto 0'\), \(1 \mapsto 1'\), \(2 \mapsto 2'\), and \(3 \mapsto 0'\).

Morphisms of digraphs send simplices to simplices, in this case both (012) and (312) map to (0’1’2’). The induced morphism \(\tilde{\phi }\) between the \((1,\widehat{d_0},\widehat{d_0})\)-digraphs, as illustrated below, then acts on vertices as \((012) \mapsto (0'1'2')\), \((312) \mapsto (0'1'2')\), \((01) \mapsto (0'1')\), \((02) \mapsto (0'2')\), \((12) \mapsto (1'2')\), \((31) \mapsto (0'1')\), and \((32) \mapsto (0'2')\).

Note that the edges ((012), (312)) and ((312), (012)) are both sent to the self-loop on (0’1’2’); this is allowed in \(\textbf{Digraph}_+\) and also consistent with the fact that \((q,\widehat{d_i},\widehat{d_j})\)-digraphs inherently arise from the \((q,\widehat{d_i},\widehat{d_j})\)-connectivity preorders which have all the reflexive relations.

The example suggests the framework for studying the functoriality of \((q,\widehat{d_i},\widehat{d_j})\)-digraphs, as we now shall show. In particular, we do not get an endofunctor on \(\textbf{Digraph}\) or \(\textbf{Digraph}_0\), but take the target category to be \(\textbf{Digraph}_+\).

Theorem 3.17

The \((q,\widehat{d_i},\widehat{d_j})\)-digraph construction induces a functor from \(\textbf{Digraph}\) to \(\textbf{Digraph}_+\).

Proof

We write \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}}\) for the \((q,\widehat{d_i},\widehat{d_j})\)-digraph of a digraph \({\mathcal {G}}\). Let \(\phi :{\mathcal {G}}_1 \rightarrow {\mathcal {G}}_2\) be a morphism of digraphs. Simplices, i.e. ordered cliques, are mapped to simplices; recall Remarks 1.4 and 2.5. Hence, two simplices \(\sigma = (v_0,\dots ,v_n)\) and \(\tau = (w_0,\dots ,w_k)\) of dmension \(\ge q\) are mapped to simplices \(\phi (\sigma ) = (\phi (v_0),\dots ,\phi (v_n))\) and \(\phi (\tau ) = (\phi (w_0),\dots ,\phi (w_k))\) of dimension \(\ge q\). The edges in \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_1}\) coming from the face inclusions \(\sigma \hookrightarrow \tau \) are then trivially sent to edges in \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_2}.\)

Assume the nearness relation \(\widehat{d_i}(\sigma ) \hookleftarrow \alpha \hookrightarrow \widehat{d_j}(\tau )\) so an edge \((\sigma ,\tau )\) in \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_1}\). The q-simplex \(\alpha \) is mapped to a q-simplex \(\phi (\alpha )\) in \({\mathcal {G}}_2\). Note that there is an order-preserving bijection between the vertices \((v_0,\dots ,v_n)\) of \(\sigma \) and \((\phi (v_0),\dots ,\phi (v_n))\), and similarly for \(\tau \) and \(\phi (\tau )\), due to \(\phi \) being a morphism of digraphs. The face maps \(\widehat{d_i}\) and \(\widehat{d_j}\) then act the same way on \(\sigma \) and \(\phi (\sigma )\), and \(\tau \) and \(\phi (\tau )\), respectively, with respect to the orderings. Therefore, \(\alpha \) has to be a selection of vertices \((v_{i_0},\dots ,v_{i_q})\) from \((v_0,\dots ,{\widehat{v}}_i,\dots ,v_n)\) with the inherited ordering, and \((\phi (v_{i_0}),\dots ,\phi (v_{i_q}))\) is a q-simplex in \(\widehat{d_i}(\phi (v_0),\dots ,\phi (v_n))\). Similarly the vertices \((v_{i_0},\dots ,v_{i_q})\) constitute a q-simplex in \((w_0,\dots ,{\widehat{w}}_j,\dots ,w_n)\), and \((\phi (v_{i_0}),\dots ,\phi (v_{i_q}))\) is a q-simplex in \(\widehat{d_j}(\phi (w_0),\dots ,\phi (w_n))\). This amount to the nearness relation \(\widehat{d_i}(\phi (\sigma )) \hookleftarrow \phi (\alpha ) \hookrightarrow \widehat{d_j}(\phi (\tau ))\) and an edge \((\phi (\sigma ),\phi (\tau ))\) in \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_2}\).

A composition of morphisms of digraphs \({\mathcal {G}}_1 \rightarrow {\mathcal {G}}_2 \rightarrow {\mathcal {G}}_3\) still maps simplices to simplices, while keeping the dimensions \(\ge q\) and preserving the relative orderings of vertices. The argument above then induces a composition of morphisms \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_1} \rightarrow (q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_2} \rightarrow (q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}_3}\). The identity morphism on a digraph \({\mathcal {G}}\) obviously maps to the identity on \((q,\widehat{d_i},\widehat{d_j})_{{\mathcal {G}}}\). \(\square \)

4.4 The n-path digraph

Our second example of connectivity digraphs is given by the n-path digraphs \(\{\mathcal{P}\mathcal{G}^{(n)}\}_{n\in {\textbf{N}}}\). These are defined as the digraphs with the ordered \((n+1)\)-cliques of \({\mathcal {G}}\) as vertices, and with directed edges given by their incidence relations (see Definition 3.20). The construction is a generalization of the line digraph of Definition 1.7; furthermore, we will show that this construction can be promoted to an endofunctor on the category of digraphs \(\textbf{Digraph}\)—cf. Theorem 3.28.

Let n be a positive natural number and let \({\mathcal {G}}\) be a directed graph. We start by rephrasing the concept of q-graph of Definition 3.11, in the specific case in which the simplicial complex K is the directed flag complex of a digraph \({\mathcal {G}}\), the simplices have all the same fixed dimension, and the relation is the 1-codimensional q-nearness.

Definition 3.18

Let \({\mathcal {G}}\) be a digraph and let \({\textrm{dFl}}({\mathcal {G}})\) be its associated directed flag complex. The n-path graph \({\mathcal {G}}^{(n)}\) associated to \({\mathcal {G}}\) is the graph whose vertices are the n-simplices of \({\textrm{dFl}}({\mathcal {G}})\), and such that two vertices \(\sigma \) and \(\tau \) are connected by an edge whenever \(\sigma \) and \(\tau \) share a common \((n-1)\)-face.

Remark 3.19

Note that Definition 3.18 gives the underlying graph for the n-clique communities (Definition 3.10). The name n-path graph is then justified by the fact that simple paths in \({\mathcal {G}}^{(n)}\) correspond to ordered \((n+1)\)-cliques of \({\mathcal {G}}\), consecutively connected by common ordered n-cliques. If \({\mathcal {G}}\) is a digraph, then the 1-path graph \({\mathcal {G}}^{(1)}\) associated to \({\mathcal {G}}\) is nothing but the line graph \({\mathcal {L}}({\mathcal {G}})\) of the underlying undirected graph associated to \({\mathcal {G}}\)—cf. Definition 1.7.

Let \({\mathcal {G}}\) be a digraph, n be a natural number and \({\textrm{dFl}}({\mathcal {G}})\) be the associated directed flag complex. Based on Definition 3.18, we now define the n-path digraphs as the connectivity digraphs on the set of ordered \((n+1)\)-cliques with their incidence relations. The digraph structure is induced from the total order on \(\{0,\dots ,n\}\) which induces a total order on the associated face maps.

Definition 3.20

For \(n\ge 1\), the n-path digraph \(\mathcal{P}\mathcal{G}^{(n)}\) associated to \({\mathcal {G}}\) is the directed graph with the n-simplices of \({\textrm{dFl}}({\mathcal {G}})\) as vertices. For vertices \(\sigma \) and \(\tau \), there is a directed edge \((\sigma ,\tau )\) if and only if there is an \((n-1)\)-simplex \(\alpha \) of \({\textrm{dFl}}({\mathcal {G}})\) and some \(i,j \in \{0,\dots ,n\}\) such that

When \(n=0\), we set the 0-th path digraph \(\mathcal{P}\mathcal{G}^{(0)}\) to be the digraph \( {\mathcal {G}}\).

Note that the difference of n-path digraph from q-digraph (Definition 3.14) is that the vertices are only the n-simplices, and the edges are determined by the natural order on face maps; in the case of q-digraphs there is a choice of the \((q,\widehat{d_i},\widehat{d_j})\) involved. These two methods then yield different connectivity structures as shown in the next example—compare it with Example 3.15.

Example 3.21

Consider the digraphs \({\mathcal {S}}_1\) and \({\mathcal {S}}_2\) of Example 3.8. The associated 2-path digraph \(\mathcal{P}\mathcal{S}_1^{(2)}\) is the following:

The digraph \(\mathcal{P}\mathcal{S}_2^{(2)}\), instead, is a disconnected digraph with two connected components:

We investigate some properties of the n-path digraphs; first, note that these path digraphs generalize the notion of line digraphs:

Proposition 3.22

When \(n=1\), the 1-path digraph \(\mathcal{P}\mathcal{G}^{(1)}\) is isomorphic to the line digraph \({\mathcal {L}}({\mathcal {G}})\) of \({\mathcal {G}}\).

Proof

When \(n=1\), the vertices of \(\mathcal{P}\mathcal{G}^{(1)}\) are the edges of \({\mathcal {G}}\). The face map \(d_1\) applied to an edge e of \({\mathcal {G}}\), gives the source of e: \(d_1(e)=s(e)\). Analogously, we have the relation \(d_0(e)=t(e)\). Consequently, two edges e and f of \({\mathcal {G}}\) are connected in \(\mathcal{P}\mathcal{G}^{(1)}\) by a directed edge (e, f) if, and only if, they share a common vertex \(d_0(e)=d_1(f)\) in \({\mathcal {G}}\). Then the two constructions in Definitions 1.7 and 3.20 are equivalent. \(\square \)

For a digraph \({\mathcal {G}}\), denote by \({\textrm{Cone}}({\mathcal {G}})\) the cone digraph obtained from \({\mathcal {G}}\) by adding a new vertex \(v_P\) and, for each vertex v in \({\mathcal {G}}\), a new directed edge \((v,v_P)\); see Fig.   for an illustration.

The cone \({\textrm{Cone}}(C_n)\) of the coherently oriented cyclic digraph \(C_n\)

Full size image

Proposition 3.23

Let \(C_n\) be the coherently oriented cyclic digraph on n vertices, with \(n\ge 3\). Then the the 2-path digraph of the cone \({\textrm{Cone}}(C_n)\) is isomorphic to \(C_n\).

Proof

For \(n\ge 3\), if \(C_n\) is the cyclic digraph on n vertices with all the edges coherently oriented, then the cone \({\textrm{Cone}}(C_n)\) has 2-simplices based at the edges of \(C_n\). For each edge \((v_i,v_{i+1})\) in \(C_n\), the edge \((v_i,v_P)\) of \({\textrm{Cone}}(C_n)\) can be written as \(d_1(v_i,v_{i+1},v_P)=d_0(v_{i-1},v_{i},v_P)\) (where the indices i are taken modulo n). Then, it is easy to check that the associated 2-path digraph is isomorphic to \(C_n\). \(\square \)

The result generalizes by induction to every m: let \({\textrm{Cone}}^m({\mathcal {G}})\) denote the m-th iterated cone of \({\mathcal {G}}\), i.e. \({\textrm{Cone}}^m:={\textrm{Cone}}\circ \dots \circ {\textrm{Cone}}\), m times. Then, we have the following:

Proposition 3.24

Let \(C_n\) be the coherently oriented cyclic digraph on n vertices, with \(n\ge 3\). Then,

the m-path digraph of the m-th cone \({\textrm{Cone}}^m(C_n)\) of \(C_n\) is isomorphic (as a directed graph) to \(C_n\).

We have seen that, for every m, the m-path digraph can be an oriented cycle. Cycles of ordered n-cliques have a rigid structure, as each subsequent element in the sequence is determined by the preceding one, and by the face maps:

Remark 3.25

Let \(\sigma \) and \(\sigma '\) be two n-simplices of \({\textrm{dFl}}({\mathcal {G}})\), and assume \(d_i(\sigma )=d_j(\sigma ')\) for \(i<j\), and \(n>0\). If \(\sigma =(v_0,\dots ,v_n)\), denote by \(\sigma [h]\) the h-entry \(v_h\) of \(\sigma \). Then we have

and \(\sigma '[j]\) is the vertex in which \(\sigma \) and \(\sigma '\) differ. For example, assume \(\sigma =(0,1,2,3)\) and \(\sigma '=(1,4,2,3)\); then \(d_0(\sigma )=d_1(\sigma ')\) and here the face maps correspond to the indices \(i=0\), and \(j=1\). When \(h=i=0\), we have \(\sigma '[0]=\sigma [1]\), and \(\sigma '[h]=\sigma [h]\) for \(h=2,3\); on the other hand, when \(h=j\) (case \(h=j=1\)), we have \(\sigma '[h]=4\), the vertex in which \(\sigma \) and \(\sigma '\) differ.

Such rigidity implies that taking n-path digraphs preserves acyclicity:

Proposition 3.26

The n-path digraph \(\mathcal{P}\mathcal{G}^{(n)}\) of a digraph \({\mathcal {G}}\) without oriented cycles does not have oriented cycles.

Proof

We proceed by contradiction. Assume \(\mathcal{P}\mathcal{G}^{(n)}\) has an oriented cycle \(\gamma \) given by n-simplices

of \({\textrm{dFl}}({\mathcal {G}})\). All the discussion below is given modulo k.

The oriented cycle in Eq. (6) corresponds to a closed path of ordered \((n+1)\)-cliques of \({\mathcal {G}}\), and for each \(\sigma _h\rightarrow \sigma _{h+1}\) there are indices \(i_h\) and \(j_{h}\) such that \(d_{i_h}(\sigma _h)=d_{j_h}(\sigma _{h+1})\), with \(i_h<j_{h}\). Without loss of generality assume that \(i_h=0\) for some h—otherwise let \(i=\min \{i_h\mid h=0,\dots ,k\}\) and replace in the discussion below the index 0 with such minimal index i.

Starting with the cycle \(\gamma \), it is now possible to construct oriented closed paths in \({\mathcal {G}}\) as follows. First, as \(i_h=0\) for some h, then we have \(\sigma _h[1]=\sigma _{h+1}[0]\) by Remark 3.25. Furthermore, as the simplex \(\sigma _h\) represents an ordered clique of \({\mathcal {G}}\), this means that there is a directed edge \(e_h\) between the 0-th and 1-st entry of \(\sigma _h\), i.e. \(e_h:=(\sigma _h[0],\sigma _h[1])\), and we can see \(e_h\) as an edge between the vertices \(\sigma _h[0]\) and \(\sigma _{h+1}[0]\). The idea is now to use these edges \(e_h\) to construct a cycle \(\gamma _0\) in \({\mathcal {G}}\). To this goal, consider only the indices h in \(\{0,\dots ,k\}\) for which \(i_h=0\), say \({h_0},\dots ,{h_s}\). For all other indices r, we have \(\sigma _r[0]=\sigma _{h_r+1}[0]\), where \(h_r:=\min _{{h_0},\dots ,{h_s}}\{h_j<r\}\). Then, starting with \(v_0:=\sigma _0[0]=\sigma _{{h_0}}[0]\), we have the sequence of edges

terminating again in \(v_0\), as \(\gamma \) was a cycle of simplices. But, this is not possible because \({\mathcal {G}}\) has no oriented cycles, leading to a contradiction. \(\square \)

In the next example we show that the directed structure inherited by the path digraphs is more informative than the undirected one. We apply the constructions of Definitions 3.18 and 3.20 to the digraphs shown in Example 3.7:

Example 3.27

Let \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\) be the graphs of Example 3.7. The 2-path graphs \({\mathcal {G}}_1^{(2)}\) and \({\mathcal {G}}_2^{(2)}\) have three vertices, corresponding to the three 2-simplices, and two edges, corresponding to the two edges in common; the obtained path graphs are isomorphic. On the other hand, the associated 2-path digraphs \(\mathcal{P}\mathcal{G}_1^{(2)}\) and \(\mathcal{P}\mathcal{G}_1^{(2)}\) are not isomorphic. In fact, we have the digraph structures

showing that the extension from 2-path graphs to 2-path digraphs provides additional non-trivial information.

We finish by establishing our main result concerning n-path digraphs, which is their functoriality.

Theorem 3.28

For each n in \({\textbf{N}}\),

is an endofunctor of the category of directed graphs.

Proof

First, note that if \(n=0\), then \({\mathcal {P}}^{(n)}\) is the identity functor by definition; if \(n=1\), then, by Proposition 3.22, \({\mathcal {P}}^{(n)}\) coincides with the line digraph functor (see Remark 1.8).

Let now \(n \ge 2\). We first observe that, if a digraph \({\mathcal {G}}\) has no ordered \((n+1)\)-cliques, then the associated n-path digraph is the empty digraph. By Remark 1.4, a morphism of digraphs \(\phi :{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\) induces a function between the sets of \((n+1)\)-cliques. As a consequence, if \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\) are two digraphs and the set of \((n+1)\)-cliques of \({\mathcal {G}}_2\) is empty, then the set \({\textrm{Hom}}_{\textbf{Digraph}}({\mathcal {G}}_1,{\mathcal {G}}_2)\) of morphisms of digraphs between \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\) is also empty. By Remark 2.5 we also have an induced function between the sets of ordered \((n+1)\)-cliques of \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\), that preserves the relative order of the faces. This function may not be surjective (there might be cliques that are not images of any clique in \({\mathcal {G}}_1\)) nor injective (as it may send different cliques to the same one).

For a morphism of digraphs \(\phi :{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\), we have got a function \({\mathcal {P}}^{(n)}(\phi )\) between the sets of vertices of the associated n-path digraphs. We now want to promote it to a morphism of n-path digraphs. To this end, let \(c,c'\) be two ordered \((n+1)\)-cliques of \({\mathcal {G}}_1\), and let \(\sigma _c\) and \(\sigma _{c'}\) be the associated n-simplices in \({\textrm{dFl}}({\mathcal {G}}_1)\). It may happen that \({\mathcal {P}}^{(n)}(\phi )\) sends both \(\sigma _c\) and \(\sigma _{c'}\) to the same simplex of \({\textrm{dFl}}({\mathcal {G}}_2)\). However, observe that if \(\sigma _c\) and \(\sigma _{c'}\) share an \((n-1)\)-face \(\tau \), and are sent to the same n-simplex of \({\textrm{dFl}}({\mathcal {G}}_2)\), then the ordered \((n+1)\)-cliques \(c,c'\) share the face \(\tau \) such that there exists an index i with \(d_i(\sigma _c) = d_i(\sigma _{c'})=\tau \) (as the linear ordering should be preserved). Therefore, if \(\sigma _c\) and \(\sigma _{c'}\) are collapsed to the same vertex of \(\mathcal{P}\mathcal{G}_2^{(n)}\), then \(\sigma _c\) and \(\sigma _{c'}\) represent two non-adjacent vertices of \(\mathcal{P}\mathcal{G}_1^{(n)}\). Furthermore, the relative incidence relations are preserved, and the morphism of digraphs \(\phi :{\mathcal {G}}_1\rightarrow {\mathcal {G}}_2\) induces a function \({\mathcal {P}}^{(n)}(\phi )\) such that \(({\mathcal {P}}^{(n)}(\phi )(\sigma _c),{\mathcal {P}}^{(n)}(\phi )(\sigma _{c'}))\in \mathcal{P}\mathcal{G}_2^{(n)}\) for every \((\sigma _c,\sigma _{c'})\) belonging to \(\mathcal{P}\mathcal{G}_1^{(n)}\), i.e. \({\mathcal {P}}^{(n)}(\phi )\) is a morphism of digraphs.

To conclude, it is now easy to see that \({\mathcal {P}}^{(n)}\) of the identity is the identity and that, if \(\phi _1\) and \(\phi _2\) are morphisms of digraphs, then \({\mathcal {P}}^{(n)}(\phi _1\circ \phi _2)={\mathcal {P}}^{(n)}(\phi _1)\circ {\mathcal {P}}^{(n)}(\phi _2)\). This shows that \({\mathcal {P}}^{(n)}\) is an endofunctor of the category \(\textbf{Digraph}\). \(\square \)

By Proposition 3.26, we get also the functoriality when restricting to acyclic digraphs:

Proposition 3.29

The funtor \({\mathcal {P}}^{(n)}\) restricts to a functor \(\textbf{DiGraph}_0\rightarrow \textbf{DiGraph}_0\) on the category of finite digraphs without oriented cycles.

Remark 3.30

The idea behind Definition 3.20 corresponds to the intuition that flows in a directed graph follow the direction of the edges, from the source to the target. As we have remarked in Lemma 3.22, the source and target of a directed edge are given by the face maps \(d_1\) and \(d_0\), respectively. The condition \(i<j\) in the construction of the path digraph follows and generalizes this principle to the higher simplices as well. This condition can be relaxed to \(i\le j\), which has the effect that the path digraphs might have reciprocal edges, and therefore oriented cycles.

As described in Sect. 2.1, one of the possible approaches to a homology theory of digraphs is given by the ordinary homology of the associated directed flag complexes; recall that this is constructed by using the set of ordered cliques in a digraph. When applied to 1-path digraphs, we have the following consequence:

Remark 3.31

Let \({\mathcal {G}}\) be a digraph without oriented cycles. Then, the directed flag complex \({\textrm{dFl}}(\mathcal{P}\mathcal{G}^{(1)}({\mathcal {G}}))={\textrm{dFl}}({\mathcal {L}}({\mathcal {G}}))\) of the 1-path digraph has simplices of dimension at most 1.

The above remark is not true for n-path digraphs. For example, it is easy to see that the 2-path digraphs may contain 3-cliques, and as a consequence the associated directed flag complexes can possibly be of dimension at least 2:

Example 3.32

Consider the digraph \({\mathcal {G}}\) on five vertices with directed edges as follows:

Then \({\mathcal {G}}\) contains three ordered cliques, corresponding to the simplices (0, 1, 2), (1, 2, 3) and (1, 4, 2). The boundary relations show that the associated 2-path digraph is the ordered clique on three vertices, and the associated directed flag complex is a 2-simplex.

In the case of q-connectivity the homotopy types of the connectivity digraphs can be studied through the order complex construction, recall Example 3.15. Analogously, it is then natural to ask what is the dimension of the directed flag complex of an n-path digraph, and what is its homotopy type:

Question 3.33

For a given digraph \({\mathcal {G}}\), what is the homotopy type of the directed flag complex associated to \(\mathcal{P}\mathcal{G}^{(n)}\), or to the relaxed n-path digraph of Remark 3.30? What are the distributions of the associated Betti numbers like?

A partial answer to this is given in Riihimäki (2023) when \({\mathcal {G}}\) is the 1-skeleton of so called pseudomanifold; for example, the Cone(\(C_n\)) in Fig. 5 is an example of a directed 2-pseudomanifold. In this case the directed flag complexes of the connectivity digraphs we have considered are 1-dimensional. The digraph in Example 3.32 does not have the structure of a 2-pseudomanifold: there is a "singular" edge (1, 2) to which three different 2-simplices are attached. We conclude this section with examples showing that the digraphs of Examples 3.7 and 3.8 can now be distinguished by using the homology groups associated to the 2-path digraphs:

Example 3.34

Consider the digraphs \({\mathcal {G}}_1\) and \({\mathcal {G}}_2\) illustrated in Example 3.7. The associated 2-path digraph \(\mathcal{P}\mathcal{G}_1^{(2)}\)—cf. Example 3.27—has two connected components, whereas the 2-path digraph \(\mathcal{P}\mathcal{G}_2^{(2)}\) has one connected component. Then all the homology theories described in Sect. 2 can now distinguish the two digraphs.

Example 3.35

For the digraphs \({\mathcal {S}}_1\) and \({\mathcal {S}}_2\) of Example 3.8 the associated 2-path digraphs \(\mathcal{P}\mathcal{S}_1^{(2)}\) and \(\mathcal{P}\mathcal{S}_2^{(2)}\) have one and two connected components, respectively. Again, all the homology theories described in Sect. 2 can distinguish these two digraphs representing 2-spheres.

The goal of this section is to introduce a persistent homology framework for Hochschild homology of directed graphs, using connectivity digraphs as an intermediate step. One of the disadvantages of Hochschild homology for digraphs is that it is trivial in degrees \(i\ge 2\). The use of connectivity digraphs is meant to solve this issue. We first show that the n-path digraphs introduced in Sect. 3.4 allow us to construct a persistent homology functorially in the case of acyclic digraphs. We then extend the persistence pipeline to general digraphs; we lose functoriality but we obtain a new persistence descriptor for digraphs.

5.1 Persistent Hochschild homology of acyclic digraphs

In this subsection we mainly follow Bergomi and Vertechi (2020), where an abstract categorical framework in which to develop persistent homology theories has been introduced. In this framework, one replaces filtrations of topological spaces with filtrations in an arbitrary category (for us, the category of directed graphs) and the homology functors with any functor with values in a regular ranked category (for us, Hochschild homology over a field \({\textbf{K}}\)), compare with Bergomi and Vertechi (2020, Table 1). To accomplish our aims we could have also used the generalised persistence of Patel (2018); we think, however, that the theory in Bergomi and Vertechi (2020) provides a more straightforward passage to our aims.

We start by considering the poset \(({\textbf{R}}, \le )\) of real numbers with the induced natural partial order \(\le \). The poset \(({\textbf{R}}, \le )\) can be seen as a category in a standard way, as every poset can be seen as a category: the category \({\textbf{P}}\) associated to a poset \(P=(S,\le )\) has the set S as a collection of objects and a (unique) morphism \(x\rightarrow y\) for any \(x\le y\). A morphism of posets is then a functor between them, equivalently an order-preserving map of posets.

In persistent homology applications, one usually considers diagrams of spaces indexed by the natural numbers, or more generally by the real numbers. These diagrams are referred to as filtrations:

Definition 4.1

A (real-indexed) filtration in a category \({\textbf{C}}\) is a functor \({\mathcal {F}}:({\textbf{R}}, \le )\rightarrow {\textbf{C}}\).

Remark 4.2

Following Bergomi and Vertechi (2020) we will always consider tame filtrations. Essentially, a filtration \({\mathcal {F}}\) is tame if there is a finite sequence \(\{t_i\}_{i \in {\textbf{N}}}\) such that \({\mathcal {F}}(a) \rightarrow {\mathcal {F}}(b)\) may fail to be an isomorphism only if \(a < t_i \le b\) for some i. The concept of tameness extends to subposets of \(({\textbf{R}}, \le )\).

Example 4.3

Let \(\{{\mathcal {G}}_n\}_{n\in {\textbf{N}}}\) be a family of digraphs, with \({\mathcal {G}}_n\rightarrow {\mathcal {G}}_{n+1}\) a morphism of digraphs for each \(n\in {\textbf{N}}\). Then, the family \(\{{\mathcal {G}}_n\}_{n\in {\textbf{N}}}\) yields a filtration \(({\textbf{N}}, \le ) \rightarrow \textbf{Digraph}\); if we assume \({\mathcal {G}}_n\) to be without oriented cycles, the filtration takes values in \(\textbf{Digraph}_0\). Observe that if \(\{{\mathcal {G}}_n\}_{n\in {\textbf{N}}}\) is a family of subgraphs of a given directed graph \({\mathcal {G}}\), then by Remark 4.2 the resulting filtration is tame.

Let \({\mathcal {F}}\) be a filtration in \(\textbf{Digraph}_0\). In the following discussion, we restrict to the n-path digraph functor \(\mathcal{P}\mathcal{G}^{(n)}\), but everything is the same by replacing \(\mathcal{P}\mathcal{G}^{(n)}\) with any functorial construction of connectivity digraphs. By Theorem 3.28, composition with the n-path digraph functor \(\mathcal{P}\mathcal{G}^{(n)}\) induces, for each n in \({\textbf{N}}\), a filtration in \(\textbf{Digraph}_0\); by Proposition 3.26, the n-path digraph of a digraph without oriented cycles does not have oriented cycles. We then get the following composition of functors:

Let \(\textbf{FinVect}\) be the category of finite dimensional vector spaces over an algebraically closed field \({\textbf{K}}\). By Remark 2.27, the Hochschild homology groups yield functors with values in \(\textbf{FinVect}\).

Remark 4.4

The category \(\textbf{FinVect}\), equipped with the dimension function assigning to a vector space its dimension, is a ranked category—cf. Bergomi and Vertechi (2020, Definition 2.1).

Before putting all together, we need the definition of a persistence function, generalizing persistent Betti numbers from classical persistent homology:

Definition 4.5

(Bergomi and Vertechi 2020, Definition 3.2) Let \({\textbf{C}}\) be a category. An integer-valued lower-bounded function p on the morphisms of \({\textbf{C}}\) is a categorical persistence function if, for all \(u_1\rightarrow u_2\rightarrow v_1 \rightarrow v_2\) the following hold:

1. 1.

   \(p(u_1\rightarrow v_1)\le p(u_2\rightarrow v_1)\) and \(p(u_2\rightarrow v_2)\le p(u_2\rightarrow v_1)\);

2. 2.

   \(p(u_2\rightarrow v_1)- p(u_1\rightarrow v_1)\ge p(u_2\rightarrow v_2)- p(u_1\rightarrow v_2)\).

Let \({\mathcal {F}}:({\textbf{R}}, \le ) \rightarrow \textbf{Digraph}_0\) be a filtration, and consider the following composition of functors:

By Bergomi and Vertech (2020, Proposition 3.6), any functor \({\textbf{C}}\rightarrow \textbf{FinVect}\) yields a categorical persistence function. In order to get an analogue of persistent Betti numbers usually associated to pairs of real numbers, it is then sufficient to have a filtration and a categorical persistence function (Bergomi and Vertechi 2020, Remark 3.8). In our context, \({\mathcal {F}}:({\textbf{R}}, \le ) \rightarrow \textbf{Digraph}_0\) is a filtration, and the composition of functors in (7) yields the categorical persistence function. Furthermore, for each pair of real numbers \(u\le v\), Hochschild homology gives the linear maps

of finite dimensional vector spaces. By taking the images of these maps, we get the desired persistent Betti numbers:

Definition 4.6

The (n, 1)-persistent Betti number of a filtration in \(\textbf{Digraph}_0\) is the persistent Betti number induced by \({\textrm{HH}}_1({\textbf{K}}\mathcal{P}\mathcal{G}_u^{(n)})\rightarrow {\textrm{HH}}_1({\textbf{K}}\mathcal{P}\mathcal{G}_v^{(n)})\), in dimension 1. The (n, 0)-persistent Betti number for dimension 0 is defined analogously.

Remark 4.7

Note that degrees of Hochschild homology are only 0 and 1. The higher "homological" degrees n, and the n-th Betti numbers, are defined by the connectivity digraphs of n-simplices. This is in our view the lifting of Hochschild homology beyond degree 1.

In this functorial framework, given a categorical persistence function p and a (tame) filtration \({\mathcal {F}}\), it is possible to define a persistence diagram \(D{\mathcal {F}}\) as well (Bergomi and Vertechi 2020). In the case of real-indexed filtrations, the morphisms \(u \le v \in {\textbf{R}}\) are in bijection with the positive half-plane \(\Delta ^+ = \{(u,v) \in {\textbf{R}}^2 \ | \ u \le v\}\). We therefore get an induced persistence function \(p_{\mathcal {F}} :\Delta ^+ \rightarrow {\textbf{Z}}\) given by \((u,v) \mapsto p({\mathcal {F}}(u \le v))\). For \(u < v\) we define the multiplicity \(\mu (u,v)\) as

where \(I_u\) and \(I_v\) range over disjoint connected neighborhoods of u and v. The persistence diagram \(D{\mathcal {F}}\) associated to \(p_{\mathcal {F}}\) is then defined by those points (u, v) such that \(\mu (u,v) > 0\), together with the diagonal \(\{(u,u)\mid u\in [0,\infty )\}\) (Bergomi and Vertechi 2020, Definition 6). Note that for small enough neighborhoods \(I_u\) and \(I_v\) we have \(\text {inf}(I_u) \rightarrow \text {sup}(I_u) \rightarrow \text {inf}(I_v) \rightarrow \text {sup}(I_v)\), and the above minimized expression is exactly that of condition 2. in Definition 4.5 with strict inequality.

We get an immediate stability theorem, in fact an isometry theorem, between our Hochschild homology valued filtrations and their persistence diagrams. Let \(d_{\textbf{FinVect}}({\mathcal {F}},{\mathcal {G}})\) be the interleaving distance between two filtrations \({\mathcal {F}},{\mathcal {G}} :({\textbf{R}}, \le ) \rightarrow \textbf{FinVect}\) and let \(d(D{\mathcal {F}},D{\mathcal {G}})\) be the bottleneck distance between the associated persistence diagrams.

Theorem 4.8

Let \(\mathcal {F,G}:({\textbf{R}}, \le )\rightarrow \textbf{Digraph}_0\) be two filtrations of digraphs. Then,

where \(D{\mathcal {F}}\) and \(D{\mathcal {G}}\) represent the persistence diagrams associated to \({\mathcal {F}}\) and \({\mathcal {G}}\).

Proof

The proof follows directly from Bergomi and Vertech (2020, Theorem 3.27 and 3.29). \(\square \)

The theorem says that the persistent Hochschild homology groups associated to a filtration of digraphs are stable, one of the main required properties in persistent homology applications. We refer to this as persistent Hochschild homology (PHH). Note that, in the terminology of Bubenik et al. (2015), we have introduced a generalised persistence along with a hard stability theorem: the map from persistence modules to discrete invariants is 1-Lipschitz. This still leaves open the (very hard) problem of proving a stable persistent Hochschild homology pipeline starting from the space of (acyclic) digraphs. The main obstacle here lies in the difficulty of having an appropriate metric for digraphs that behaves well with filtrations.

Note that persistent Hochschild homology does not behave as the usual persistent homology; in fact, we have the following:

Remark 4.9

Consider an edge weighted directed graph \({\mathcal {G}}\), and consider the filtration induced by sorting the weights in an increasing order—the first digraph in the sequence being the spanning subgraph on the vertices of \({\mathcal {G}}\). Then, generators in persistent Hochschild homology applied to such filtration always persist until \(\infty \). Therefore we cannot talk about births and deaths as is usually done in the context of barcodes.

Similarly, as for Hochschild homology, we can consider compositions

involving the homology of directed flag complexes, or the path homology functors. For \(n=0\), these compositions yield the usual persistent homology in the first case, and the persistent path homology introduced in Chowdhury and Mémoli (2018), in the second. Henceforth, composition with the higher connectivity digraphs allows us to extend the usual classical pipelines. As the homology functors—of the directed flag complex \({\textrm{dFl}}\) and of the path complex P associated to finite digraphs, when considering coefficients in a field—take values in finite dimensional vector spaces, the same discussion of the section repeats verbatim, yielding the following:

Theorem 4.10

Let \(\mathcal {F,G}:({\textbf{R}}, \le )\rightarrow \textbf{Digraph}_0\) be two filtrations of digraphs. Then, for each \(i\in {\textbf{N}}\) we get:

and

where \(D{\mathcal {F}}\) and \(D{\mathcal {G}}\) represent the persistence diagrams associated to \({\mathcal {F}}\) and \({\mathcal {G}}\).

The connectivity digraphs could be substantiated much more, for example, by trying to understand their homotopy types and how those might relate to the underlying digraphs, see the discussion around Question 3.33; this is an ongoing work of the authors. From persistence point of view the filtrations of digraphs could be produced from some derived filtrations, in the same vein as in standard persistence of finite metric spaces one might employ eccentricity or curvature filtrations. For digraphs one interesting example comes from the discrete Forman-Ricci curvature extended to directed networks (Saucan et al. 2019). We believe this connection of structurally interesting filtrations and connectivity digraphs might be of interest and would lead to new avenues in analysing the structure of digraphs.

5.2 A persistent Hochschild homology pipeline for directed graphs

As seen in the previous section, Hochschild homology gives rise to a persistence function when considering directed graphs without oriented cycles; however, this approach fails with graphs having oriented cycles, due to Proposition 2.22. We now introduce a persistence-like framework for Hochschild homology that extends our set-up to the whole category \(\textbf{Digraph}\).

Our pipeline proceeds as follows:

1. 1.

   We start with a filtration \({\mathcal {F}}:({\textbf{R}}, \le ) \rightarrow \textbf{Digraph}\).

2. 2.

   At each filtration step t we obtain a connectivity digraph \(E{\mathcal {F}}_t\) by applying the n-path digraph \({\mathcal {P}}^{(n)}\) for some n, or the q-digraph for some \((q,\widehat{d_i},\widehat{d_j})\), or any other connectivity digraph construction (possibly non-functorial).

3. 3.

   The resulting digraphs \(E{\mathcal {F}}_t\) can in general have oriented cycles. We therefore consider the condensation \(c(E{\mathcal {F}}_t)\) (Definition 1.10).

4. 4.

   By Remark 1.11, \(c(E{\mathcal {F}}_t)\) does not have oriented cycles. Hence, we compute the Hochschild characteristic \({\mathcal {X}}_{{\textrm{HH}}}(c(E{\mathcal {F}}_t)) = \dim _k {\textrm{HH}}_0(A)-\dim _k {\textrm{HH}}_1(A)\), where A is the associated path algebra. Note that \(\dim _k {\textrm{HH}}_0(A)\) agrees with the number of connected components and \(\dim _k {\textrm{HH}}_1(A)\) with the formula \(1-n +\sum _{e\in E({\mathcal {G}})}\dim _k e_{t(e)}A e_{s(e)}\) of Theorem 2.25. As the digraph \(c(E{\mathcal {F}}_t)\) does not have oriented cycles, this is exactly the characteristic introduced in Definition 2.29.

Diagrammatically, we have:

Note that the process lands in the category of finite vector spaces. Even though E might be functorial, as we have introduced two examples in this paper, the composition is not functorial anymore due to condensation c; we refer to the discussion after Remark 1.11.

Remark 4.11

Observe that taking the condensation of a digraph and the connectivity digraphs do not commute. In particular, killing the cycles in the condensation process may kill also ordered cliques; this is the reason why we first apply E and then the condensation c.

We demonstrate our persistent Hochschild homology pipeline, by applying it to the filtrations of the following digraphs:

• Random Erdös-Rényi (ER) digraph with probability 0.5 for directed edges between any pair of vertices. We make it randomly edge weighted by replacing each non-zero entry of the adjacency matrix with a value sampled uniformly from [0, 1).

• Random necklace digraph, as represented in Fig. . Similarly, to make it random we first construct the associated adjacency matrix, which has ones on the first upper and lower diagonals, and we then replace these with a value sampled uniformly from [0, 1).

The necklace digraph

Full size image

In both examples, we take the digraph filtration induced by the random entries of the associated adjacency matrices: at a filtration value t we take the digraph induced by keeping only edges whose weight is \(\le t\). The digraphs we used had 20 vertices, so were represented by \(20 \times 20\) adjacency matrices.

Figure  shows the persistent Hochschild characteristics for the random Erdös-Rényi and necklace digraphs, and for their associated 1-path digraphs. Figure  shows the results for q-digraphs with \((q,\widehat{d_i},\widehat{d_j})\) equal to \((q,\widehat{d_0},{\widehat{d}}_{q+1})\) for \(q \in \{1,2,3,4\}\) for the random Erdös-Rényi, and \((0,\widehat{d_0},\widehat{d_1})\) for the necklace digraph; for ease of notation we write \((q,\widehat{d_i},\widehat{d_j})\) as (q, i, j) in the remainder of the paper.

As observed in Remark 4.9, generators in persistent Hochschild homology always persist until \(\infty \), and therefore the associated Betti curves yield monotone functions. Experiments involving the persistent Hochschild characteristics of random ER digraphs, and more structured necklace digraphs—cf. Fig. 7—show instead that the associated curves are not monotone. This is caused by the condensation step in the pipeline introduced in this section. Condensation also has the effect of reducing the number of edges and paths in the graph, a number that is correlated to the first Hochschild homology group—cf. Theorem 2.25. The effect of condensation is seen in the plots as zig-zagging; particularly large positive jumps correspond to large cyclic components being killed.

Note that a common feature in all plots is that the early parts of the filtrations are dominated by the connected components. This occurs until a certain saturation point in which more structured graphs appear and the number of edges, paths, and of oriented cycles, is more prominent. It is interesting to note that this saturation point is reached very soon when dealing with random digraphs and much later for the necklace digraphs. Essentially this is observed in the plots when the value of \({\mathcal {X}}_{{\textrm{HH}}}\) drops to negative. The plots for ER q-digraphs also begin slightly positive before more paths begin to dominate dropping the values very negatively. Exception is the ER (4,0,5)-digraph: due to the required high-dimensional connecting faces the digraphs are predominantly rather empty of edges and dominated by connected components.

When oriented cycles are more likely to be created with long paths, the variations in \({\mathcal {X}}_{{\textrm{HH}}}\) are stronger. Compare this effect on the persistent Hochschild characteristics of random ER digraphs and of necklace digraphs in Fig. 7. Necklace digraphs, perturbed with addition of white noise, present small cycles, so that the persistent Hochschild characteristics is changing almost linearly. Changing the associated connectivity digraph may change completely the behaviour of \({\mathcal {X}}_{{\textrm{HH}}}\). Note the change in the persistent Hochschild characteristics associated to the line digraphs of the same random and necklace digraphs.

Finally, we remark that the \({\mathcal {X}}_{{\textrm{HH}}}\) of the q-digraphs in Fig. 8 show drastically larger values compared to Fig. 7. Recall that these digraphs have as vertices all the simplices of dimension \(\ge q\). The simplicial face inclusions are also always near resulting in edges (Definition 3.13). Therefore the q-digraphs are larger and more dominated by paths along the filtration. This is particularly visible in the plot for ER (2,0,3)-digraph.

Persistent Hochschild characteristics. Left: condensed digraph and condensed 1-path digraph of a random Erdös–Rényi. Right: condensed digraph and condensed 1-path digraph of a random necklace digraph. Both digraphs had 20 vertices

Full size image

Persistent Hochschild characteristics. Left: condensed q-digraphs of a random Erdös–Rényi. Right: condensed q-digraph of a random necklace digraph. The choices for (q, i, j) are shown in the figures. Both digraphs had 20 vertices

Full size image

As already mentioned, the pipeline we have introduced uses the condensation of a digraph to kill the oriented cycles. By producing acyclic digraphs, this also has an effect in the computational efficiency since many graph algorithms, for example finding paths, have lower complexity; this was taken advantage of in Riihimäki (2023) for computing q-connected pathways of simplices. Other approaches are possible, for example in Kaul and Tamaki (2020, Algorithm 1) a Berger and Shor algorithm (Berger and Shor 1990) has been used for the same task. Using condensation leads to our pipeline not being functorial, and we do not know if the persistent Hochschild characteristic defined this way is stable in the sense of Theorem 4.8; this leaves open the following question:

Question 4.12

Is it possible to modify the composition of Eq. (8) in a functorial way? Is the composition of Eq. (8) stable in the sense of Theorem 4.8?

5.3 Persistent Hochschild homology of the C. elegans network

As an application of the pipeline (8) to real-world data, we analysed the neuronal network of the C. elegans organism (Varshney et al. 2011); in this network vertices are neurons and directed edges represent pre-post-synaptic connections. The synaptic connectivity is obtainable from Altun et al. (2023) and we used the steps in Govc (2020) to construct the directed graph, which has 279 vertices and 2194 edges. The computations demonstrate that our proposed pipeline can be taken as the first steps in computational (persistent) Hochschild homology, and the analysis below is meant to provide insight into how one might use this approach in concrete network analysis.

The network data contains the synaptic strengths, i.e. each edge has an integer weight in the interval [1, 37]; note that not every value appears as an edge weight. These weights allow to define a natural synaptic filtration of the full digraph \({\mathcal {G}}\): for \(t \in [1,37]\) we take \({\mathcal {G}}_t \subseteq {\mathcal {G}}\) to be the subgraph induced by all edges with weight \(\le t\).

Persistent Hochschild homology of the synaptic filtration of the C. elegans digraph. Left: n-path digraphs. Right: (q, i, j)-digraphs

Full size image

Figure  shows the persistent Hochschild characteristics over the synaptic filtration, for various n-path digraphs and q-digraphs. The choice of the triple (q, i, j) is only exemplary, and was selected to be different from the examples in the previous section. For more about the Q-analysis of C. elegans see Riihimäki (2023). To gain more insight into the behaviour of \({\mathcal {X}}_{{\textrm{HH}}}\) we also show in Fig.  the numbers of vertices, connected components, and strongly connected components in the n-path digraphs and (q, i, j)-digraphs over the synaptic filtration. In all the plots we see a flattening of the curves around synaptic weight 17. This indicates that addition of new simplices along with higher weight edges happens so sparsely within the network, that it does not change the structure of n-path or q-digraphs in any meaningful way.

Numbers of vertices, connected components, and strongly connected components of the synaptic filtration of the C. elegans digraph. Left: n-path digraphs. Right: (q, i, j)-digraphs

Full size image

Recall that the Hochschild characteristic \({\mathcal {X}}_{{\textrm{HH}}}\) for (not necessarily connected) acyclic digraphs is computed as \(\# \text {components} -1 + \# \text {vertices} - \sum _{\text {edges} \ e} \#\{s(e)-t(e)\text {-paths}\}\). This quantity is computed after condensation. For the 2-path digraph we see that in the early parts of the filtration the numbers of components and strong components rise sharply. Particularly strong components are nearly half of the number of vertices indicating that there are many reciprocally connected pairs of simplices. While the 2-path digraph becomes more connected along the filtration, as seen by the sharp decline in the number of components, the number of strong components stays rather constant. The value of \({\mathcal {X}}_{{\textrm{HH}}}\), however, is very negative along the full filtration. These observations seem to indicate that, even after condensing the strong components, the 2-path digraph is dominated by paths of 2-simplices connected through shared 1-faces. This interpretation is in fact consistent with the known structure of the C. elegans digraph: there is an over-representation of 2- and 3-cliques with reciprocal edges (Varshney et al. 2011). The behaviour of 3-, 4- and 5-path digraphs seems to follow that of 2-path digraph; the sharp rise of \({\mathcal {X}}_{{\textrm{HH}}}\) at filtration values 2–5 is most likely the effect of condensing away many edges.

The q-digraphs exhibit very large negative values of \({\mathcal {X}}_{{\textrm{HH}}}\). This is largely dominated by the contribution of edges: recall that each simplicial face inclusion is q-near, hence contributing an edge. Predominantly due to this, in contrast to 2- and 3-path digraphs, the \({\mathcal {X}}_{{\textrm{HH}}}\) of (2,0,2)- and (3,0,3)-digraphs steadily decreases to more negative values along the synaptic filtration when more simplices appear. The numbers of strongly connected components in these digraphs is a large fraction of the numbers of vertices, possibly indicating that the strong components are rather small, i.e there are only few reciprocally connected simplices. Condensation then only destroys relatively few edges, leaving a larger negative factor in \({\mathcal {X}}_{{\textrm{HH}}}\). From the known over-representation of reciprocally connected 2- and 3-cliques in the C. elegans network one might expect that many pairs of simplices with exactly the same vertices would be connected in both ways in the (q, i, j)-digraphs; the particular choice of i and j here might not be sensitive to this. The sharp increase in the (4,0,4)-digraph around filtration values 12–13 seems to be due to condensation: at the same time there is a drop in the number of components, so more simplices become connected, and a steep increase in the number of strong components, with the overall effect being that many edges are condensed away. It is interesting that this happens at the particular synaptic weights, and the same phenomena occurs in all the n-path digraphs, albeit to a less degree; this seems to indicate that there is, simplicially, something interesting happening in the C. elegans network at the synaptic weight range 10–15. Further investigating this is left for future work. For (5,0,5)-digraph we see that the slightly positive value of \({\mathcal {X}}_{{\textrm{HH}}}\) until filtration value 12 is dominated by vertices and components with very little connections; this is reasonable as simplices of dimension \(\ge 5\) are sparse within the network. As more simplices appear we see a decline in \({\mathcal {X}}_{{\textrm{HH}}}\) with the increase of connecting edges. Note that the numbers of vertices and strong components seem to agree throughout the filtration, indicating that there are nearly zero reciprocal connections and condensation therefore has no effect.