Files and links (1)
PDFOpen Access (License Unspecified), Open Access
Dissertation
Performance of random walks and sampling for graph search
Doctor of Philosophy (Ph.D.), Drexel University
Sep 2018
DOI:
https://doi.org/10.17918/D8X096
Abstract
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.
Metrics
37 File views/ downloads
34 Record Views
Details
- Title
- Performance of random walks and sampling for graph search
- Creators
- Jonathan Stokes - DU
- Contributors
- Steven P. Weber (Advisor) - Drexel University (1970-)
- Awarding Institution
- Drexel University
- Degree Awarded
- Doctor of Philosophy (Ph.D.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Number of pages
- xii, 181 pages
- Resource Type
- Dissertation
- Language
- English
- Academic Unit
- College of Engineering (1970-2026); Electrical (and Computer) Engineering [Historical]; Drexel University
- Other Identifier
- 8187; 991014632068604721