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

摘要

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.