Random walks on dense graphs and graphons

Research output: Contribution to journalArticlepeer-review

Abstract

Graph-limit theory focuses on the convergence of sequences of increasingly large graphs, providing a framework for the study of dynamical systems on massive graphs, where classical methods would become computationally intractable. Through an approximation procedure, the standard ordinary differential equations are replaced by nonlocal evolution equations on the unit interval. In this work, we adopt this methodology to prove the validity of the continuum limit of random walks, a largely studied model for diffusion on graphs. We focus on two classes of processes on dense weighted graphs, in discrete and in continuous time, whose dynamics are encoded in the transition matrix of the associated Markov chain or in the random-walk Laplacian. We further show that previous works on the discrete heat equation, associated to the combinatorial Laplacian, fall within the scope of our approach. Finally, we characterize the relaxation time of the process in the continuum limit.
Original languageEnglish
JournalSIAM Journal of Applied Mathematics
Volume81
Issue number6
DOIs
Publication statusPublished - 5 Nov 2021

Keywords

  • graphons
  • random walk
  • network
  • functional analysis

Fingerprint

Dive into the research topics of 'Random walks on dense graphs and graphons'. Together they form a unique fingerprint.

Cite this