Adaptive Random Walks on the Class of Web Graph

Abstract

We study random walk with adaptive move strategies on a class of directed graphs with variable wiring diagram. The graphs are grown from the evolution rules compatible with the dynamics of the world-wide Web [Tadić, Physica A {\bf 293}, 273 (2001)], and are characterized by a pair of power-law distributions of out- and in-degree for each value of the parameter $\beta$, which measures the degree of rewiring in the graph. The walker adapts its move strategy according to locally available information both on out-degree of the visited node and in-degree of target node. A standard random walk, on the other hand, uses the out-degree only. We compute the distribution of connected 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 control parameter $\beta$ is varied. For $\beta \ge 3$, corresponding 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 walk on the same graph. By reducing the amount of rewiring towards rigidity limit $β\to β_c \lesss im 0.1$, corresponding to the range of naturally occurring biochemical networks, the survival probability of adaptive and standard random walk become increasingly similar. The adaptive random walk can be used as an efficient message-passing algorithm on this class of graphs for large degree of rewiring.

8 pages, including 7 figures; to appear in Europ. Phys. Journal B

References in corpus (1)

• Statistical mechanics of complex networks

Cited by in corpus (28)

• Optimal network topologies for local search with congestion
• Congestion and centrality in traffic flow on complex networks
• Exploring complex networks by walking on them
• Network Landscape from a Brownian Particle's Perspective
• Transport on Complex Networks: Flow, Jamming and Optimization
• Extreme events in dynamical systems and random walkers: A review
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Exploring Complex Networks through Random Walks
• Statistical properties of sampled networks by random walks
• Self-avoiding walks on scale-free networks
• Extreme events and event size fluctuations in biased random walks on networks
• Walks on Apollonian networks
• Preferential Behaviour and Scaling in Diffusive Dynamics on Networks
• Learning about knowledge: A complex network approach
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Temporal fractal structures: Origin of power-laws in the world-wide Web
• Kinetic growth walks on complex networks
• Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
• Inter-arrival times of message propagation on directed networks
• Kinetic-growth self-avoiding walks on small-world networks
• Can car density in a two-lane section depend on the position of the latter in a single-lane road?
• Intermittent exploration on a scale-free network
• On Properties of Non-Markovian Random Walk in One Dimension
• Small-Worlds, Mazes and Random Walks
• Networks and Our Limited Information Horizon
• Gaussian Networks Generated by Random Walks
• Resource location based on precomputed partial random walks in dynamic networks
• Random Walks on Complex Networks