Research Article
Efficiency of random walks for search in different network structures
@INPROCEEDINGS{10.4108/smctools.2007.2025, author={Gerhard Hasslinger and Sebastian Kempken}, title={Efficiency of random walks for search in different network structures}, proceedings={1st International ICST Workshop on Tools for solving Structured Markov Chains}, proceedings_a={SMCTOOLS}, year={2010}, month={5}, keywords={Random walks transient analysis coverage of search}, doi={10.4108/smctools.2007.2025} }- Gerhard Hasslinger
Sebastian Kempken
Year: 2010
Efficiency of random walks for search in different network structures
SMCTOOLS
ICST
DOI: 10.4108/smctools.2007.2025
Abstract
Dynamic overlay networks on the Internet as well as ad hoc networks often rely on self-organizing distributed communication and construction techniques. When there are no central management facilities and search indices available, flooding is a standard method to collect knowledge about the network structure and the content on the nodes. In recent time, random walks have attracted attention as an alternative search method in P2P networks. The efficiency of the method is usually evaluated by simulation studies. In this paper we use transient analysis as a simple and scalable approach to examine the properties of random walks. The convergence to steady state and the coverage of the network in the course of the random work are main characteristics to be analyzed. In our evaluations we consider network examples of different type and size.
