Premium
A model of self‐avoiding random walks for searching complex networks
Author(s) -
López Millán Víctor M.,
Cholvi Vicent,
López Luis,
Fernández Anta Antonio
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20461
Subject(s) - random walk , computer science , replication (statistics) , evolving networks , scale free network , random graph , complex network , markov process , preferential attachment , degree (music) , random walker algorithm , degree distribution , theoretical computer science , mathematics , graph , statistics , physics , world wide web , acoustics
Abstract 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