In this paper, we introduce random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension @math , a random walk with an absorbing state is defined which relates to the spectrum of the @math -dimensional Laplacian for @math and which relates to the local random walk on a graph defined by Fan Chung. We also examine an application of random walks on simplicial complexes to a semi-supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs.
Both @cite_0 @cite_11 have examined the relation between graph random walks and the geometry of graphs with Dirichlet boundary conditions. In section we show that under certain conditions the Dirichlet random walk in codimension 0 coincides with the notion of a random walk on a graph with Dirichlet boundary. A natural question to ask concerning random walks on simplicial complexes is: what would be the analogous process on manifolds? In general we are not aware of results on the continuum limit of these walks. However, the Dirichlet random walk in codimension zero is analogous to the concept of Brownian motion with killing as described by Lawler and Sokal in @cite_9 .
@cite_0 @cite_9 @cite_11
2038098381 2032336879
The difference Laplacian on a square lattice in Rn has been stud- ied by many authors. In this paper an analogous difference operator is studied for an arbitrary graph. It is shown that many properties of the Laplacian in the continuous setting (e.g. the maximum principle, the Harnack inequality, and Cheeger's bound for the lowest eigenvalue) hold for this difference oper- ator. The difference Laplacian governs the random walk on a graph, just as the Laplace operator governs the Brownian motion. As an application of the theory of the difference Laplacian, it is shown that the random walk on a class of graphs is transient. The random walks we consider are defined as follows. Let K be a connected graph (i.e. a one dimensional simplicial complex). For a vertex x E K, let m(x) denote the number of edges emanating from x. The probability that a particle moves from x to another vertex y E K is l m(x) if x and y are connected by an edge and it is zero otherwise. As observed by Courant, Friedrichs and Lewy (CFL) for the case of a square lattice in the plane this random walk is intimately related to the difference analog of the Laplacian For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions.