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

Abstract

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 $\Delta q$ as a power $<t_{aw}>\sim (\Delta q{)}^{-\theta }$. 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.

Revtex, 2 PostScript figures