  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 degree correlation serves as a local gradient
for which a bias towards selecting higher degree neighbors will on average
reduce the search time. Unfortunately, although the expected absorption time on
the graph can be written down using the theory of absorbing Markov chains,
computing this time is infeasible for large graphs. With this motivation, we
construct an absorbing Markov chain with a state for each degree of the graph,
and observe computing the expected absorption time is now computationally
feasible. Our paper finds preliminary results along the following lines: i)
there are graphs for which the proposed Markov model does and graphs for which
the model does not capture the absorbtion time, ii) there are graphs where
random sampling outperforms biased random walks, and graphs where biased random
walks are superior, and iii) the optimal bias parameter for the random walk is
graph dependent, and we study the dependence on the graph assortativity.
