Random walks on dense graphs and graphons

Résultats de recherche: Contribution à un journal/une revueArticleRevue par des pairs


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.
langue originaleAnglais
Pages (de - à)2323-2345
Nombre de pages23
journalSIAM Journal of Applied Mathematics
Numéro de publication6
Les DOIs
Etat de la publicationPublié - 5 nov. 2021

Empreinte digitale

Examiner les sujets de recherche de « Random walks on dense graphs and graphons ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation