Performance of random walks and sampling for graph search
Jonathan Stokes, Steven P. Weber · 2018
This thesis discusses several random walk and sampling algorithms and analyses the expected cost of using these algorithms to find target nodes in large graphs. The first algorithms discussed are degree biased random walks. A degree biased random walk variant is introduced entitled Self Avoiding Walk Jump (SAWJ). The innovation is in roughly upper bounding the expected unit cost for SAWJ to find a maximum degree node using a discrete time Markov chain model. Second this thesis estimates the expected unit and linear cost to find a target node in Erdos Renyi (ER) graphs under three variants of star sampling, where a random node is selected and it and its neighbors are sampled. These estimates are shown numerically to be accurate on ER and some real-world graphs. Third this thesis looks at questions tangentially related to analyzing graph search algorithms. Counter examples are given showing greedy wiring or rewiring algorithms do not necessarily construct maximally assortative simple graphs and an estimate is given of the expected samples to find a near maximum value in a set of elements with known distribution but unknown parameterization.