Date Added: Jan 2012
Random walk is a means of network node sampling that requires little index maintenance and can function on almost all connected network topologies. With careful guidance, node samples following a desired probability distribution can be generated with the only requirement that the sampling probabilities of each visited node and its direct neighbors are known at each walk step. This paper describes a broad range of network applications that can benefit from such guided random walks in dynamic and decentralized settings. This paper also examines several key issues for implementing random walks in self-organizing networks, including the convergence time of random walks, impact of dynamic network changes and particularly resulted walker losses, and the difficulty of pacing walk steps without synchronized clocks between network nodes.