A model of self-avoiding random walks for searching complex networks
Ver/ Abrir
Impacto
Scholar |
Otros documentos de la autoría: López Millán, Víctor M.; Cholvi, Vicent; López, Luis; Fernández Anta, Antonio
Metadatos
Mostrar el registro completo del ítemcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7038
comunitat-uji-handle3:10234/8634
comunitat-uji-handle4:
INVESTIGACIONMetadatos
Título
A model of self-avoiding random walks for searching complex networksFecha de publicación
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.Tipo de documento
info:eu-repo/semantics/articleVersión de la editorial
http://onlinelibrary.wiley.com/doi/10.1002/net.20461/pdfVersión
info:eu-repo/semantics/submittedVersionPalabras clave / Materias
Resumen
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. [-]
Publicado en
Networks (2012), 60(2), 71-85.Derechos de acceso
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
Aparece en las colecciones
- LSI_Articles [366]