Characteristic times of biased random walks on complex networks

Abstract

We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree $k$ is proportional to $k^{\alpha }$, where $\alpha$ is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely: i) the time the walker needs to come back to the starting node, ii) the time it takes to visit a given node for the first time, and iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of $\alpha$ which minimizes the three characteristic times is different from the value ${\alpha }_{\min }=-1$ analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of ${\alpha }_{\min }$ in the range $[-1,-0.5]$, while disassortative networks have ${\alpha }_{\min }$ in the range $[-0.5,0]$. We derive an analytical relation between the degree correlation exponent $\nu$ and the optimal bias value ${\alpha }_{\min }$, which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks, by means of an appropriate tuning of the motion bias.

18 pages, 14 figures, 1 table

References in corpus (18)

• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Statistical physics of social dynamics
• Synchronization in complex networks
• Community Structure in Jazz
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• First-passage times in complex scale-invariant media
• Entropy Rate of Diffusion Processes on Complex Networks
• Exact mean first-passage time on the T-graph
• Maximal-entropy random walks in complex networks with limited information
• Random walks on weighted networks
• Determining mean first-passage time on a class of treelike regular fractals
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Topologically biased random walk with application for community finding in networks
• Ring structures and mean first passage time in networks
• Navigating Networks with Limited Information
• Growing distributed networks with arbitrary degree distributions
• Random Walks on Complex Networks

Cited by in corpus (26)

• Random walks and diffusion on networks
• Multifractal analysis of financial markets
• Network dynamics of innovation processes
• Efficient exploration of multiplex networks
• Mean first-passage time for maximal-entropy random walks in complex networks
• Heterogeneous continuous time random walks
• Epidemic spreading driven by biased random walks
• Multifractal Characterization of Protein Contact Networks
• Random walks on complex networks under node-dependent stochastic resetting
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Random walks on complex networks with multiple resetting nodes: a renewal approach
• A comparative analysis of knowledge acquisition performance in complex networks
• Reactive random walkers on complex networks
• Connecting Network Science and Information Theory
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time
• From random walks on networks to nonlinear diffusion
• Random Walk with Memory on Complex Networks
• Biased random walkers and extreme events on the edges of complex networks
• Hubs-biased resistance distances on graphs and networks
• Unexpected advantages of exploitation for target searches in complex networks
• Degree-penalized contact processes
• Non-equilibrium random walks on multiplex networks
• Cross-frequency interactions during diffusion on complex brain networks are facilitated by scale-free properties
• Dynamics on networks. Case of Heterogeneous Opinion Status Model
• Comparative study of random walks with one-step memory on complex networks
• Core-biased random walks in complex networks