A model of self-avoiding random walks for searching complex networks

• Published in: Networks 2012-09, Vol.60 (2), p.71-85
• Main Authors: López Millán, Víctor M., Cholvi, Vicent, López, Luis, Fernández Anta, Antonio
• Format: Article
• Language: English
• Subjects: average search length; network search; one-hop replication; random walk; resource location; self-avoiding random walk
• ISSN: 0028-3045; 1097-0037
• DOI: 10.1002/net.20461

Random walks have been proven useful in several applications in networks. Some variants of the basic random walk have been devised pursuing a suitable trade‐off between better performance and limited cost. A self‐avoiding random walk (SAW) is one that tries not to revisit nodes, therefore covering the network faster than a random walk. Suggested as a network search mechanism, the performance of the SAW has been analyzed using essentially empirical studies. A strict analytical approach is hard since, unlike the random walk, the SAW is not a Markovian stochastic process. We propose an analytical model to estimate the average search length of a SAW when used to locate a resource in a network. The model considers single or multiple instances of the resource sought and the possible availability of one‐hop replication in the network (nodes know about resources held by their neighbors). The model characterizes networks by their size and degree distribution, without assuming a particular topology. It is, therefore, a mean‐field model, whose applicability to real networks is validated by simulation. Experiments with sets of randomly built regular networks, Erdős–Rényi networks, and scale‐free networks of several sizes and degree averages, with and without one‐hop replication, show that model predictions are very close to simulation results, and allow us to draw conclusions about the applicability of SAWs to network search. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012