arXiv / 2022

Cover and Hitting Times of Hyperbolic Random Graphs

Marcos Kiwi, Markus Schepers, John Sylvester

Graph Learning

We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range $(2,3)$. In particular, we first focus on the expected time for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that, a.a.s. (with respect to the HRG), and up to multiplicative constants: the cover time is $n(\log n)^2$, the maximum hitting time is $n\log n$, and the average hitting time is $n$. We then determine the expected time to commute between two given vertices a.a.s., up to a small factor polylogarithmic in $n$, and under some mild hypothesis on the pair of vertices involved. Our results are proved by controlling effective resistances using the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane, on which we overlay a forest-like structure.

0 citations0 influential

Full paper

Read the original paper

Open PDF Source page

Learning resources

arXiv PDFPDF arXiv abstract pagearXiv Google Scholar referencesGoogle Scholar Papers with Code searchPapers with Code YouTube explanationsYouTube

Reading state

Discuss in ChatGPT

Uses your own ChatGPT account. The paper context is copied into a tutor prompt before ChatGPT opens.

Preview prompt

You are my AI/ML research paper instructor. I want to deeply understand the paper below.

First, teach it in layers:
1. One-paragraph intuition.
2. Problem statement and why it mattered.
3. Key method, architecture, or algorithm.
4. Important equations or mechanisms, explained intuitively.
5. Experiments and evidence.
6. Limitations, assumptions, and failure modes.
7. How this paper influenced later AI/ML/Deep Learning/GenAI work.
8. A 30-minute study plan with checkpoints.
9. Quiz me with 5 questions and wait for my answers.

When something is not available in the attached context, say what is missing and infer carefully.

### Paper attached as context
Title: Cover and Hitting Times of Hyperbolic Random Graphs
Authors: Marcos Kiwi, Markus Schepers, John Sylvester
Year: 2022
Venue: arXiv
Categories: Graph Learning
Citations: 0
Paper URL: https://arxiv.org/abs/2207.06956v3
Open PDF: https://arxiv.org/pdf/2207.06956v3

Abstract:
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range $(2,3)$. In particular, we first focus on the expected time for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that, a.a.s. (with respect to the HRG), and up to multiplicative constants: the cover time is $n(\log n)^2$, the maximum hitting time is $n\log n$, and the average hitting time is $n$. We then determine the expected time to commute between two given vertices a.a.s., up to a small factor polylogarithmic in $n$, and under some mild hypothesis on the pair of vertices involved. Our results are proved by controlling effective resistances using the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane, on which we overlay a forest-like structure.

Learning resources:
- PDF: arXiv PDF (https://arxiv.org/pdf/2207.06956v3)
- arXiv: arXiv abstract page (https://arxiv.org/abs/2207.06956v3)
- Google Scholar: Google Scholar references (https://scholar.google.com/scholar?q=Cover%20and%20Hitting%20Times%20of%20Hyperbolic%20Random%20Graphs)
- Papers with Code: Papers with Code search (https://paperswithcode.com/search?q=Cover%20and%20Hitting%20Times%20of%20Hyperbolic%20Random%20Graphs)
- YouTube: YouTube explanations (https://www.youtube.com/results?search_query=Cover%20and%20Hitting%20Times%20of%20Hyperbolic%20Random%20Graphs+paper+explained)