  The random walk with choice is a well known variation to the random walk that
first selects a subset of $d$ neighbours nodes and then decides to move to the
node which maximizes the value of a certain metric; this metric captures the
number of (past) visits of the walk to the node. In this paper we propose an
enhancement to the random walk with choice by considering a new metric that
captures not only the actual visits to a given node, but also the intensity of
the visits to the neighbourhood of the node. We compare the random walk with
choice with its enhanced counterpart. Simulation results show a significant
improvement in cover time, maximum node load and load balancing, mainly in
random geometric graphs.
