--- abstract: 'We study two methods for computing network features with topological underpinnings: the Rips and Dowker persistent homology diagrams. Our formulations work for general networks, which may be asymmetric and may have any real number as an edge weight. We study the sensitivity of Dowker persistence diagrams to asymmetry via numerous theoretical examples, including a family of highly asymmetric cycle networks that have interesting connections to the existing literature. In particular, we characterize the Dowker persistence diagrams arising from asymmetric cycle networks. We investigate the stability properties of both the Dowker and Rips persistence diagrams, and use these observations to run a classification task on a dataset comprising simulated hippocampal networks. Our theoretical and experimental results suggest that Dowker persistence diagrams are particularly suitable for studying asymmetric networks. As a stepping stone for our constructions, we prove a functorial generalization of a theorem of Dowker, after whom our constructions are named.' address: - 'Department of Mathematics, The Ohio State University. Phone: (669)504-9950.' - 'Department of Mathematics and Department of Computer Science and Engineering, The Ohio State University. Phone: (669)504-9950, Fax: (669)504-9950.' author: - Samir Chowdhury and Facundo Mémoli bibliography: - 'biblio.bib' title: A functorial Dowker theorem and persistent homology of asymmetric networks --- Introduction ============ Networks are used throughout the sciences for representing the complex relations that exist between the objects of a dataset @newman2003structure [@kleinberg-book]. Network data arises from applications in social science @kumar2010structure [@kleinberg-book], commerce and economy @elliott2014financial [@kleinberg-book; @acemoglu2015systemic], neuroscience @sporns2011networks [@sporns2012discovering; @sporns2004motifs; @rubinov2010complex; @pessoa2014understanding], biology @barabasi2004network [@huson2010phylogenetic], and defence @masys2014networks, to name a few sources. Networks are often directed, in the sense that weights attached to edges do not satisfy any symmetry property, and this asymmetry often precludes the applicability of many standard methods for data analysis. Network analysis problems come in a wide range of flavors. One problem is in *exploratory data analysis*: given a network representing a dataset of societal, economic, or scientific value, the goal is to obtain insights that are meaningful to the interested party and can help uncover interesting phenomena. Another problem is *network classification*: given a "bag" of networks representing multiple instances of different phenomena, one wants to obtain a clustering which groups the networks together according to the different phenomena they represent. Because networks are often too complex to deal with directly, one typically extracts certain invariants of networks, and infers structural properties of the networks from properties of these invariants. While there are numerous such network invariants in the existing literature, there is growing interest in adopting a particular invariant arising from *persistent homology* @frosini1992measuring [@robins1999towards; @edelsbrunner2002topological; @zomorodian2005computing], known as a *persistence diagram*, to the setting of networks. Persistence diagrams are used in the context of finite metric space or point cloud data to pick out *features of significance* while rejecting random noise @edelsbrunner2002topological [@carlsson2009topology]. Since a network on $n$ nodes is regarded, in the most general setting, as an $n\times n$ matrix of real numbers, i.e. as a generalized metric space, it is conceivable that one should be able to describe persistence diagrams for networks as well. The motivation for computing persistence diagrams of networks is at least two-fold: (1) comparing persistence diagrams has been shown to be a viable method for *shape matching* applications @frosini1992measuring [@frosini1999size; @collins2004barcode; @bot-stab; @carlsson2005persistence; @dgh-pers], analogous to the network classification problem described above, and (2) persistence diagrams have been successfully applied to feature detection, e.g. in detecting the structure of protein molecules (see @krishnamoorthy2007topological [@xia2014persistent] and @edelsbrunner2002topological [§6]) and solid materials (see @hiraoka2016hierarchical) and might thus be a useful tool for exploratory analysis of network datasets. We point the reader to @ghrist2008barcodes [@edelsbrunner2008persistent; @carlsson2009topology; @zigzag; @weinberger2011persistent; @burghelea2013topological; @dey2014computing] for surveys of persistent homology and its applications, and some recent extensions. Some extant approaches that obtain persistence diagrams from networks assume that the underlying network data actually satisfies metric properties @lee2011computing [@khalid2014tracing]. A more general approach for obtaining persistence diagrams from networks is followed in @horak2009persistent [@carstens2013persistent; @giusti2015clique; @petri2013topological], albeit with the restriction that the input data sets are required to be symmetric matrices. Our chief goal is to devise notions of persistent homology that are directly applicable to asymmetric networks in the most general sense, and are furthermore capable of absorbing structural information contained in the asymmetry. Contributions and an overview of our approach --------------------------------------------- \(N) at (0,0)<span>${\mathcal{N}}$</span>; (F) at (3,0)<span>${\mathcal}{F}$</span>; (D) at (6,0)<span>${\operatorname{Dgm}}$</span>; \(N) edge\[loop above, out=150, in=90, looseness=8, -&gt;\] node\[left\]<span>${\mathfrak}{s}$</span> (N); (N) edge\[loop above, out=210, in=270, looseness=8, -&gt;\] node\[left\]<span>${\mathfrak}{t}$</span> (N); \(N) edge\[-&gt;, bend left, looseness =1.5\] node\[above\]<span>${\mathfrak}{R}$</span> (F); (N) edge\[-&gt;\] node\[above\]<span>${{\mathfrak}{D}^{\operatorname{si}}}$</span> (F); (N) edge\[-&gt;, bend right, looseness=1.5\] node\[above\]<span>${{\mathfrak}{D}^{\operatorname{so}}}$</span> (F); \(F) edge\[-&gt;\] node\[above\]<span>$H_k$</span> (D); In this paper, we study two types of persistence diagrams: the *Rips* and *Dowker* diagrams. We define both invariants in the setting of asymmetric networks with real-valued weights, without assuming any metric properties at all (not symmetry and not even that the matrix representing the networks weights vanishes on the diagonal). As a key step in defining the Dowker persistence diagram, we first define two dual constructions, each of which can be referred to as a Dowker persistence diagram, and then prove a *functorial Dowker theorem* which implies that these two possible diagrams are equivalent. Following the line of work in @dgh-pers, where stability of Rips persistence diagrams arising from finite metric spaces was first established, we formulate similar stability results for the Rips and Dowker persistence diagrams of a network. Through various examples, in particular a family of *cycle networks*, we espouse the idea that Dowker persistence diagrams are more appropriate than Rips persistence diagrams for studying asymmetric networks. We test our methods by solving a network classification problem on a database of simulated hippocampal networks. The first step in constructing a persistence diagram from a network is to construct a nested sequence of simplicial complexes, i.e. a simplicial filtration, which, in our work, will be the *Rips* or *Dowker* filtrations associated to a network. Rips and Dowker simplicial complexes and their associated filtrations are classically defined for metric spaces @de2004topological [@ghrist-eat], and the generalization to networks that we use is a natural extension of the metric versions. After producing the simplicial filtrations, the standard framework of *persistent homology* takes over, and we obtain the Rips or Dowker persistence diagrams. Practitioners of persistent homology might recall that there are *two* Dowker complexes @ghrist-eat [p. 73], which we describe as the *source* and *sink* Dowker complexes. A subtle point to note here is that each of these Dowker complexes can be used to construct a persistence diagram. A folklore result in the literature about persistent homology of metric spaces, known as *Dowker duality*, is that the two persistence diagrams arising this way are equal @chazal2014persistence [Remark 4.8]. In this paper we prove a stronger result—a functorial Dowker theorem—from which the duality follows easily. Furthermore, the context of this result is strictly more general than that of metric spaces (see below for a more thorough description of the functorial version of Dowker's theorem). Providing a construction of Rips and Dowker persistence diagrams is not enough: in order for these invariants to be useful in practice, one must verify that the diagrams are *stable*. In this context, stability means the following: the dissimilarity between two Rips (resp. Dowker) persistence diagrams obtained from two networks should be bounded above by a function of the dissimilarity between the two networks. To our knowledge, stability is not addressed in the existing literature on producing persistence diagrams from networks. In our work, we provide stability results for both the Rips and Dowker persistence diagrams (Propositions \[prop:rips-stab\] and \[prop:dowker-stab\]). One key ingredient in our proof of this result is a notion of *network distance* that follows previous work in @clust-net [@nets-allerton; @nets-icassp]. This network distance is analogous to the Gromov-Hausdorff distance between metric spaces, which has previously been used to prove stability results for hierarchical clustering @carlsson2008persistent [@clust-um] and Rips persistence diagrams obtained from finite metric spaces @dgh-pers [Theorem 3.1]. The Gromov-Hausdorff distance was later used in conjunction with the Algebraic Stability Theorem of @chazal2009proximity to provide alternative proofs of stability results for Rips and Dowker persistence diagrams arising from metric spaces @chazal2014persistence. Our proofs also involve this Algebraic Stability Theorem, but the novelty of our approach lies in a reformulation of the network distance (Proposition \[prop:dn-ko\]) that yields direct maps between two networks, thus passing naturally into the machinery of the Algebraic Stability Theorem (without having to define auxiliary constructions such as multivalued maps, as in @chazal2014persistence). A crucial issue that we point out in this paper is that even though we can construct both Rips and Dowker persistence diagrams out of asymmetric networks, Rips persistence diagrams appear to be *blind* to asymmetry, whereas Dowker persistence diagrams do exhibit sensitivity to asymmetry. In the case of Rips complexes, this purported insensitivity to asymmetry can be immediately seen from its definition. In the case of Dowker complexes, we argue about its sensitivity to asymmetry in two different ways. Firstly, we do so by explicitly computing Dowker persistence diagrams of multiple examples of asymmetric networks. In particular, we consider a family of highly asymmetric networks, the *cycle networks*, and by bulding upon results from @adamaszek2015vietoris [@adamaszek2016nerve] we prove a complete characterization result for the Dowker persistence diagrams—across all dimensions—of any network belonging to this family. These networks constitute directed analogues of circles and may be *motifs* of interest in different applications related to network data analysis. More specifically, appearance of nontrivial 1-dimensional persistence in the Dowker persistence diagram of asymmetric network data may suggest the presence of directed cycles in the data. Some of our experimental results suggest that the Rips persistence diagrams of this family of networks are pathological, in the sense that they do not represent the signatures one would expect from the underlying dataset, which is a directed circle. Dowker persistence diagrams, on the other hand, are well-behaved in this respect in that they succeed at capturing relevant features. Secondly, we study the degree to which Dowker persistence diagrams are insensitive to changes (such as edge flips, or transposition) in the network structure. An overview of this thread of work is provided in Figure \[fig:overview\].\ #### Dowker's theorem and a functorial generalization Let $X,Y$ be two totally ordered sets, and let $R\subseteq X\times Y$ be a nonempty relation. Then one can define two simplicial complexes $E_R$ and $F_R$ as follows. A finite subset ${\sigma}\subseteq X$ belongs to $E_R$ whenever there exists $y \in Y$ such that $(x,y) \in R$ for each $x\in {\sigma}$. Similarly a finite subset ${\tau}\subseteq Y$ belongs to $F_R$ whenever there exists $x\in X$ such that $(x,y) \in R$ for each $y\in {\tau}$. These constructions can be traced back to @dowker1952homology, who proved the following result that we refer to as *Dowker's theorem*: \[Dowker's theorem; Theorem 1a, @dowker1952homology\]\[thm:dowker\] Let $X,Y$ be two totally ordered sets, let $R\subseteq X\times Y$ be a nonempty relation, and let $E_R, F_R$ be as above. Then for each $k \in {\mathbb{Z}}_+$, $$H_k(E_R) \cong H_k(F_R).$$ There is also a strong form of Dowker's theorem that Björner proves via the classical *nerve theorem* @bjorner-book [Theorems 10.6, 10.9]: \[The strong form of Dowker's theorem; Theorem 10.9, @bjorner-book\] \[thm:dowker-strong\] Under the assumptions of Theorem \[thm:dowker\], we in fact have $|E_R| \simeq |F_R|$. The Functorial Dowker Theorem is the following generalization of the strong form of Dowker's theorem: instead of a single nonempty relation $R \subseteq X\times Y$, consider any pair of nested, nonempty relations $R\subseteq R' \subseteq X\times Y$. Then there exist homotopy equivalences between the geometric realizations of the corresponding complexes that commute with the canonical inclusions, up to homotopy. We formalize this statement below. \[The Functorial Dowker Theorem (FDT)\] \[thm:dowker-functorial\] Let $X,Y$ be two totally ordered sets, let $R\subseteq R' \subseteq X\times Y$ be two nonempty relations, and let $E_R, F_R, E_{R'}, F_{R'}$ be their associated simplicial complexes. Then there exist homotopy equivalences $\Gamma_{|E_R|}:|F_R| {\rightarrow}|E_R|$ and $\Gamma_{|E_{R'}|}: |F_{R'}| {\rightarrow}|E_{R'}|$ such that the following diagram commutes up to homotopy: \[\] (1) at (0,0)<span>$|F_R|$</span>; (2) at (3,0)<span>$|F_{R'}|$</span>; \(3) at (0,-2)<span>$|E_{R}|$</span>; (4) at (3,-2)<span>$|E_{R'}|$</span>; \(1) edge\[-&gt;\] node\[above\]<span>$|\iota_E|$</span> (2); (3) edge\[-&gt;\] node\[above\]<span>$|\iota_F|$</span>(4); (1) edge\[-&gt;\] node\[left\]<span>$\Gamma_{|E_R|}$</span> node\[right\] <span>$\simeq$</span>(3); (2) edge\[-&gt;\] node\[right\]<span>$\Gamma_{|E_{R'}|}$</span> node\[left\] <span>$\simeq$</span> (4); In other words, we have $|\iota_F|\circ \Gamma_{|E_R|} \simeq \Gamma_{|E_{R'}|} \circ |\iota_E|$, where $\iota_E,\iota_F$ are the canonical inclusions. From Theorem \[thm:dowker-functorial\] we automatically obtain Theorem \[thm:dowker-strong\] (the strong form of Dowker's theorem) as an immediate corollary. The strong form does not appear in Dowker's original paper @dowker1952homology, but Björner has given a proof using the nerve theorem @bjorner-book [Theorems 10.6, 10.9]. Moreover, Björner writes in a remark following @bjorner-book [Theorem 10.9] that the nerve theorem and the strong form of Dowker's theorem are equivalent, in the sense that one implies the other. We were not able to find an elementary proof of the strong form of Dowker's theorem in the existing literature. However, such an elementary proof is provided by our proof of Theorem \[thm:dowker-functorial\] (given in Section \[sec:dowker-dual\]), which we obtained by extending ideas in Dowker's original proof of Theorem \[thm:dowker\].[^1] Whereas the Functorial Dowker Theorem and our elementary proof are of independent interest, it has been suggested in @chazal2014persistence [Remark 4.8] that such a functorial version of Dowker's theorem could also be proved using a functorial nerve theorem @chazal2008towards [Lemma 3.4]. Despite being an interesting possibility, we were not able to find a detailed proof of this claim in the literature. In addition, Björner's remark regarding the equivalence between the nerve theorem and the strong form of Dowker's theorem suggests the following question: \[q:f-nerve-f-dowker\] Are the Functorial Nerve Theorem (FNT) of @chazal2008towards and the Functorial Dowker Theorem (FDT, Theorem \[thm:dowker-functorial\]) equivalent? This question is of fundamental importance because the Nerve Theorem is a crucial tool in the applied topology literature and its functorial generalizations are equally important in persistent homology. In general, the answer is *no*, and moreover, one (of the FNT and FDT) is not stronger than the other. The FNT of @chazal2008towards is stated for paracompact spaces, which are more general than the simplicial complexes of the FDT. However, the FNT of @chazal2008towards is stated for spaces with *finitely-indexed* covers, so the associated nerve complexes are necessarily finite. All the complexes involved in the statement of the FDT are allowed to be infinite, so the FDT is more general than the FNT in this sense. To clarify these connections, we formulate a simplicial Functorial Nerve Theorem (Theorem \[thm:nerve-functorial-II\]) and prove it via a finite formulation of the FDT (Theorem \[thm:dowker-functorial-finite\]). In turn, we show that the simplicial FNT implies the finite FDT, thus proving the equivalence of these formulations (Theorem \[thm:dowker-nerve-eq\]). Dowker complexes are also known to researchers who use Q-analysis to study social networks @johnson2013hypernetworks [@atkin1975mathematical; @atkin1972cohomology]. We perceive that viewing Dowker complexes through the modern lens of persistence will enrich the classical framework of Q-analysis by incorporating additional information about the *meaningfulness* of features, thus potentially opening new avenues in the social sciences. An announcement of part of our work has appeared in @dowker-asilo. Implementations --------------- Following work in @curto2008cell [@dabaghian2012topological], we implement our methods in the setting of classifying simulated hippocampal networks. We simulate the activity pattern of hippocampal cells in an animal as it moves around arenas with a number of obstacles, and compile this data into a network which can be interpreted as the transition matrix for the time-reversal of a Markov process. The motivating idea is to ascertain whether, by just observing hippocampal activity and not using any higher reasoning ability, one might be able to determine the number of obstacles in the arena that the animal has just finished traversing. The results of computing Dowker persistence diagrams suggest that the hippocampal activity is indeed sufficient to accurately count the number of obstacles in each arena. Our datasets and software are available on <https://research.math.osu.edu/networks/Datasets.html> as part of the `PersNet` software package. Organization of the paper ------------------------- Notation used globally is defined directly below. §\[sec:background\] contains the necessary background on persistent homology. §\[sec:nets\] contains our formulations for networks, as well as some key ingredients of our stability results. §\[sec:rips\] contains details about the Rips persistence diagram. The first part of §\[sec:dowker\] contains details about the Dowker persistence diagram. §\[sec:dowker-dual\] contains the Functorial Dowker Theorem. The connection between the simplicial Functorial Nerve Theorem and the finite Functorial Dowker Theorem is detailed in §\[sec:dowker-nerve-equiv\]. In §\[sec:symmetry\] we show that Dowker complexes are sensitive to asymmetry. §\[sec:cycle\] contains a family of asymmetric networks, the *cycle networks*, and a full characterization of their Dowker persistence diagrams. In §\[sec:exp\] we provide details on an implementation of our methods. Finally, proofs of statements not contained in the main body of the paper are relegated to Appendix \[app:proofs\], whereas details about the characterization results for Dowker persistence diagrams of cycle networks are given in Appendix \[sec:cycle-addendum\]. Notation -------- We will write $\mathbb{K}$ to denote a field, which we will fix and use throughout the paper. We will write ${\mathbb{Z}}_+$ and ${\mathbb{R}}_+$ to denote the nonnegative integers and reals, respectively. The extended real numbers ${\mathbb{R}}\cup {\left\{\infty, -\infty\right\}}$ will be denoted $\overline{{\mathbb{R}}}$. The cardinality of a set $X$ will be denoted ${\operatorname{card}}(X)$. The collection of nonempty subsets of a set $X$ will be denoted ${\operatorname{pow}}(X)$. The natural numbers ${\left\{1,2,3,\ldots\right\}}$ will be denoted by ${\mathbb{N}}$. The dimension of a vector space $V$ will be denoted $\dim(V)$. The rank of a linear transformation $f$ will be denoted ${\operatorname{rank}}(f)$. An isomorphism between vector spaces $V$ and $W$ will be denoted $V\cong W$. A homotopy relation for two maps $f,g:X{\rightarrow}Y$ between topological spaces will be denoted $f\simeq g$. Occasionally we will need to take about multisets, i.e. sets where elements can have multiplicity greater than 1. We will use square bracket notation $[\ldots]$ to denote multisets. Identity maps will be denoted by the notation ${\operatorname{id}}_\bullet$. Given a simplicial complex ${\Sigma}$, we will often write $V({\Sigma})$ to denote the vertex set of ${\Sigma}$. We will write ${\operatorname{Bd}}({\sigma})$ to denote the boundary of a simplex ${\sigma}$. Background on persistent homology {#sec:background} ================================= We assume that the reader is familiar with terms and concepts related to simplicial homology, and refer to @munkres-book for details. Here we describe our choices of notation. Whenever we have a simplicial complex over a set $X$ and a $k$-simplex ${\left\{x_0,x_1,\ldots, x_k\right\}}$, $k\in {\mathbb{Z}}_+$, we will assume that the simplex is *oriented* by the ordering $x_0< x_1 < \ldots < x_k$. We will write $[x_0,x_1,\ldots,x_k]$ to denote the equivalence class of the even permutations of this chosen ordering, and $-[x_0,x_1,\ldots,x_k]$ to denote the equivalence class of the odd permutations of this ordering. Given a simplicial complex ${\Sigma}$, we will denote its geometric realization by $|{\Sigma}|$. The *weak topology* on $|{\Sigma}|$ is defined by requiring that a subset $A \subseteq |{\Sigma}|$ is closed if and only if $A \cap |{\sigma}|$ is closed in $|{\sigma}|$ for each ${\sigma}\in {\Sigma}$. A simplicial map $f: {\Sigma}{\rightarrow}\Xi$ between two simplicial complexes induces a map $|f|: |{\Sigma}| {\rightarrow}|\Xi|$ between the geometric realizations, defined as $|f|(\sum_{v\in {\Sigma}}a_v v):= \sum_{v\in {\Sigma}}a_v f(v)$. These induced maps satisfy the usual composition identity: given simpicial maps $f:{\Sigma}{\rightarrow}\Xi$ and $g:\Xi {\rightarrow}\Upsilon$, we have $|g\circ f| = |g| \circ |f|$. To see this, observe the following: $$\label{eq:htpy-func} |g\circ f|(\sum_{v\in {\Sigma}}a_v v) = \sum_{v\in {\Sigma}} a_vg(f(v)) = |g|(\sum_{v\in {\Sigma}}a_v f(v)) = |g|\circ|f|(\sum_{v\in {\Sigma}}a_v v).$$ A *filtration* of a simplicial complex ${\Sigma}$ (also called a *filtered simplicial complex*) is defined to be a nested sequence $\{{\Sigma}^{{\delta}}\subseteq {\Sigma}^{{\delta}'}\}_{{\delta}\leq {\delta}' \in {\mathbb{R}}}$ of simplicial complexes satisfying the condition that there exist ${\delta}_I,\, {\delta}_F \in {\mathbb{R}}$ such that ${\Sigma}^{{\delta}} = {\varnothing}$ for all ${\delta}\leq {\delta}_I$, and ${\Sigma}^{{\delta}} = {\Sigma}\text{ for all }{\delta}\geq {\delta}_F$. Fix a field ${\mathbb}{K}$. Given a finite simplicial complex ${\Sigma}$ and a dimension $k \in {\mathbb{Z}}_+$, we will denote a *$k$-chain* in ${\Sigma}$ as $\sum_ia_i{\sigma}_i$, where each $a_i \in \mathbb{K}$ and ${\sigma}_i \in {\Sigma}$. We write $C_k({\Sigma})$ or just $C_k$ to denote the $\mathbb{K}$-vector space of all $k$-chains. We will write ${\partial}_k$ to denote the associated *boundary map* ${\partial}_k : C_k {\rightarrow}C_{k-1}$: $${\partial}_k[x_0,\ldots,x_k]:=\sum_i(-1)^i[x_0,\ldots,\hat{x}_i,\ldots, x_k], \text{ where $\hat{x}_i$ denotes omission of $x_i$ from the sequence.}$$ We will write ${\mathcal{C}}=(C_k,{\partial}_k)_{k\in {\mathbb{Z}}_+}$ to denote a *chain complex*, i.e. a sequence of vector spaces with boundary maps such that ${\partial}_{k-1}\circ {\partial}_k =0$. Given a chain complex ${\mathcal{C}}$ and any $k\in {\mathbb{Z}}_+$, the *$k$-th homology of the chain complex ${\mathcal{C}}$* is denoted $H_k({\mathcal{C}}) :=\ker({\partial}_k)/{\operatorname{im}}({\partial}_{k+1})$. The *$k$-th Betti number* of ${\mathcal{C}}$ is denoted ${\beta}_k({\mathcal{C}})$. Given a simplicial map $f$ between simplicial complexes, we write $f_*$ to denote the induced chain map between the corresponding chain complexes @munkres-book [§1.12], and $(f_k)_{\#}$ to denote the linear map on $k$th homology vector spaces induced for each $k \in {\mathbb{Z}}_+$. The operations of passing from simplicial complexes and simplicial maps to chain complexes and induced chain maps, and then to homology vector spaces with induced linear maps, will be referred to as *passing to homology*. Recall the following useful fact, often referred to as *functoriality of homology* @munkres-book [Theorem 12.2]: given a composition $g\circ f$ of simplicial maps, we have $$(g_k\circ f_k)_\# = (g_k)_\#\circ (f_k)_\# \qquad\text{ for each } k\in {\mathbb{Z}}_+. \label{eq:functoriality}$$ A *persistence vector space* is defined to be a family of vector spaces $\{U^{\delta}{\xrightarrow}{\mu_{{\delta},{\delta}'}} U^{{\delta}'}\}_{{\delta}\leq {\delta}'\in {\mathbb{R}}}$ such that: (1) $\mu_{{\delta},{\delta}}$ is the identity for each ${\delta}\in {\mathbb{R}}$, and (2) $\mu_{{\delta},{\delta}''} = \mu_{{\delta}',{\delta}''}\circ \mu_{{\delta},{\delta}'}$ for each ${\delta}\leq {\delta}' \leq {\delta}'' \in {\mathbb{R}}$. The persistence vector spaces that we consider in this work also satisfy the following conditions: (1) $\dim(U^{\delta}) <\infty$ at each ${\delta}\in {\mathbb{R}}$, (2) there exist ${\delta}_I,\, {\delta}_F \in {\mathbb{R}}$ such that all maps $\mu_{{\delta},{\delta}'}$ are isomorphisms for ${\delta},{\delta}' \geq {\delta}_F$ and for ${\delta},{\delta}' \leq {\delta}_I$, and (3) there are only finitely many values of ${\delta}\in {\mathbb{R}}$ such that $U^{{\delta}-{\varepsilon}} \not\cong U^{{\delta}}$ for each ${\varepsilon}>0$. Here ${\delta}$ is referred to as a *resolution* parameter, and such a persistence vector space is described as being *${\mathbb{R}}$-indexed*. The collection of all such persistence vector spaces is denoted ${{\operatorname{\mathbf{PVec}}}}({\mathbb{R}})$. Observe that by fixing $k \in {\mathbb{Z}}_+$ and passing to the $k$th homology vector space at each step ${\Sigma}^{{\delta}}$ of a filtered simplicial complex $({\Sigma}^{{\delta}})_{{\delta}\in {\mathbb{R}}}$, the functoriality of homology gives us the $k$th persistence vector space associated to $({\Sigma}^{{\delta}})_{{\delta}\in {\mathbb{R}}}$, denoted $${\mathcal{H}}_k({\Sigma}) := \{H_k({\mathcal{C}}^{{\delta}}){\xrightarrow}{(\iota_{{\delta},{\delta}'})_\#} H_k({\mathcal{C}}^{{\delta}'})\}_{{\delta}\leq {\delta}' \in {\mathbb{R}}}.$$ The elements of ${{\operatorname{\mathbf{PVec}}}}({\mathbb{R}})$ contain only a finite number of vector spaces, up to isomorphism. By the classification results in @carlsson2005persistence [§5.2], it is possible to associate a full invariant, called a *persistence barcode* or *persistence diagram*, to each element of ${{\operatorname{\mathbf{PVec}}}}({\mathbb{R}})$. This barcode is a multiset of *persistence intervals*, and is represented as a set of lines over a single axis. The barcode of a persistence vector space ${\mathcal{V}}$ is denoted ${{\operatorname{\mathbf{Pers}}}}({\mathcal{V}})$. The intervals in ${{\operatorname{\mathbf{Pers}}}}({\mathcal{V}})$ can be represented as the *persistence diagram of ${\mathcal{V}}$*, which is as a multiset of points lying on or above the diagonal in $\overline{{\mathbb{R}}}^2$, counted with multiplicity. More specifically, $${\operatorname{Dgm}}({\mathcal{V}}):=\big[({\delta}_i,{\delta}_{j+1}) \in \overline{{\mathbb{R}}}^2 : [{\delta}_i,{\delta}_{j+1}) \in {{\operatorname{\mathbf{Pers}}}}({\mathcal{V}}) \big],$$ where the multiplicity of $({\delta}_i,{\delta}_{j+1})\in \overline{{\mathbb{R}}}^2$ is given by the multiplicity of $[{\delta}_i,{\delta}_{j+1}) \in {{\operatorname{\mathbf{Pers}}}}({\mathcal{V}})$. Persistence diagrams can be compared using the *bottleneck distance*, which we denote by ${d_{\operatorname{B}}}$. Details about this distance, as well as the other material related to persistent homology, can be found in @chazal2012structure. Numerous other formulations of the material presented above can be found in @edelsbrunner2002topological [@zomorodian2005computing; @zigzag; @edelsbrunner2010computational; @edelsbrunner2014persistent; @bauer-isom; @ph-self]. \[rem:trivial-diag\] Whenever we describe a persistence diagram as being *trivial*, we mean that either it is empty, or it does not have any off-diagonal points. Interleaving distance and stability of persistence vector spaces. {#sec:background-int} ----------------------------------------------------------------- In what follows, we will consider ${\mathbb{R}}$-indexed persistence vector spaces ${{\operatorname{\mathbf{PVec}}}}({\mathbb{R}})$. Given ${\varepsilon}\geq 0$, two ${\mathbb{R}}$-indexed persistence vector spaces ${\mathcal{V}}=\{V^{\delta}{\xrightarrow}{\nu_{{\delta},{\delta}'}} V^{{\delta}'}\}_{{\delta}\leq {\delta}'}$ and ${\mathcal{U}}=\{U^{\delta}{\xrightarrow}{\mu_{{\delta},{\delta}'}} U^{{\delta}'}\}_{{\delta}\leq {\delta}'}$ are said to be *${\varepsilon}$-interleaved* @chazal2009proximity [@bauer-isom] if there exist two families of linear maps $$\begin{aligned} \{{\varphi}_{{\delta},{\delta}+{\varepsilon}}&:V^{\delta}{\rightarrow}V^{{\delta}+ {\varepsilon}}\}_{{\delta}\in {\mathbb{R}}},\\ \{\psi_{{\delta},{\delta}+{\varepsilon}}&:U^{\delta}{\rightarrow}U^{{\delta}+ {\varepsilon}}\}_{{\delta}\in {\mathbb{R}}}\end{aligned}$$ such that the following diagrams commute for all ${\delta}' \geq {\delta}\in {\mathbb{R}}$: $$\begin{tikzcd}[column sep=large] V^{\delta}\arrow{r}{\nu_{{\delta},{\delta}'}} \arrow[swap]{dr}{{\varphi}_{\delta}} & V^{{\delta}'}\arrow{dr}{{\varphi}_{{\delta}'}} & {} & {} & V^{{\delta}+{\varepsilon}} \arrow{r}{\nu_{{\delta}+\eta,{\delta}'+\eta}} & V^{{\delta}'+{\varepsilon}} \\ {} & U^{{\delta}+{\varepsilon}} \arrow{r}{\mu_{{\delta}+\eta,{\delta}'+\eta}} & U^{{\delta}'+{\varepsilon}} & U^{{\delta}} \arrow{ur}{\psi_{\delta}} \arrow{r}{\mu_{{\delta},{\delta}'}} & U^{{\delta}'} \arrow[swap]{ur}{\psi_{{\delta}'}} & {} \end{tikzcd}$$ $$\begin{tikzcd}[column sep=large] V^{\delta}\arrow{rr}{\nu_{{\delta},{\delta}+2{\varepsilon}}} \arrow[swap]{dr}{{\varphi}_{\delta}} & {} & V^{{\delta}+2{\varepsilon}} & {}& V^{{\delta}+{\varepsilon}} \arrow{dr}{\psi_{{\delta}+{\varepsilon}}}\\ {} & U^{{\delta}+{\varepsilon}} \arrow[swap]{ur}{{\varphi}_{{\delta}+{\varepsilon}}} & {}& U^{{\delta}} \arrow{ur}{\psi_{{\delta}}} \arrow{rr}{\mu_{{\delta},{\delta}+2{\varepsilon}}} & {} & U^{{\delta}+2\eta} \end{tikzcd}$$ The purpose of introducing ${\varepsilon}$-interleavings is to define a pseudometric on the collection of persistence vector spaces. The *interleaving distance* between two ${\mathbb{R}}$-indexed persistence vector spaces ${\mathcal{V}},{\mathcal{U}}$ is given by: $${d_{\operatorname{I}}}({\mathcal{U}},{\mathcal{V}}) := \inf \{{\varepsilon}\geq 0 : \text{${\mathcal{U}}$ and ${\mathcal{V}}$ are ${\varepsilon}$-interleaved}\}.$$ One can verify that this definition induces a pseudometric on the collection of persistence vector spaces @chazal2009proximity [@bauer-isom]. The interleaving distance can then be related to the bottleneck distance as follows: \[Algebraic Stability Theorem, @chazal2009proximity\] Let ${\mathcal{U}}, {\mathcal{V}}$ be two ${\mathbb{R}}$-indexed persistence vector spaces. Then, $${d_{\operatorname{B}}}({\operatorname{Dgm}}({\mathcal{U}}),{\operatorname{Dgm}}({\mathcal{V}}))\leq {d_{\operatorname{I}}}({\mathcal{U}},{\mathcal{V}}).$$ Stability results are at the core of persistent homology, beginning with the classical bottleneck stability result in @bot-stab. One of our key contributions is to use the Algebraic Stability Theorem stated above, along with Lemma §\[sec:nets\] stated below, to prove stability results for methods of computing persistent homology of a network. Before stating the following lemma, recall that two simplicial maps $f,g: {\Sigma}{\rightarrow}\Xi$ are *contiguous* if for any simplex ${\sigma}\in {\Sigma}$, $f({\sigma}) \cup g({\sigma})$ is a simplex of $\Xi$. Contiguous maps satisfy the following useful properties: \[Properties of contiguous maps\] \[prop:contigo-props\] Let $f,g: {\Sigma}{\rightarrow}\Xi$ be two contiguous simplicial maps. Then, 1. $|f|,|g|:|{\Sigma}| {\rightarrow}|\Xi|$ are homotopic @spanier-book [§3.5], and 2. The chain maps induced by $f$ and $g$ are chain homotopic, and as a result, the induced maps $f_\#$ and $g_\#$ for homology are equal @munkres-book [Theorem 12.5]. \[Stability Lemma\] \[lem:stab\] Let ${\mathfrak}{F}, {\mathfrak}{G}$ be two filtered simplicial complexes written as $$\{{\mathfrak}{F}^{\delta}{\xrightarrow}{s_{{\delta},{\delta}'}} {\mathfrak}{F}^{{\delta}'}\}_{{\delta}'\geq {\delta}\in {\mathbb{R}}} \text{ and } \{{\mathfrak}{G}^{\delta}{\xrightarrow}{t_{{\delta},{\delta}'}} {\mathfrak}{G}^{{\delta}'}\}_{{\delta}'\geq {\delta}\in {\mathbb{R}}},$$ where $s_{{\delta},{\delta}'}$ and $t_{{\delta},{\delta}'}$ denote the natural inclusion maps. Suppose $\eta\geq 0$ is such that there exist families of simplicial maps ${\left\{{\varphi}_{\delta}:{\mathfrak}{F}^{\delta}{\rightarrow}{\mathfrak}{G}^{{\delta}+\eta}\right\}}_{{\delta}\in {\mathbb{R}}}$ and ${\left\{\psi_{\delta}:{\mathfrak}{G}^{\delta}{\rightarrow}{\mathfrak}{F}^{{\delta}+\eta}\right\}}_{{\delta}\in {\mathbb{R}}}$ such that the following are satisfied for any ${\delta}' \geq {\delta}$: 1. $t_{{\delta}+\eta,{\delta}'+\eta}\circ {\varphi}_{\delta}$ and ${\varphi}_{{\delta}'}\circ s_{{\delta},{\delta}'}$ are contiguous 2. $s_{{\delta}+\eta,{\delta}'+\eta}\circ \psi_{\delta}$ and $\psi_{{\delta}'}\circ t_{{\delta},{\delta}'}$ are contiguous 3. $\psi_{{\delta}+\eta}\circ {\varphi}_{\delta}$ and $s_{{\delta},{\delta}+2\eta}$ are contiguous 4. ${\varphi}_{{\delta}+\eta}\circ \psi_{\delta}$ and $t_{{\delta},{\delta}+2\eta}$ are contiguous. All the diagrams are as below: $$\begin{tikzcd}[column sep=large] {\mathfrak}{F}^{\delta}\arrow{r}{s_{{\delta},{\delta}'}} \arrow[swap]{dr}{{\varphi}_{\delta}} & {\mathfrak}{F}^{{\delta}'}\arrow{dr}{{\varphi}_{{\delta}'}} & {} & {} & {\mathfrak}{F}^{{\delta}+\eta} \arrow{r}{s_{{\delta}+\eta,{\delta}'+\eta}} & {\mathfrak}{F}^{{\delta}'+\eta} \\ {} & {\mathfrak}{G}^{{\delta}+\eta} \arrow{r}{t_{{\delta}+\eta,{\delta}'+\eta}} & {\mathfrak}{G}^{{\delta}'+\eta} & {\mathfrak}{G}^{{\delta}} \arrow{ur}{\psi_{\delta}} \arrow{r}{t_{{\delta},{\delta}'}} & {\mathfrak}{G}^{{\delta}'} \arrow[swap]{ur}{\psi_{{\delta}'}} & {} \end{tikzcd}$$ $$\begin{tikzcd}[column sep=large] {\mathfrak}{F}^{\delta}\arrow{rr}{s_{{\delta},{\delta}+2\eta}} \arrow[swap]{dr}{{\varphi}_{\delta}} & {} & {\mathfrak}{F}^{{\delta}+2\eta} & {} & {}& {\mathfrak}{F}^{{\delta}+\eta} \arrow{dr}{{\varphi}_{{\delta}+\eta}}\\ {} & {\mathfrak}{G}^{{\delta}+\eta} \arrow[swap]{ur}{\psi_{{\delta}+\eta}} & {} & {}& {\mathfrak}{G}^{{\delta}} \arrow{ur}{\psi_{\delta}} \arrow{rr}{t_{{\delta},{\delta}+2\eta}} & {} & {\mathfrak}{G}^{{\delta}+2\eta} \end{tikzcd}$$ For each $k\in {\mathbb{Z}}_+$, let ${\mathcal{H}}_k({\mathfrak}{F}), {\mathcal{H}}_k({\mathfrak}{G})$ denote the $k$-dimensional persistence vector spaces associated to ${\mathfrak}{F}$ and ${\mathfrak}{G}$. Then for each $k\in {\mathbb{Z}}_+$, $${d_{\operatorname{B}}}({\operatorname{Dgm}}_k({\mathcal{H}}_k({\mathfrak}{F})),{\operatorname{Dgm}}_k({\mathcal{H}}_k({\mathfrak}{G}))) \leq {d_{\operatorname{I}}}({\mathcal{H}}_k({\mathfrak}{F}),{\mathcal{H}}_k({\mathfrak}{G})) \leq \eta.$$ Background on networks and our network distance {#sec:nets} =============================================== A *network* is a pair $(X,{\omega}_X)$ where $X$ is a finite set and ${\omega}_X: X\times X {\rightarrow}{\mathbb{R}}$ is a *weight function*. Note that ${\omega}_X$ need not satisfy the triangle inequality, any symmetry condition, or even the requirement that ${\omega}_X(x,x) = 0$ for all $x\in X$. The weights are even allowed to be negative. The collection of all such networks is denoted ${\mathcal{N}}$. When comparing networks, one needs a way to correlate points in one network with points in the other. To see how this can be done, let $(X,{\omega}_X), (Y,{\omega}_Y) \in {\mathcal{N}}$. Let $R$ be any nonempty relation between $X$ and $Y$, i.e. a nonempty subset of $X \times Y$. The *distortion* of the relation $R$ is given by: $${\operatorname{dis}}(R):=\max_{(x,y),(x',y')\in R}|{\omega}_X(x,x')-{\omega}_Y(y,y')|.$$ A *correspondence between $X$ and $Y$* is a relation $R$ between $X$ and $Y$ such that $\pi_X(R)=X$ and $\pi_Y(R)=Y$, where $\pi_X:X\times Y {\rightarrow}X$ and $\pi_Y:X\times Y {\rightarrow}Y$ denote the natural projections. The collection of all correspondences between $X$ and $Y$ will be denoted ${\mathscr{R}}(X,Y)$. Following previous work in @clust-net [@nets-allerton; @nets-icassp] the *network distance* ${d_{\mathcal{N}}}:{\mathcal{N}}\times {\mathcal{N}}{\rightarrow}{\mathbb{R}}_+$ is then defined as: $${d_{\mathcal{N}}}(X,Y):=\frac{1}{2}\min_{R\in{\mathscr{R}}}{\operatorname{dis}}(R).$$ It can be verified that ${d_{\mathcal{N}}}$ as defined above is a pseudometric, and that the networks at 0-distance can be completely characterized @nets-allerton. Next we wish to prove the reformulation in Proposition \[prop:dn-ko\]. First we define the distortion of a map between two networks. Given any $(X,{\omega}_X),(Y,{\omega}_Y)\in {\mathcal{N}}$ and a map ${\varphi}:(X,{\omega}_X) {\rightarrow}(Y,{\omega}_Y)$, the *distortion* of ${\varphi}$ is defined as: $${\operatorname{dis}}({\varphi}):= \max_{x,x'\in X}|{\omega}_X(x,x')-{\omega}_Y({\varphi}(x),{\varphi}(x'))|.$$ Next, given maps ${\varphi}:(X,{\omega}_X){\rightarrow}(Y,{\omega}_Y)$ and $\psi:(Y,{\omega}_Y){\rightarrow}(X,{\omega}_X)$, we define two *co-distortion* terms: $$\begin{aligned} C_{X,Y}({\varphi},\psi) &:= \max_{(x,y)\in X\times Y}|{\omega}_X(x,\psi(y)) - {\omega}_Y({\varphi}(x),y)|,\\ C_{Y,X}(\psi,{\varphi}) &:= \max_{(y,x)\in Y\times X}|{\omega}_Y(y,{\varphi}(x)) - {\omega}_X(\psi(y),x)|.\end{aligned}$$ \[prop:dn-ko\] Let $(X,{\omega}_X), (Y,{\omega}_Y)\in {\mathcal{N}}$. Then, $${d_{\mathcal{N}}}(X,Y) = \tfrac{1}{2}\min\{\max({\operatorname{dis}}({\varphi}),{\operatorname{dis}}(\psi),C_{X,Y}({\varphi},\psi), C_{Y,X}(\psi,{\varphi})) : {\varphi}:X {\rightarrow}Y, \psi:Y {\rightarrow}X \text{ any maps}\}.$$ Proposition \[prop:dn-ko\] is analogous to a result of Kalton and Ostrovskii @kalton1997distances [Theorem 2.1] where—instead of ${d_{\mathcal{N}}}$—one has the Gromov-Hausdorff distance between metric spaces. We remark that when restricted to the special case of networks that are also metric spaces, the network distance ${d_{\mathcal{N}}}$ agrees with the Gromov-Hausdorff distance. Details on the Gromov-Hausdorff distance can be found in @burago. An important remark is that in the Kalton-Ostrovskii formulation, there is only one co-distortion term. When Proposition \[prop:dn-ko\] is applied to metric spaces, the two co-distortion terms become equal by symmetry, and thus the Kalton-Ostrovskii formulation is recovered. But *a priori*, the lack of symmetry in the network setting requires us to consider both terms. In the following sections, we propose methods for computing persistent homology of networks, and prove that they are stable via Lemma \[lem:stab\]. Note that similar results, valid in the setting of metric spaces, have appeared in @dgh-pers [@chazal2014persistence]. Whereas the proofs in @chazal2014persistence invoke an auxiliary construction of multivalued maps arising from correspondences, our proofs simply use the maps ${\varphi}, \psi$ arising directly from the reformulation of ${d_{\mathcal{N}}}$ (Proposition \[prop:dn-ko\]), thus streamlining the treatment. When studying the effect of asymmetry on persistent homology, it will be useful to consider the network transformations that we define next. \[Symmetrization and Transposition\] \[defn:sym-trans\] Define the *max-symmetrization* map ${\mathfrak}{s}:{\mathcal{N}}{\rightarrow}{\mathcal{N}}$ by $(X,{\omega}_X)\mapsto (X,\widehat{{\omega}_X})$, where for any network $(X,{\omega}_X)$, we define $\widehat{{\omega}_X}:X\times X {\rightarrow}{\mathbb{R}}$ as follows: $$\widehat{{\omega}_X}(x,x'):= \max({\omega}_X(x,x'),{\omega}_X(x',x)), \text{ for } x,x'\in X.$$ Also define the *transposition* map ${\mathfrak}{t}:{\mathcal{N}}{\rightarrow}{\mathcal{N}}$ by $(X,{\omega}_X) \mapsto (X,{\omega}_X^\top)$, where for any $(X,{\omega}_X) \in {\mathcal{N}}$, we define ${\omega}_X^\top(x,x'):= {\omega}_X(x',x)$ for $x,x'\in X$. For convenience, we denote $X^\top:={\mathfrak}{t}(X)$ for any network $X$. We are now ready to formulate our two methods for computing persistent homology of networks. The Rips filtration is the "workhorse" of persistent homology of metric spaces so it is natural to consider its generalization to general asymmetric networks. The Rips filtration of a network {#sec:rips} ================================ Recall that for a metric space $(X,d_X)$, the *Rips complex* is defined for each ${\delta}\geq 0$ as follows: $${\mathfrak}{R}^{\delta}_X := {\left\{{\sigma}\in {\operatorname{pow}}(X): {\operatorname{diam}}({\sigma}) \leq {\delta}\right\}}, \text{ where } {\operatorname{diam}}({\sigma}) := \max_{x,x'\in {\sigma}}d_X(x,x').$$ Following this definition, we can define the Rips complex for a network $(X,{\omega}_X)$ as follows: $${\mathfrak}{R}^{\delta}_X:=\{{\sigma}\in {\operatorname{pow}}(X) : \max_{x,x'\in {\sigma}}{\omega}_X(x,x') \leq {\delta}\}.$$ To any network $(X,{\omega}_X)$, we may associate the *Rips filtration* $\{{\mathfrak}{R}^{\delta}_X{\hookrightarrow}{\mathfrak}{R}^{{\delta}'}_X\}_{{\delta}\leq {\delta}'}$. We denote the $k$-dimensional persistence vector space associated to this filtration by ${\mathcal{H}}_k^{{\mathfrak}{R}}(X)$, and the corresponding persistence diagram by ${\operatorname{Dgm}}_k^{{\mathfrak}{R}}(X)$. The Rips filtration is stable to small perturbations of the input data:9 \[prop:rips-stab\] Let $(X,{\omega}_X), (Y,{\omega}_Y) \in {\mathcal{N}}$. Then ${d_{\operatorname{B}}}({\operatorname{Dgm}}_k^{{\mathfrak}{R}}(X),{\operatorname{Dgm}}_k^{{\mathfrak}{R}}(Y)) \leq 2{d_{\mathcal{N}}}(X,Y).$ We omit the proof because it is similar to that of Proposition \[prop:dowker-stab\], which we will prove in detail. \[rem:rips-benefits\] The preceding proposition serves a dual purpose: (1) it shows that the Rips persistence diagram is robust to noise in input data, and (2) it shows that instead of computing the network distance between two networks, one can compute the bottleneck distance between their Rips persistence diagrams as a suitable proxy. The advantage to computing bottleneck distance is that it can be done in polynomial time (see @efrat2001geometry), whereas computing ${d_{\mathcal{N}}}$ is NP-hard in general. This follows from the fact that the problem of computing ${d_{\mathcal{N}}}$ includes the problem of computing the Gromov-Hausdorff distance between finite metric spaces, which is an NP-hard problem @schmiedl. We remark that the idea of computing Rips persistence diagrams to compare finite metric spaces first appeared in @dgh-pers, and moreover, that Proposition \[prop:rips-stab\] is an extension of Theorem 3.1 in @dgh-pers. The Rips filtration in the setting of symmetric networks has been used in @horak2009persistent [@carstens2013persistent; @giusti2015clique; @petri2013topological], albeit without addressing stability results. To our knowledge, Proposition \[prop:rips-stab\] is the first quantitative result justifying the constructions in these prior works. \[Rips is insensitive to asymmetry\] \[rem:rips-symm\] A critical weakness of the Rips complex construction is that it is not sensitive to asymmetry. To see this, recall the symmetrization map defined in Definition \[defn:sym-trans\], and let $(X,{\omega}_X) \in {\mathcal{N}}$. Now for any ${\sigma}\in {\operatorname{pow}}(X)$, we have $\max_{x,x' \in {\sigma}}{\omega}_X(x,x') = \max_{x,x'\in {\sigma}}\widehat{{\omega}_X}(x,x').$ It follows that for each ${\delta}\geq 0$, the Rips complexes of $(X,{\omega}_X)$ and $(X,\widehat{{\omega}_X})={\mathfrak}{s}(X,{\omega}_X)$ are equal, i.e. ${\mathfrak}{R} = {\mathfrak}{R} \circ {\mathfrak}{s}$. Thus the Rips persistence diagrams of the original and max-symmetrized networks are equal. The Dowker filtration of a network {#sec:dowker} ================================== Given $(X,\omega_X)\in \mathcal{N}$, and for any ${\delta}\in {\mathbb{R}}$, consider the following relation on $X$: $$R_{{\delta},X}:={\left\{(x,x') : {\omega}_X(x,x') \leq {\delta}\right\}}. \label{eq:relation}$$ Then $R_{{\delta},X} \subseteq X \times X$, and $R_{{\delta}_F,X} = X \times X$ for some sufficiently large ${\delta}_F$. Furthermore, for any ${\delta}' \geq {\delta}$, we have $R_{{\delta},X} \subseteq R_{{\delta}',X}$. Using $R_{{\delta},X}$, we build a simplicial complex ${{\mathfrak}{D}^{\operatorname{si}}}_{\delta}$ as follows: $$\label{eq:d-sink} {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}:={\left\{{\sigma}=[x_0,\ldots, x_n] : \text{ there exists } x'\in X \text{ such that } (x_i,x')\in R_{{\delta},X} \text{ for each } x_i\right\}}.$$ If ${\sigma}\in {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$, it is clear that any face of ${\sigma}$ also belongs to ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$. We call ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$ the *Dowker ${\delta}$-sink simplicial complex* associated to $X$, and refer to $x'$ as a *${\delta}$-sink* for ${\sigma}$ (where ${\sigma}$ and $x'$ should be clear from context). Since $R_{{\delta},X}$ is an increasing sequence of sets, it follows that ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$ is an increasing sequence of simplicial complexes. In particular, for ${\delta}'\geq {\delta}$, there is a natural inclusion map ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X} {\hookrightarrow}{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}',X}$. We write ${{\mathfrak}{D}^{\operatorname{si}}}_X$ to denote the filtration $\{{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X} {\hookrightarrow}{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}',X}\}_{ {\delta}\leq {\delta}'}$ associated to $X$. We call this the *Dowker sink filtration on $X$*. We will denote the $k$-dimensional persistence diagram arising from this filtration by ${\operatorname{Dgm}}_k^{{\operatorname{si}}}(X)$. \[every node/.style=<span>font=</span>\] \[draw,purple\] (2) at (2,0)<span>$a$</span>; (3) at (3,2)<span>$b$</span>; (4) at (4,0)<span>$c$</span>; \[draw,xshift=6cm,yshift=1cm\] (5) at (5,1)<span> $ {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}= \begin{cases} {\varnothing}&: {\delta}<-1 \\ \{[a]\} &:-1\leq {\delta}<0\\ \{[a],[b],[c]\} &: 0\leq {\delta}< 1\\ \{[a],[b],[c],[ab],[bc],[ac],[abc]\} &: {\delta}\geq 1 \end{cases} $ </span>; \[draw,xshift=6cm,yshift=-1.2cm\] (50) at (5,1)<span> $ {{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}= \begin{cases} {\varnothing}&: {\delta}<-1 \\ \{[a]\} &:-1\leq {\delta}<0\\ \{[a],[b],[c]\} &: 0\leq {\delta}< 1\\ \{[a],[b],[c],[ab],[ac]\} &: 1\leq {\delta}< 2\\ \{[a],[b],[c],[ab],[bc],[ac],[abc]\} &: {\delta}\geq 2 \end{cases} $ </span>; \[xshift=1cm,yshift=1cm\] (0) at (4,0); (1) at (6,0); \[draw=NavyBlue\] (2) edge \[loop left\] node\[left\]<span>$-1$</span>(2); (3) edge \[loop right\] node\[right\]<span>$0$</span>(3); (4) edge \[loop right\] node\[right\]<span>$0$</span>(4); (2) edge \[bend left\] node\[above\]<span>$1$</span> (3); (3) edge \[\] node\[below\]<span>$1$</span> (2); (2) edge \[\] node\[above\]<span>$2$</span> (4); (3) edge \[\] node\[below\]<span>$2$</span> (4); (4) edge \[bend left\] node\[below\]<span>$1$</span> (2); (4) edge \[bend right\] node\[below\]<span>$2$</span> (3); Note that we can define a dual construction as follows: $$\label{eq:d-src} {{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}:={\left\{{\sigma}=[x_0,\ldots, x_n] : \text{ there exists } x'\in X \text{ such that } (x',x_i)\in R_{{\delta},X} \text{ for each } x_i\right\}}.$$ We call ${{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}$ the *Dowker ${\delta}$-source simplicial complex* associated to $X$. The filtration $\{{{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X} {\hookrightarrow}{{\mathfrak}{D}^{\operatorname{so}}}_{{\delta}',X}\}_{ {\delta}\leq {\delta}'}$ associated to $X$ is called the *Dowker source filtration*, denoted ${{\mathfrak}{D}^{\operatorname{so}}}_X$. We denote the $k$-dimensional persistence diagram arising from this filtration by ${\operatorname{Dgm}}_k^{{\operatorname{so}}}(X)$. Notice that any construction using ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$ can also be repeated using ${{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}$, so we focus on the case of the sink complexes and restate results in terms of source complexes where necessary. In particular, we will prove in §\[sec:dowker-dual\] that $${\operatorname{Dgm}}_k^{{\operatorname{si}}}(X) = {\operatorname{Dgm}}_k^{{\operatorname{so}}}(X) \text{ for any } k\in {\mathbb{Z}}_+,$$ so it makes sense to talk about "the" Dowker diagram associated to $X$. The sink and source filtrations are not equal in general; this is illustrated in Figure \[fig:dowker-three-node\]. As in the case of the Rips filtration, both the Dowker sink and source filtrations are stable. \[prop:dowker-stab\] Let $(X,{\omega}_X), (Y,{\omega}_Y) \in {\mathcal{N}}$. Then ${d_{\operatorname{B}}}({\operatorname{Dgm}}_k^{\bullet}{(X)},{\operatorname{Dgm}}_k^{\bullet}(Y)) \leq 2{d_{\mathcal{N}}}(X,Y).$ Here ${\operatorname{Dgm}}^{\bullet}$ refers to either of ${\operatorname{Dgm}}^{{\operatorname{si}}}$ and ${\operatorname{Dgm}}^{{\operatorname{so}}}$. \[Proof of Proposition \[prop:dowker-stab\]\] Both cases are similar, so we just prove the result for ${\operatorname{Dgm}}^{{\operatorname{si}}}$. Let $\eta=2{d_{\mathcal{N}}}(X,Y)$. Then by Proposition \[prop:dn-ko\], there exist maps ${\varphi}:X {\rightarrow}Y, \psi: Y {\rightarrow}X$ such that $$\max({\operatorname{dis}}({\varphi}),{\operatorname{dis}}(\psi), C_{X,Y}({\varphi},\psi),C_{Y,X}(\psi,{\varphi}))\leq \eta.$$ First we check that ${\varphi},\psi$ induce simplicial maps ${\varphi}_{\delta}:{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X} {\rightarrow}{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+\eta,Y}$ and $\psi_{\delta}:{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},Y} {\rightarrow}{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+\eta,Y}$ for each ${\delta}\in {\mathbb{R}}$. Let ${\delta}' \geq {\delta}\in {\mathbb{R}}$. Let ${\sigma}=[x_0,\ldots, x_n] \in {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$. Then there exists $x' \in X$ such that ${\omega}_X(x_i,x') \leq {\delta}$ for each $0\leq i \leq n$. Fix such an $x'$. Since ${\operatorname{dis}}({\varphi}) \leq \eta$, we have the following for each $i$: $$\vert {\omega}_X(x_i,x') - {\omega}_Y({\varphi}(x_i),{\varphi}(x'))\vert \leq \eta.$$ So ${\omega}_Y({\varphi}(x_i),{\varphi}(x')) \leq {\omega}_X(x_i,x') + \eta \leq {\delta}+ \eta$ for each $0\leq i\leq n$. Thus ${\varphi}_{{\delta}}({\sigma}):={\left\{{\varphi}(x_0),\ldots, {\varphi}(x_n)\right\}}$ is a simplex in ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+ \eta,Y}$. Thus the map on simplices ${\varphi}_{\delta}$ induced by ${\varphi}$ is simplicial for each ${\delta}\in {\mathbb{R}}$. Similarly we can check that the map $\psi_{\delta}$ on simplices induced by $\psi$ is simplicial. Now to prove the result, it will suffice to check the contiguity conditions in the statement of Lemma \[lem:stab\]. Consider the following diagram: $$\begin{tikzcd}[column sep=large] {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X} \arrow{r}{s_{{\delta},{\delta}'}} \arrow[swap]{dr}{{\varphi}_{\delta}} & {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}',X}\arrow{dr}{{\varphi}_{{\delta}'}} & \\ &{{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+\eta,Y} \arrow{r}{t_{{\delta}+\eta,{\delta}'+\eta}} & {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}'+\eta,Y} \end{tikzcd}$$ Here $s_{{\delta},{\delta}'}$ and $t_{{\delta}+\eta,{\delta}'+\eta}$ are the inclusion maps. We claim that $t_{{\delta}+\eta,{\delta}'+\eta} \circ {\varphi}_{\delta}$ and ${\varphi}_{{\delta}'} \circ s_{{\delta},{\delta}'}$ are contiguous simplicial maps. To see this, let ${\sigma}\in {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$. Since $s_{{\delta},{\delta}'}$ is just the inclusion, it follows that $t_{{\delta}+\eta,{\delta}'+\eta}({\varphi}_{\delta}({\sigma})) \cup {\varphi}_{{\delta}'}(s_{{\delta},{\delta}'}({\sigma}))={\varphi}_{\delta}({\sigma}),$ which is a simplex in ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+\eta,Y}$ because ${\varphi}_{\delta}$ is simplicial, and hence a simplex in ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}'+\eta,Y}$ because the inclusion $t_{{\delta}+\eta,{\delta}'+\eta}$ is simplicial. Thus $t_{{\delta}+\eta,{\delta}'+\eta} \circ {\varphi}_{\delta}$ and ${\varphi}_{{\delta}'} \circ s_{{\delta},{\delta}'}$ are contiguous, and their induced linear maps for homology are equal. By a similar argument, one can show that $s_{{\delta}+\eta,{\delta}'+\eta}\circ \psi_{\delta}$ and $\psi_{{\delta}'}\circ t_{{\delta},{\delta}'}$ are contiguous simplicial maps as well. Next we check that the maps $\psi_{{\delta}+\eta}\circ {\varphi}_{\delta}$ and $s_{{\delta},{\delta}+2\eta}$ in the figure below are contiguous. $$\begin{tikzcd} {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X} \arrow{rr}{s_{{\delta},{\delta}+2\eta}} \arrow[swap]{dr}{{\varphi}_{\delta}} & {} & {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+2\eta,X}\\ {} & {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+\eta,Y} \arrow[swap]{ur}{\psi_{{\delta}+\eta}} & {} \end{tikzcd}$$ Let $x_i\in {\sigma}$. Note that for our fixed ${\sigma}= [x_0,\ldots, x_n]\in {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$ and $x'$, we have: $$\begin{aligned} |{\omega}_X(x_i,x')-{\omega}_X(\psi({\varphi}(x_i)),\psi({\varphi}(x')))|&\leq |{\omega}_X(x_i,x') - {\omega}_Y({\varphi}(x_i),{\varphi}(x'))|\\ &+ |{\omega}_Y({\varphi}(x_i),{\varphi}(x')) - {\omega}_X(\psi({\varphi}(x_i)),\psi({\varphi}(x')))| \\ &\leq 2\eta.\\ \text{Thus we obtain }\hfill {\omega}_X(\psi({\varphi}(x_i)),\psi({\varphi}(x')))&\leq {\omega}_X(x_i,x')+ 2\eta \leq {\delta}+2\eta.\end{aligned}$$ Since this holds for any $x_i \in {\sigma}$, it follows that $\psi_{{\delta}+\eta}({\varphi}_{\delta}({\sigma})) \in {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+2\eta,X}$. We further claim that $${\tau}:={\sigma}\cup \psi_{{\delta}+\eta}({\varphi}_{\delta}({\sigma})) = {\left\{x_0,x_1,\ldots, x_n, \psi({\varphi}(x_0)),\ldots, \psi({\varphi}(x_n))\right\}}$$ is a simplex in ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+2\eta,X}$. Let $0\leq i\leq n$. It suffices to show that ${\omega}_X(x_i,\psi({\varphi}(x')) \leq {\delta}+ 2\eta$. Notice that from the reformulation of ${d_{\mathcal{N}}}$ (Proposition \[prop:dn-ko\]), we have $$C_{X,Y}({\varphi},\psi) = \max_{(x,y)\in X\times Y}|{\omega}_X(x,\psi(y)) - {\omega}_Y({\varphi}(x),y)| \leq \eta .$$ Let $y = {\varphi}(x')$. Then $|{\omega}_X(x_i,\psi(y)) - {\omega}_Y({\varphi}(x_i),y)| \leq \eta$. In particular, $${\omega}_X(x_i,\psi({\varphi}(x'))) \leq {\omega}_Y({\varphi}(x_i),{\varphi}(x')) + \eta \leq {\omega}_X(x_i,x') + 2\eta \leq {\delta}+2\eta.$$ Since $0\leq i\leq n$ were arbitrary, it follows that ${\tau}\in {{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}+2\eta,X}$. Thus $\psi_{{\delta}+\eta}\circ {\varphi}_{\delta}$ and $s_{{\delta},{\delta}+2\eta}$ are contiguous. Similarly, one can use the ${\operatorname{dis}}(\psi)$ and $C_{Y,X}(\psi,{\varphi})$ terms to show that $t_{{\delta},{\delta}+2\eta}$ and ${\varphi}_{{\delta}+\eta}\circ \psi_{\delta}$ are contiguous. The result now follows by an application of Lemma \[lem:stab\]. \[rem:dowker-benefits\] The preceding proposition shows that the Dowker persistence diagram is robust to noise in input data, and that the bottleneck distance between Dowker persistence diagrams arising from two networks can be used as a proxy for computing the actual network distance. Note the analogy with Remark \[rem:rips-benefits\]. Both the Dowker and Rips filtrations are valid methods for computing persistent homology of networks, by virtue of their stability results (Propositions \[prop:rips-stab\] and \[prop:dowker-stab\]). However, we present the Dowker filtration as an appropriate method for capturing directionality information in directed networks. In §\[sec:symmetry\] we discuss this particular feature of the Dowker filtration in full detail. \[Symmetric networks\] In the setting of symmetric networks, the Dowker sink and source simplicial filtrations coincide, and so we automatically obtain ${\operatorname{Dgm}}_k^{{\operatorname{so}}}(X)={\operatorname{Dgm}}_k^{{\operatorname{si}}}(X)$ for any $k\in {\mathbb{Z}}_+$ and any $(X,{\omega}_X)\in {\mathcal{N}}$. \[The metric space setting and relation to witness complexes\] When restricted to the setting of metric spaces, the Dowker complex resembles a construction called the witness complex @de2004topological. In particular, a version of the Dowker complex for metric spaces, constructed in terms of *landmarks* and *witnesses*, was discussed in @chazal2014persistence, along with stability results. When restricted to the special networks that are pseudo-metric spaces, our definitions and results agree with those presented in @chazal2014persistence. The Functorial Dowker Theorem and equivalence of diagrams {#sec:dowker-dual} --------------------------------------------------------- Let $(X,{\omega}_X)\in {\mathcal{N}}$, and let ${\delta}\in {\mathbb{R}}$ be such that $R_{{\delta},X}$ is nonempty. By applying Dowker's theorem (Theorem \[thm:dowker\]) to the setting $Y=X$, we have $H_k({{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}) \cong H_k({{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X})$, for any $k \in {\mathbb{Z}}_+$. We still have this equality in the case where $R_{{\delta},X}$ is empty, because then ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$ and ${{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}$ are both empty. Thus we obtain: \[cor:dowker\] Let $(X,{\omega}_X)\in{\mathcal{N}}$, ${\delta}\in {\mathbb{R}}$, and $k\in {\mathbb{Z}}_+$. Then, $$H_k({{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}) \cong H_k({{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}).$$ In the persistent setting, Theorem \[thm:dowker\] and Corollary \[cor:dowker\] suggest the following question: > *Given a network $(X,{\omega}_X)$ and a fixed dimension $k\in {\mathbb{Z}}_+$, are the persistence diagrams of the Dowker sink and source filtrations of $(X,{\omega}_X)$ necessarily equal?* In what follows, we provide a positive answer to the question above. Our strategy is to use the Functorial Dowker Theorem (Theorem \[thm:dowker-functorial\]), for which we will provide a complete proof below. The Functorial Dowker Theorem implies equality between sink and source persistence diagrams. \[Dowker duality\] \[cor:dowker-dual\] Let $(X,{\omega}_X)\in {\mathcal{N}}$, and let $k\in {\mathbb{Z}}_+$. Then, $${\operatorname{Dgm}}_k^{{\operatorname{si}}}(X)={\operatorname{Dgm}}_k^{{\operatorname{so}}}(X).$$ Thus we may call either of the diagrams above the *$k$-dimensional Dowker diagram of $X$*, denoted ${\operatorname{Dgm}}_k^{{\mathfrak}{D}}(X)$. Before proving the corollary, we state an ${\mathbb{R}}$-indexed variant of the Persistence Equivalence Theorem @edelsbrunner2010computational. This particular version follows from the *isometry theorem* @bauer-isom, and we refer the reader to @chazal2012structure [Chapter 5] for an expanded presentation of this material. \[Persistence Equivalence Theorem\] \[thm:pet\] Consider two persistence vector spaces ${\mathcal{U}}=\{U^{{\delta}} {\xrightarrow}{\mu_{{\delta},{\delta}'}} U^{{\delta}'}\}_{{\delta}\leq{\delta}' \in {\mathbb{R}}}$ and ${\mathcal{V}}=\{V^{{\delta}} {\xrightarrow}{\nu_{{\delta},{\delta}'}} V^{{\delta}'}\}_{{\delta}\leq {\delta}'\in {\mathbb{R}}}$ with connecting maps $f_{{\delta}}:U^{{\delta}}{\rightarrow}V^{{\delta}'}$. \[\] (00) at (-3,0)<span>$\cdots$</span>; (1) at (0,0)<span>$V^{{\delta}}$</span>; (2) at (3,0)<span>$V^{{\delta}'}$</span>; (3) at (6,0)<span>$V^{{\delta}''}$</span>; (01) at (9,0)<span>$\cdots$</span>; \(02) at (-3,2)<span>$\cdots$</span>; (4) at (0,2)<span>$U^{{\delta}}$</span>; (5) at (3,2)<span>$U^{{\delta}'}$</span>; (6) at (6,2)<span>$U^{{\delta}''}$</span>; (03) at (9,2)<span>$\cdots$</span>; \(00) edge\[-&gt;\] (1); (3) edge\[-&gt;\] (01); (02) edge\[-&gt;\] (4); (6) edge\[-&gt;\] (03); \(1) edge\[-&gt;\] (2); (2) edge\[-&gt;\] (3); (4) edge\[-&gt;\] (5); (5) edge\[-&gt;\] (6); (1) edge\[&lt;-\] node\[right\]<span>$f_{{\delta}}$</span> (4); (2) edge\[&lt;-\] node\[right\]<span>$f_{{\delta}'}$</span> (5); (3) edge\[&lt;-\] node\[right\]<span>$f_{{\delta}''}$</span> (6); If the $f_{{\delta}}$ are all isomorphisms and each square in the diagram above commutes, then: $${\operatorname{Dgm}}({\mathcal{U}}) = {\operatorname{Dgm}}({\mathcal{V}}).$$ \[Proof of Corollary \[cor:dowker-dual\]\] Let ${\delta}\leq {\delta}' \in {\mathbb{R}}$, and consider the relations $R_{{\delta},X} \subseteq R_{{\delta}',X} \subseteq X\times X$. Suppose first that $R_{{\delta},X}$ and $R_{{\delta}',X}$ are both nonempty. By applying Theorem \[thm:dowker-functorial\], we obtain homotopy equivalences between the source and sink complexes that commute with the canonical inclusions up to homotopy. Passing to the $k$-th homology level, we obtain persistence vector spaces that satisfy the commutativity properties of Theorem \[thm:pet\]. The result follows from Theorem \[thm:pet\]. In the case where $R_{{\delta},X}$ and $R_{{\delta}',X}$ are both empty, there is nothing to show because all the associated complexes are empty. Suppose $R_{{\delta},X}$ is empty, and $R_{{\delta}',X}$ is nonempty. Then ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta},X}$ and ${{\mathfrak}{D}^{\operatorname{so}}}_{{\delta},X}$ are empty, so their inclusions into ${{\mathfrak}{D}^{\operatorname{si}}}_{{\delta}',X}$ and ${{\mathfrak}{D}^{\operatorname{so}}}_{{\delta}',X}$ induce zero maps upon passing to homology. Thus the commutativity of Theorem \[thm:pet\] is satisfied, and the result follows by Theorem \[thm:pet\]. #### The proof of the Functorial Dowker Theorem It remains to prove Theorem \[thm:dowker-functorial\]. Because the proof involves numerous maps, we will adopt the notational convention of adding a subscript to a function to denote its codomain—e.g. we will write $f_B$ to denote a function with codomain $B$. First we recall the construction of a combinatorial barycentric subdivision (see @dowker1952homology [§2], @lefschetz1942algebraic [§4.7], @barmak2011algebraic [Appendix A]). \[Barycentric subdivisions\]\[def:subdivision\] For any simplicial complex ${\Sigma}$, one may construct a new simplicial complex ${\Sigma}^{(1)}$, called the *first barycentric subdivision*, as follows: $${\Sigma}^{(1)}:={\left\{[{\sigma}_1,{\sigma}_2,\ldots, {\sigma}_p] : {\sigma}_1 \subseteq {\sigma}_2 \subseteq \ldots \subseteq {\sigma}_p, \text{ each } {\sigma}_i \in {\Sigma}\right\}}.$$ Note that the vertices of ${\Sigma}^{(1)}$ are the simplices of ${\Sigma}$, and the simplices of ${\Sigma}^{(1)}$ are nested sequences of simplices of ${\Sigma}$. Furthermore, note that given any two simplicial complexes ${\Sigma}, \Xi$ and a simplicial map $f:{\Sigma}{\rightarrow}\Xi$, there is a natural simplicial map $f{^{(1)}}:{\Sigma}{^{(1)}}{\rightarrow}\Xi{^{(1)}}$ defined as: $$f{^{(1)}}([{\sigma}_1,\ldots,{\sigma}_p]):=[f({\sigma}_1),\ldots,f({\sigma}_p)], \qquad {\sigma}_1\subseteq {\sigma}_2\subseteq \ldots, {\sigma}_p, \text{ each } {\sigma}_i\in {\Sigma}.$$ To see that this is simplicial, note that $f({\sigma}_i) \subseteq f({\sigma}_j)$ whenever ${\sigma}_i\subseteq {\sigma}_j$. As a special case, observe that any inclusion map $\iota:{\Sigma}{\hookrightarrow}\Xi$ induces an inclusion map $\iota{^{(1)}}:{\Sigma}{^{(1)}}{\hookrightarrow}\Xi{^{(1)}}$. Given a simplex ${\sigma}=[x_0,\ldots, x_k]$ in a simplicial complex ${\Sigma}$, one defines the *barycenter* to be the point ${\mathcal}{B}({\sigma}):= \sum_{i=0}^k \tfrac{1}{k+1}x_i \in |{\Sigma}|$. Then the spaces $|{\Sigma}{^{(1)}}|$ and $|{\Sigma}|$ can be identified via a homeomorphism ${\mathcal}{E}_{|{\Sigma}|}:|{\Sigma}{^{(1)}}| {\rightarrow}|{\Sigma}|$ defined on vertices by ${\mathcal}{E}_{|{\Sigma}|}({\sigma}):= {\mathcal}{B}({\sigma})$ and extended linearly. Details on the preceding list of definitions can be found in @munkres-book [§2.14-15, 2.19], @spanier-book [§3.3-4], and also @barmak2011algebraic [Appendix A]. The next proposition follows from the discussions in these references, and is a simple restatement of @barmak2011algebraic [Proposition A.1.5]. We provide a proof in the appendix for completeness. \[Simplicial approximation to ${\mathcal}{E}_\bullet$\]\[prop:subdiv-identity\] Let ${\Sigma}$ be a simplicial complex, and let $\Phi: \Sigma{^{(1)}}{\rightarrow}\Sigma$ be a simplicial map such that $\Phi({\sigma}) \in {\sigma}$ for each ${\sigma}\in \Sigma$. Then $|\Phi| \simeq {\mathcal}{E}_{|\Sigma|}$. We now introduce some auxiliary constructions dating back to @dowker1952homology that use the setup stated in Theorem \[thm:dowker-functorial\]. For any nonempty relation $R\subseteq X\times Y$, one may define @dowker1952homology [§2] an associated map $\Phi_{E_R} : E_R{^{(1)}}{\rightarrow}E_R$ as follows: first define $\Phi_{E_R}$ on vertices of $E_R{^{(1)}}$ by $\Phi_{E_R}({\sigma})=s_{{\sigma}}$, where $s_{{\sigma}}$ is the least vertex of ${\sigma}$ with respect to the total order. Next, for any simplex $[{\sigma}_1,\ldots,{\sigma}_k]$ of $E_R{^{(1)}}$, where ${\sigma}_1\subseteq \ldots \subseteq {\sigma}_k$, we have $\Phi_{E_R}({\sigma}_i)=s_{{\sigma}_i} \in {\sigma}_k$ for all $1\leq i\leq k$. Thus $[\Phi_{E_R}({\sigma}_1),\ldots,\Phi_{E_R}({\sigma}_k)]=[s_{{\sigma}_1},s_{{\sigma}_2},\ldots,s_{{\sigma}_k}]$ is a face of ${\sigma}_k$, hence a simplex of ${\Sigma}$. This defines $\Phi_{E_R}$ as a simplicial map $E_R{^{(1)}}{\rightarrow}E_R$. This argument also shows that $\Phi_{E_R}$ is order-reversing: if ${\sigma}\subseteq {\sigma}'$, then $\Phi_{E_R}({\sigma}) \geq \Phi_{E_{R}}({\sigma}')$. \[rem:subdiv-id\] Applying Proposition \[prop:subdiv-identity\] to the setup above, one sees that $|\Phi_{E_R}| \simeq {\mathcal}{E}_{|E_R|}$. After passing to a second barycentric subdivision $E_R^{(2)}$ (obtained by taking a barycentric subdivision of $E_R{^{(1)}}$) and obtaining a map $\Phi_{E_R{^{(1)}}}:E_R^{(2)} {\rightarrow}E_R{^{(1)}}$, one also has $|\Phi_{E_R{^{(1)}}}| \simeq {\mathcal}{E}_{|E_R{^{(1)}}|}$. One can also define @dowker1952homology [§3] a simplicial map $\Psi_{F_R}: E_R{^{(1)}}{\rightarrow}F_R$ as follows. Given a vertex ${\sigma}=[x_0,\ldots, x_k] \in E_R{^{(1)}}$, one defines $\Psi_{F_R}({\sigma})=y_{\sigma}$, for some $y_{\sigma}\in Y$ such that $(x_i,y_{\sigma}) \in R$ for each $i$. To see why this vertex map is simplicial, let ${\sigma}{^{(1)}}= [{\sigma}_0,\ldots, {\sigma}_k]$ be a simplex in $E_R{^{(1)}}$. Let $x \in {\sigma}_0$. Then, because ${\sigma}_0 \subseteq {\sigma}_1 \subseteq \ldots \subseteq {\sigma}_k$, we automatically have that $(x,\Psi_{F_R}({\sigma}_i)) \in R$, for each $i=0,\ldots, k$. Thus $\Psi_{F_R}({\sigma}{^{(1)}})$ is a simplex in $F_R$. This definition involves a choice of $y_{\sigma}$ when writing $\Psi_{F_R}({\sigma}) = y_{\sigma}$, but all the maps resulting from such choices are contiguous @dowker1952homology [§3]. The preceding map induces a simplicial map $\Psi_{F_R{^{(1)}}}:E_R^{(2)} {\rightarrow}F_R{^{(1)}}$ as follows. Given a vertex ${\tau}{^{(1)}}= [{\tau}_0,\ldots, {\tau}_k] \in E_R^{(2)}$, i.e. a simplex in $E_R{^{(1)}}$, we define $\Psi_{F_R{^{(1)}}}({\tau}{^{(1)}}) := [\Psi_{F_R}({\tau}_0),\ldots, \Psi_{F_R}({\tau}_k)]$. Since $\Psi_{F_R}$ is simplicial, this is a simplex in $F_R$, i.e. a vertex in $F_R{^{(1)}}$. Thus we have a vertex map $\Psi_{F_R{^{(1)}}}:E_R^{(2)} {\rightarrow}F_R{^{(1)}}$. To check that this map is simplicial, let ${\tau}^{(2)} = [{\tau}{^{(1)}}_0,\ldots, {\tau}{^{(1)}}_p]$ be a simplex in $E_R^{(2)}$. Then ${\tau}{^{(1)}}_0 \subseteq {\tau}{^{(1)}}_1 \subseteq \ldots \subseteq {\tau}{^{(1)}}_p$, and because $\Psi_{F_R}$ is simplicial, we automatically have $$\Psi_{F_R}({\tau}{^{(1)}}_0) \subseteq \Psi_{F_R}({\tau}{^{(1)}}_1) \subseteq \ldots \subseteq \Psi_{F_R}({\tau}{^{(1)}}_p).$$ Thus $\Psi_{F_R{^{(1)}}}({\tau}^{(2)})$ is a simplex in $F_R{^{(1)}}$. \[Proof of Theorem \[thm:dowker-functorial\]\] We write $F_R^{(2)}$ to denote the barycentric subdivision of $F_R{^{(1)}}$, and obtain simplicial maps $\Phi_{F_R{^{(1)}}}:F_R^{(2)} {\rightarrow}F_R{^{(1)}}$, $\Phi_{F_R}:F_R^{(1)} {\rightarrow}F_R$, $\Psi_{E_R{^{(1)}}}:F_R^{(2)} {\rightarrow}E_R{^{(1)}}$, and $\Psi_{F_R}:E_R^{(1)} {\rightarrow}F_R$ as above. Consider the following diagram: \(1) at (0,0)<span>$F_R^{(2)}$</span>; (2) at (3,-1)<span>$F_R^{(1)}$</span>; (3) at (6,-2)<span>$F_R$</span>; (4) at (8,0)<span>$F_{R'}^{(2)}$</span>; (5) at (11,-1)<span>$F_{R'}^{(1)}$</span>; (6) at (14,-2)<span>$F_{R'}$</span>; (7) at (-1,-3)<span>$E_R^{(2)}$</span>; (8) at (2,-4)<span>$E_R{^{(1)}}$</span>; (9) at (5,-5)<span>$E_R$</span>; (10) at (7,-3)<span>$E_{R'}^{(2)}$</span>; (11) at (10,-4)<span>$E_{R'}{^{(1)}}$</span>; (12) at (13,-5)<span>$E_{R'}$</span>; \(1) edge\[-&gt;,violet!80,thick\] node\[right\] (2); (2) edge\[-&gt;,violet!80,thick\] node\[above\] (3); (1) edge\[-&gt;\] node\[left\] (4); (4) edge\[-&gt;\] node\[above right\]<span>$\Phi_{F_{R'}{^{(1)}}}$</span> (5); (5) edge\[-&gt;\] node\[above right\]<span>$\Phi_{F_{R'}}$</span> (6); (3) edge\[-&gt;\] node\[above\] (6); \(7) edge\[-&gt;,teal!80,thick\] node\[below\] (8); (8) edge\[-&gt;,teal!80,thick\] node\[below\] (9); (7) edge\[-&gt;,dashed\] node\[left\] (10); (10) edge\[-&gt;,dashed\] node\[above right\] (11); (11) edge\[-&gt;,dashed\] node\[above\] (12); (9) edge\[-&gt;\] node\[above\] (12); \(1) edge\[-&gt;,orange,thick\] node\[left,pos=0.2\] (8); (8) edge\[-&gt;,orange,thick\] node\[below right,pos=0.2\] (3); (4) edge\[-&gt;,dashed\] node\[left\] (11); (11) edge\[-&gt;,dashed\] node\[below right\] (6); \[on background layer\] (7) edge\[-&gt;,NavyBlue!80,thick\] node\[above left,pos=0.2\] (2); (2) edge\[-&gt;,NavyBlue!80,thick\] node\[left,pos=0.2\] (9); (10) edge\[-&gt;,dashed\] node\[left\] (5); (5) edge\[-&gt;,dashed\] node\[below right\] (12); \[\] \(1) at (0,0)<span>$E_R^{(2)}$</span>; (2) at (2,-1)<span>$E_R^{(1)}$</span>; (3) at (4,-2)<span>$E_R$</span>; (4) at (6,0)<span>$E_{R'}^{(2)}$</span>; (5) at (8,-1)<span>$E_{R'}^{(1)}$</span>; (6) at (10,-2)<span>$E_{R'}$</span>; (7) at (3,1)<span>$F_R{^{(1)}}$</span>; (8) at (9,1)<span>$F_{R'}{^{(1)}}$</span>; (1) edge\[-&gt;\] node\[below left\] (2); (2) edge\[-&gt;\] node\[below left\] (3); (1) edge\[-&gt;,dashed\] node\[left\] (4); (4) edge\[-&gt;,dashed\] node\[left\] (5); (5) edge\[-&gt;,dashed\] node\[left\] (6); (3) edge\[-&gt;\] node\[above\]<span>$\iota_E$</span> (6); (1) edge\[-&gt;\] node\[above\] (7); (7) edge\[-&gt;\] node\[right\] (3); (4) edge\[-&gt;,dashed\] node\[left\] (8); (8) edge\[-&gt;\] node\[right\] (6); (7) edge\[-&gt;\] node\[above\]<span>$\iota_F$</span> (8); \[yshift = -1.5in\] (1) at (0,0)<span>$F_R^{(2)}$</span>; (2) at (2,-1)<span>$F_R^{(1)}$</span>; (3) at (4,-2)<span>$F_R$</span>; (4) at (6,0)<span>$F_{R'}^{(2)}$</span>; (5) at (8,-1)<span>$F_{R'}^{(1)}$</span>; (6) at (10,-2)<span>$F_{R'}$</span>; (7) at (1,-3)<span>$E_R{^{(1)}}$</span>; (8) at (7,-3)<span>$E_{R'}{^{(1)}}$</span>; (1) edge\[-&gt;\] node\[right\] (2); (2) edge\[-&gt;\] node\[above\] (3); (1) edge\[-&gt;\] node\[left\] (4); (4) edge\[-&gt;\] node\[above right\]<span>$\Phi_{F_{R'}{^{(1)}}}$</span> (5); (5) edge\[-&gt;\] node\[above\]<span>$\Phi_{F_{R'}}$</span> (6); (3) edge\[-&gt;\] node\[above\] (6); (1) edge\[-&gt;\] node\[left\] (7); (7) edge\[-&gt;\] node\[above left\] (3); (4) edge\[-&gt;,dashed\] node\[left\] (8); (8) edge\[-&gt;\] node\[below right\] (6); (7) edge\[-&gt;\] node\[above\] (8); We proceed by claiming contiguity of the following. \[\] \(1) at (0,0)<span>$E_R^{(2)}$</span>; (2) at (2,0)<span>$E_R^{(1)}$</span>; (3) at (4,0)<span>$E_R$</span>; (7) at (2,2)<span>$F_R{^{(1)}}$</span>; (1) edge\[-&gt;,teal\] node\[below\] (2); (2) edge\[-&gt;,teal\] node\[below\] (3); (1) edge\[-&gt;,NavyBlue\] node\[left\] (7); (7) edge\[-&gt;,NavyBlue\] node\[right\] (3); \[xshift=3in\] (1) at (0,2)<span>$F_R^{(2)}$</span>; (2) at (2,2)<span>$F_R^{(1)}$</span>; (3) at (4,2)<span>$F_R$</span>; (7) at (2,0)<span>$E_R{^{(1)}}$</span>; (1) edge\[-&gt;,violet\] node\[below\] (2); (2) edge\[-&gt;,violet\] node\[below\] (3); (1) edge\[-&gt;,orange\] node\[below left\] (7); (7) edge\[-&gt;,orange\] node\[below right\] (3); \[yshift=-1.5in\] (1) at (0,2)<span>$F_R^{(2)}$</span>; (2) at (3,2)<span>$F_R^{(1)}$</span>; (7) at (3,0)<span>$E_R{^{(1)}}$</span>; (3) at (6,0)<span>$E_R$</span>; (1) edge\[-&gt;,violet\] node\[below\] (2); (2) edge\[-&gt;,NavyBlue\] node\[left\]
{'source': 'arXiv_out/1608'}