Random Walks with Look-ahead in Scale-free Random Graphs
Colin Cooper
Alan Frieze
10.1184/R1/6479267.v1
https://kilthub.cmu.edu/articles/journal_contribution/Random_Walks_with_Look-ahead_in_Scale-free_Random_Graphs/6479267
<p>If m ≥ 2 is constant and 0 ≤ r ≤ ε log log n for a small positive constant ε, then whp a random walk with look-ahead r on a scale-free graph G = G(m,n) has cover time C<sub>G</sub>(r) ∼ (2/(m<sup>r−1</sup> (m − 1))) n log n.</p>
2010-03-20 00:00:00
random walks
look-ahead
scale-free random graphs