Motivic constructions on graphs and networks with stability results

Abstract

Neste trabalho estudamos certos funtores sobre grafos, chamados de representáveis ou motívicos. Esses funtores não mudam os vértices de um grafo, mas apenas suas setas (as arestas direcionadas). Quaisquer tais funtores podem ser estendidos para networks (uma generalização de espaços métricos). Funtores de clustering sobre grafos dão origem a funtores de hierarchical clustering sobre networks. Mais ainda, podemos modificar a definição de funtor representável para criar filtrações de complexos simpliciais, que tem como caso particular os complexos de Vietoris-Rips e Cech. Isso faz com que possamos aplicar o funtor de homologia ˇ simplicial e obter um diagrama de persistência, como usual em Análise Topológica de Dados. Obtivemos resultados de estabilidade com respeito à distância bottleneck e à distância network, quando uma certa condição é imposta nos motivos de um funtor representável. Algumas operações sobre grafos (e.g., produtos e suspensão) também podem ser estendidas para networks, e três fórmulas de Künneth foram obtidas. Finalmente, alguns algoritmos e códigos para casos especiais são fornecidos com exemplos.

In this work we study certain functors on graphs, called representable or motivic. These functors do not change the vertices of a graph, but only its arrows (the directed edges). Any such functor can be extended to networks (a generalization of metric spaces). Clustering functors on graphs give rise to hierarchical clustering functors on networks. Moreover, we can further modify the definition of a representable functor on graphs to create simplicial complex filtrations on networks, which have as particular cases the Vietoris-Rips and the Cech simplicial complexes. This ˇ allows us to apply the simplicial homology functor and obtain a persistent diagram, as in the usual pipeline of Topological Data Analysis. We obtained some stability results regarding the bottleneck distance and the network distance, when a certain condition is imposed in the motives of a representable functor. Some operations on graphs can also be extended to networks (products and suspension), and three Künneth formulas were obtained. Finally, some algorithms and codes for special cases are provided with examples.