Source-linked AI summary
Biased random walks on complex networks: the role of local navigation rules
Agata Fronczak, Piotr Fronczak
TL;DR
The paper asks how local navigation rules affect mean first-passage times on complex networks, where shortest-path routing would require global knowledge. For random uncorrelated networks, it analyzes walks biased by transition probabilities based on the next node’s connectivity, deriving stationary occupation and transit-time formulas and modeling cyclic search by degree renormalization. The mean first-passage time is reported to depend on destination, not source; the transit-time approximation agrees better with numerical calculations for α > αm.
Problem
The paper asks how local navigation rules affect mean first-passage times on complex networks, where shortest-path routing would require global knowledge.
Source: p. 1Method
For random uncorrelated networks, it analyzes walks biased by transition probabilities based on the next node’s connectivity, deriving stationary occupation and transit-time formulas and modeling cyclic search by degree renormalization.
Source: pp. 1–2Results
The mean first-passage time is reported to depend on destination, not source; the transit-time approximation agrees better with numerical calculations for α > αm.
Source: p. 4Takeaways & Limitations
The random-walk model describes free-flow traffic properties, and its results provide a basis for estimating the critical packet-generation rate.
Source: p. 1When target node j and its nearest neighborhood are replaced by a single node J of degree kJ, precise calculation or even estimation of R(0) is difficult.
Source: p. 5
Abstract
from arXiv · showhide
We study the biased random walk process in random uncorrelated networks with arbitrary degree distributions. In our model, the bias is defined by the preferential transition probability, which, in recent years, has been commonly used to study efficiency of different routing protocols in communication networks. We derive exact expressions for the stationary occupation probability, and for the mean transit time between two nodes. The effect of the cyclic search on transit times is also explored. Results presented in this paper give the basis for theoretical treatment of the transport-related problems on complex networks, including quantitative estimation of the critical value of the packet generation rate.