Random walk hitting times and effective resistance in sparsely connected Erdős-Rényi random graphs

Abstract

We prove expectation and concentration results for the following random variables on an Erdős-Rényi random graph $\mathcal{G}\left(n,p\right)$ in the sparsely connected regime $\log n+\log \log \log n\le np<n^{1/10}$: effective resistances, random walk hitting and commute times, the Kirchoff index, cover cost, random target times, the mean hitting time and Kemeny's constant. For the effective resistance between two vertices our concentration result extends further to $np\ge c\log n,c>0$. To achieve these results, we show that a strong connectedness property holds with high probability for $\mathcal{G}(n,p)$ in this regime.

32 pages, 1 figures. Final version published in JGT

References in corpus (1)

• A Tractable Variant of Cover Time

Cited by in corpus (3)

• Graph Resistance and Learning from Pairwise Comparisons
• Cover and Hitting Times of Hyperbolic Random Graphs
• Resistance distance distribution in large sparse random graphs