Silvia Bartolucci, Fabio Caccioli, Francesco Caravelli, Pierpaolo Vivo
SciPost Phys. 11, 088 (2021) ·
published 4 November 2021

· pdf
We derive an approximate but explicit formula for the Mean First Passage Time
of a random walker between a source and a target node of a directed and
weighted network. The formula does not require any matrix inversion, and it
takes as only input the transition probabilities into the target node. It is
derived from the calculation of the average resolvent of a deformed ensemble of
random substochastic matrices $H=\langle H\rangle +\delta H$, with $\langle
H\rangle$ rank$1$ and nonnegative. The accuracy of the formula depends on the
spectral gap of the reduced transition matrix, and it is tested numerically on
several instances of (weighted) networks away from the high sparsity regime,
with an excellent agreement.
SciPost Phys. Lect. Notes 33 (2021) ·
published 10 August 2021

· pdf
We review the problem of how to compute the spectral density of sparse
symmetric random matrices, i.e. weighted adjacency matrices of undirected
graphs. Starting from the EdwardsJones formula, we illustrate the milestones
of this line of research, including the pioneering work of Bray and Rodgers
using replicas. We focus first on the cavity method, showing that it quickly
provides the correct recursion equations both for single instances and at the
ensemble level. We also describe an alternative replica solution that proves to
be equivalent to the cavity method. Both the cavity and the replica derivations
allow us to obtain the spectral density via the solution of an integral
equation for an auxiliary probability density function. We show that this
equation can be solved using a stochastic population dynamics algorithm, and we
provide its implementation. In this formalism, the spectral density is
naturally written in terms of a superposition of local contributions from nodes
of given degree, whose role is thoroughly elucidated. This paper does not
contain original material, but rather gives a pedagogical overview of the
topic. It is indeed addressed to students and researchers who consider entering
the field. Both the theoretical tools and the numerical algorithms are
discussed in detail, highlighting conceptual subtleties and practical aspects.
Dr Vivo: "see attached pdf"
in Submissions  report on "Spectrally gapped" random walks on networks: a Mean First Passage Time formula