Random walks on simplicial complexes and harmonics1. Issue 2 (7th March 2016)

• Record Type: Journal Article
• Authors: Mukherjee, Sayan; Steenbergen, John
• Is Part Of: Random structures & algorithms. Volume 49:Issue 2(2016)
• Page Start: 379
• Page End: 405
• Publication Date: 2016-03-07
• Subjects: spectral theory -- random walks -- simplicial complexes; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20645
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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