Topological graph persistence (Q827588): Difference between revisions

Persistent homology, a common tool arising in topological data analysis, is often defined with the filtration of a simplicial complex required as input. Specifically, we start with a simplicial complex \(K\) and a nested sequence of inclusions \(K_1 \subseteq K_2 \subseteq \cdots \subseteq K_n\). Then the persistent homology is encoded in the induced maps \[ H_p(K_1) \to H_p(K_2) \to \cdots \to H_p(K_n). \] Appearance and disappearance of homology classes is encoded in a persistence diagram, which is often viewed as a collection of off diagonal points in the plane for the (appearance, disappearance) of the features. It is less clear how to construct such a simplicial filtration when the starting input is graph data. While a graph can be viewed as a 1-dimensional simplicial complex, and a weighting function can easily be used to induce a filtration on this graph, the homology is too uninteresting to be useful in many applications. Thus, this paper investigates several possible definitions for how to turn (undirected, weighted) graph input data into a filtration for persistent homology based analyses. These constructions are: \begin{itemize} \item (Sec 3.1) The clique complex, which is the standard filtration which arises in the case of constructions such as the Vietoris Rips complex; \item (Sec 3.2) Neighborhood complex, which is the nerve of the cover induced by the neighborhoods of vertices; \item (Sec 3.3) The complex defined by what the authors call ``enclaveless sets'', which are essentially dual to dominating sets; and \item (Sec 3.4) The complex induced by independent sets in the graph. \end{itemize} The authors further provide a pseudodistance for graphs and filtrations, although this is limited to the case where the objects to be compared are isomorphic. We also direct the interested reader to the following citation, which has some overlap with this paper: [\textit{M. E. Aktas} et al., ``Persistence homology of networks: methods and applications'', Appl. Netw. Sci. 4, 61 (2019; \url{https://doi.org/10.1007/s41109-019-0179-3})].