Adaptive random walks on the class of Web graphs

We study random walk with adaptive move strategies oil a class of directed graphs with variable wiring diagram. The graphs are grown from the evolutio n rules compatible with the dynamics of the worldwide Web [B. Tadic, Physic a A 293, 273 (2001)], and are characterized by a pair of power-law distribu tions of out- and in-degree for each value of the parameter beta, which mea sures the degree of rewiring in the graph. The walker adapts its move strat egy according to locally available information both oil out-degree of the v isited node and in-degree of target node. A standard random walk, on the ot her hand, uses the out-degree only. We compute the distribution of connecte d subgraphs visited by an ensemble of walkers, the average access time and survival probability of the walks. We discuss these properties of the walk dynamics relative to the changes in the global graph structure when the con trol parameter beta is varied. For beta greater than or equal to 3, corresp onding to the world-wide Web, the access time of the walk to a given level of hierarchy on the graph is much shorter compared to the standard random w alk on the same graph. By reducing the amount of rewiring towards rigidity limit beta --> beta (c) less than or similar to 0.1, corresponding to the r ange of naturally occurring biochemical networks, the survival probability of adaptive and standard random walk become increasingly similar. The adapt ive random walk can be used as ail efficient message-passing algorithm on t his class of graphs for large degree of rewiring.