Abstract
A tabu random walk on a graph is a partially self-avoiding random walk which uses a bounded memory to avoid cycles. This memory is called a tabu list and contains vertices already visited by the walker. The size of the tabu list being bounded, the way vertices are inserted and removed from the list, called here an update rule, has an important impact on the performance of the walk, namely the mean hitting time between two given vertices.
We define a large class of tabu random walks, characterized by their update rules. We enunciate a necessary and sufficient condition on these update rules that ensures the finiteness of the mean hitting time of their associated walk on every finite and connected graph. According to the memory allocated to the tabu list, we characterize the update rules which yield smallest mean hitting times on a large class of graphs. Finally, we compare the performances of three collections of classical update rules according to the size of their associated tabu list.
This work has been partially supported by ANR Project Aresa2 and MSTIC Project Terra.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ochirkhand, E.O., Minier, M., Valois, F., Kountouris, A.: Resilient networking in wireless sensor networks. Research report, Inria (2010)
Ponsonnet, C.: Secure probabilistic routing in wireless sensor networks. Master thesis, Laboratoire Verimag (2011)
Lovász, L.: Random walks on graphs: A survey. In: Miklós, D., Sós, V.T., Szönyi, T. (eds.) Combinatorics, Paul Erdös is Eighty. Bolyai Society Mathematical Studies, vol. 2, pp. 1–46. János Bolyai Mathematical Society (1993)
Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs. Book in preparation (20XX), http://www.stat.berkeley.edu/~aldous/RWG/book.html
Slade, G.: The self-avoiding walk: A brief survey. In: Blath, J., Imkeller, P., Roelly, S. (eds.) To appear in Surveys in Stochastic Processes, Proceedings of the Thirty-third SPA Conference in Berlin, 2009. The EMS Series of Congress Reports (2010)
Li, K.: Performance analysis and evaluation of random walk algorithms on wireless networks. In: IPDPS Workshops, pp. 1–8 (2010)
Altisen, K., Devismes, S., Lafourcade, P., Ponsonnet, C.: Routage par marche aléatoire à listes tabous. In: Algotel 2011, Cap Estérel, Mai 23-26 (2011)
Ortner, R., Woess, W.: Non-backtracking random walks and cogrowth of graphs. Canad. J. Math. 59(4), 828–844 (2007)
Altisen, K., Devismes, S., Gerbaud, A., Lafourcade, P.: Comparisons of mean hitting times for tabu random walks on finite graphs. Technical report, Laboratoire Verimag (2011), http://www-verimag.imag.fr/TR/TR-2012-6.pdf
Hughes, B.: Random walks and random environments, vol. 1. Oxford University Press (1995)
Levin, D., Peres, Y., Wilmer, E.: Markov chains and mixing times. American Mathematical Society (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Altisen, K., Devismes, S., Gerbaud, A., Lafourcade, P. (2012). Analysis of Random Walks Using Tabu Lists. In: Even, G., Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2012. Lecture Notes in Computer Science, vol 7355. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31104-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-31104-8_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31103-1
Online ISBN: 978-3-642-31104-8
eBook Packages: Computer ScienceComputer Science (R0)