Access time of an adaptive random walk on the world-wide Web

We introduce and simulate the random walk that adapts move strategies according to local node preferences on a directed graph. We consider graphs with double-hierarchical connectivity and variable wiring diagram in the universality class of the world-wide Web. The ensemble of walkers reveals the structure of local subgraphs with dominant promoters and attractors of links. The average access time decays with the distance in hierarchy $Δq$ as a power $<t_{aw}> \sim (Δq)^{-θ}$. The access to highly connected nodes is orders of magnitude shorter compared to the standard random walk, suggesting the adaptive walk as an efficient message-passing algorithm on this class of graphs.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.