论文标题
双曲随机图的覆盖和击打时间
Cover and Hitting Times of Hyperbolic Random Graphs
论文作者
论文摘要
我们研究了双曲线随机图（HRG）的巨大组成部分，当时学位分布遵守指数范围内的功率定律（2,3）$时。特别是，我们首先关注随机步行的预期时间，以击中给定的顶点或访问，即掩护，所有顶点。我们表明，A.A.S。 （相对于HRG），直到乘法常数：封面时间为$ n（\ log n）^2 $，最大打击时间为$ n \ log n $，平均打击时间为$ n $。然后，我们确定在两个给定的顶点A.A.S.之间通勤的预期时间，最高为$ n $的小因素的小因素，以及在涉及的两对顶点的一些轻度假设下。我们的结果是通过使用与双曲平面平铺相关的精心设计的网络流消散的能量来控制有效电阻的，我们在其上覆盖了森林样结构。
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.
