Journal article
A Markov chain model for the search time for max degree nodes in a graph using a biased random walk
24 Feb 2016
Abstract
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.
Metrics
2 Record Views
Details
- Title
- A Markov chain model for the search time for max degree nodes in a graph using a biased random walk
- Creators
- Jonathan StokesSteven Weber
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Identifiers
- 991019170461804721