1st International ICST Workshop on Tools for solving Structured Markov Chains

Research Article

Efficiency of random walks for search in different network structures

Download242 downloads
  • @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
Gerhard Hasslinger1,*, Sebastian Kempken2,*
  • 1: T-Systems Enterprise Syste Deutsche-Telekom-Allee 7 D-64295 Darmstadt, Germany
  • 2: Department of Computer Science University of Duisburg-Essen D-47057 Duisburg, Germany
*Contact email: gerhard.hasslinger@telekom.de, kempken@inf.uni-dui.de

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.