A model of self-avoiding random walks for searching complex networks
Visualitza/
Impacte
Scholar |
Altres documents de l'autoria: López Millán, Víctor M.; Cholvi, Vicent; López, Luis; Fernández Anta, Antonio
Metadades
Mostra el registre complet de l'elementcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7038
comunitat-uji-handle3:10234/8634
comunitat-uji-handle4:
INVESTIGACIONMetadades
Títol
A model of self-avoiding random walks for searching complex networksData de publicació
2012Editor
John Wiley & SonsISSN
1097-0037Cita bibliogràfica
López Millán, V. M., Cholvi, V., López, L., & Fernández Anta, A. (2012). A model of self‐avoiding random walks for searching complex networks. Networks, 60(2), 71-85.Tipus de document
info:eu-repo/semantics/articleVersió de l'editorial
http://onlinelibrary.wiley.com/doi/10.1002/net.20461/pdfVersió
info:eu-repo/semantics/submittedVersionParaules clau / Matèries
Resum
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-av ... [+]
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. [-]
Publicat a
Networks (2012), 60(2), 71-85.Drets d'accés
Copyright © 2011 Wiley Periodicals, Inc
http://rightsstatements.org/vocab/InC/1.0/
info:eu-repo/semantics/openAccess
http://rightsstatements.org/vocab/InC/1.0/
info:eu-repo/semantics/openAccess
Apareix a les col.leccions
- LSI_Articles [361]