Estimating mean first passage time of biased random walks with short relaxation time on complex networks

Area of Science:

• Network Science
• Statistical Physics
• Computer Science

Background:

• Biased random walks are crucial in network analysis, particularly for transport and communication systems.
• Mean First Passage Time (MFPT) is a key performance metric, but existing calculation methods are computationally expensive or oversimplified.
• Current Mean Field Theory approaches inadequately account for local network structure variations.

Purpose of the Study:

• To derive an approximate bound for the MFPT of biased random walks on complex networks.
• To develop a method that incorporates local weight distribution beyond just node degree.
• To enable faster and more interpretable MFPT estimation.

Main Methods:

• Derivation of an approximate bound for MFPT in biased random walks with short relaxation times.
• Analysis of complex networks with arbitrarily assigned node weights.
• Comparison of theoretical results with computer simulations.

Main Results:

• The MFPT is shown to depend on both node degree and local weight distribution.
• A new theoretical analysis provides an approximate bound for MFPT.
• Computer simulations validate the accuracy of the derived theoretical analysis.

Conclusions:

• The new method allows for rapid estimation of MFPT.
• This approach effectively distinguishes nodes with similar degrees but different local weight distributions.
• The findings enhance understanding of biased random walk dynamics in complex networks.