Predicting cover-time distribution of noncompact random walks

Area of Science:

• Complex Systems Science
• Network Theory
• Statistical Physics

Background:

• The cover-time problem is crucial for understanding exhaustive exploration in complex domains.
• Estimating cover-time distribution from system structure is challenging but valuable for applications.
• Existing methods lack analytical approaches for predicting cover-time distributions.

Purpose of the Study:

• To propose an analytical scheme for estimating the original cover-time distribution.
• To leverage the universal cover-time distribution after rescaling.
• To provide a novel analytical tool for analyzing exhaustive random exploration.

Main Methods:

• Approximating first-passage time by the inverse of the occupation ratio (node visit probability).
• Relating node degree to occupation ratio via a fitting constant.
• Rescaling original cover times by first-passage times to obtain a universal distribution.
• Deriving the original cover-time distribution from the universal scaled distribution.

Main Results:

• Demonstrated excellent agreement between theoretical predictions and numerical simulations for various network systems.
• Validated the approximation of first-passage time by inverse occupation ratio.
• Derived a validity bound for the mean-field approximation on Erdős-Rényi graphs, identifying conditions for potential failure in sparse networks.

Conclusions:

• The proposed scheme provides an effective analytical method for estimating cover-time distributions.
• The findings offer a valuable tool for analyzing random walks and exhaustive exploration in complex networks.
• Understanding the limitations of the mean-field approximation in sparse networks is crucial for accurate analysis.