Efficiency of random walks for search in different network structures

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.