کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418344 | 681642 | 2014 | 6 صفحه PDF | دانلود رایگان |
Consider the random walk on graphs such that, at each step, the next visited vertex is a neighbor of the current vertex, chosen with probability proportional to the inverse of the square root of its degree. On one hand, for every graph with nn vertices, the maximal mean hitting time for this degree-biased random walk is asymptotically dominated by n2n2. On the other hand, the maximal mean hitting time for the simple random walk is asymptotically dominated by n3n3. Yet, in this article, we exhibit for each positive integer nn:
• A graph of size nn with maximal mean hitting time strictly smaller for the simple random walk than for the degree-biased one.
• A graph of size nn with mean hitting time of a so called root vertex strictly smaller for the simple random walk than for the degree-biased one.
Journal: Discrete Applied Mathematics - Volume 170, 19 June 2014, Pages 104–109