Random walk on simplicial complexes
Institution:
université Paris-SaclayDisciplines:
Directors:
Abstract EN:
The notion of Laplacian of a graph can be generalized to simplicial complexes and hypergraphs. This notion contains information on the topology of these structures. In the first part of this thesis, we define a new Markov chain on simplicial complexes. For a given degree k of simplices, the state space is not thek-simplices as in previous papers about this subject but rather the set of k-chains or k-cochains.This new framework is the natural generalization on the canonical Markov chains on graphs.We show that the generator of our Markov chainis related to the upper Laplacian defined in the context of algebraic topology for discrete structure. We establish several key properties of this new process. We show that when the simplicial complexes under scrutiny are a sequence of ever refining triangulation of the flat torus, the Markov chains tend to a differential form valued continuous process.In the second part of this thesis, we explore some applications of the random walk, i.e., random walk based hole detection and simplicial complexes kernels. For the random walk based hole detection, we introduce an algorithm tomake simulations carried for the cycle-valuedrandom walk (k = 1) on a simplicial complex with holes. For the simplicial complexes kernels,we extend the definition of random walk based graph kernels in order to measure the similarity between two simplicial complexes.
Abstract FR:
La notion de laplacien d’un graphe peut être généralisée aux complexes simpliciaux et aux hypergraphes. Cette notion contient des informations sur la topologie de ces structures. Dans la première partie de cette thèse,nous définissons une nouvelle chaîne de Markov sur les complexes simpliciaux. Pour un degré donné k de simplexes, l’espace d’états n’est pas les k-simplexes comme dans les articles précédents sur ce sujet mais plutôt l’ensemble des k-chaines ou k-co-chaines. Ce nouveau cadre est la généralisation naturelle sur les chaînes de Markov canoniques sur des graphes. Nous montrons que le générateur de notre chaîne de Markov est lié au Laplacien supérieur défini dans le contexte de la topologie algébrique pour structure discrète. Nous établissons plusieurs propriétés clés de ce nouveau procédé. Nous montrons que lorsque les complexes simpliciaux examinés sont une séquence de triangulation du tore plat, les chaînes de Markov tendent vers une forme différentielle valorisée processus continu.Dans la deuxième partie de cette thèse, nous explorons quelques applications de la marche aléatoire, i.e. la détection de trous basée sur la marche aléatoire et les noyaux complexes simpliciaux. Pour la détection de trous basée sur la marche aléatoire, nous introduisons un algorithme pour faire des simulations effectuées pour la marche aléatoire à valeur cyclique (k = 1) sur un complexe simplicial avec trous. Pour les noyaux de complexes simpliciaux, nous étendons la définition des noyaux de graphes basés sur la marche aléatoire afin de mesurer la similitude entre deux complexes simpliciaux.