Random walks on dense graphs and graphons

Research output: Contribution to journalArticlepeer-review


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
Pages (from-to)2323-2345
Number of pages23
JournalSIAM Journal of Applied Mathematics
Issue number6
Publication statusPublished - 5 Nov 2021


  • graphons
  • random walk
  • network
  • functional analysis


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

Cite this