Random Walks in the Edge Sampling Model

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2016-06-30
Authors/Contributors
Author: Xu, Chang
Abstract
The random walk is an important tool to analyze the structural features of graphs such as the community structure and the PageRank. The problem of generating a random walk may be hard if we are not given full access to the graph. The main component of this thesis is solving the problem in one such model with restricted access to the graph, the edge sampling model. We design Sampling-AS, a randomized algorithm that efficiently samples the endpoint of a random walk, unless some unlikely event happens during the execution of the algorithm. We also propose Sampling-LS, a randomized algorithm that always samples the endpoint of a random walk; however, its performance is not as good. Moreover, we slightly modify both algorithms to improve their performance on some special classes of graphs such as regular graphs, random graphs and fast mixing graphs. Finally, we consider some applications for both algorithms.
Document
Identifier
etd9640
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Bulatov, Andrei
Thesis advisor: Berenbrink, Petra
Member of collection
Attachment Size
etd9640_CXu.pdf 636.28 KB