A Markov chain model for the search time for max degree nodes in a graph using a biased random walk

Jonathan Stokes, Steven Weber

We consider the problem of estimating the expected time to find a maximum degree node on a graph using a (parameterized) biased random walk. For assortative graphs the positive deg…