Premium
Random walks on simplicial complexes and harmonics
Author(s) -
Mukherjee Sayan,
Steenbergen John
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20645
Subject(s) - random walk , simplicial complex , mathematics , generalization , abstract simplicial complex , context (archaeology) , dimension (graph theory) , combinatorics , laplace operator , simplicial approximation theorem , class (philosophy) , discrete mathematics , simplicial homology , computer science , pure mathematics , artificial intelligence , simplicial set , mathematical analysis , geography , statistics , homotopy , homotopy category , archaeology
In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d , a random walk with an absorbing state is defined which relates to the spectrum of the k ‐dimensional Laplacian for 1 ≤ k ≤ d . We study an example of random walks on simplicial complexes in the context of 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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 379–405, 2016