Mixing Rates of Random Walks with Little Backtracking

被引：4

作者：

Cioaba, Sebastian M. ^{[1
]}

Xu, Peng ^{[1
]}

机构：

[1] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA

来源：

SCHOLAR - A SCIENTIFIC CELEBRATION HIGHLIGHTING OPEN LINES OF ARITHMETIC RESEARCH | 2015年 / 655卷

关键词：

Regular graph; cliques; random walk; mixing rate; eigenvalues; HYPERGRAPHS; SPECTRA; GRAPHS;

D O I：

10.1090/conm/655/13202

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Many regular graphs admit a natural partition of their edge set into cliques of the same order such that each vertex is contained in the same number of cliques. In this paper, we study the mixing rate of certain random walks on such graphs and we generalize previous results of Alon, Benjamini, Lubetzky and Sodin regarding the mixing rates of non-backtracking random walks on regular graphs.

引用

页码：27 / 58

页数：32

共 16 条

[1]

Aldous D., 2014, REVRSIBLE MARKOV CHA

[2]

ALON N., 2008, WILEY INTERSCIENCE S, DOI [10.1002/9780470277331, DOI 10.1002/9780470277331]

[3] Non-backtracking random walks mix faster [J].

Alon, Noga ;

Benjamini, Itai ;

Lubetzky, Eyal ;

Sodin, Sasha .

COMMUNICATIONS IN CONTEMPORARY MATHEMATICS, 2007, 9 (04) :585-603

[4] Poisson approximation for non-backtracking random walks [J].

Alon, Noga ;

Lubetzky, Eyal .

ISRAEL JOURNAL OF MATHEMATICS, 2009, 174 (01) :227-252

[5]

[Anonymous], 1997, CBMS Regional Conference Series in Mathematics

[6]

Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6

[7] Spectra of hypergraphs and applications [J].

Feng, KQ ;

Li, WCW .

JOURNAL OF NUMBER THEORY, 1996, 60 (01) :1-22

[8] Non-backtracking Random Walk [J].

Fitzner, Robert ;

van der Hofstad, Remco .

JOURNAL OF STATISTICAL PHYSICS, 2013, 150 (02) :264-284

[9] Spectral redemption in clustering sparse networks [J].

Krzakala, Florent ;

Moore, Cristopher ;

Mossel, Elchanan ;

Neeman, Joe ;

Sly, Allan ;

Zdeborova, Lenka ;

Zhang, Pan .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2013, 110 (52) :20935-20940

[10] Spectra of regular graphs and hypergraphs and orthogonal polynomials [J].

Li, WCW ;

Sole, P .

EUROPEAN JOURNAL OF COMBINATORICS, 1996, 17 (05) :461-477

← 1 2 →