  We develop a model for a random walker with long-range hops on general
graphs. This random multi-hopper jumps from a node to any other node in the
graph with a probability that decays as a function of the shortest-path
distance between the two nodes. We consider here two decaying functions in the
form of the Laplace and Mellin transforms of the shortest-path distances.
Remarkably, when the parameters of these transforms approach zero
asymptotically, the multi-hopper's hitting times between any two nodes in the
graph converge to their minimum possible value, given by the hitting times of a
normal random walker on a complete graph. Stated differently, for small
parameter values the multi-hopper explores a general graph as fast as possible
when compared to a random walker on a full graph. Using computational
experiments we show that compared to the normal random walker, the multi-hopper
indeed explores graphs with clusters or skewed degree distributions more
efficiently for a large parameter range. We provide further computational
evidence of the speed-up attained by the random multi-hopper model with respect
to the normal random walker by studying deterministic, random and real-world
networks.
