Analysis of Random Walks using Tabu Lists

• Main Authors: Altisen, Karine, Devismes, Stéphane, Gerbaud, Antoine, Lafourcade, Pascal
• Other Authors: VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne 2017-2020 (UCA 2017-2020 )-Centre National de la Recherche Scientifique (CNRS)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2012
• Subjects: Random walk; tabu list; mean hitting time; [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]; Iceland
• Online Access: https://hal.archives-ouvertes.fr/hal-01759228; https://hal.archives-ouvertes.fr/hal-01759228/document; https://hal.archives-ouvertes.fr/hal-01759228/file/AGDL12.pdf

International audience 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.