Mean first-passage time calculations: comparison of the deterministic Hill’s algorithm with Monte Carlo simulations

Accurate determination of mean first-passage times (MFPTs) between any two states of a complex network still attracts considerable attention. Appropriate methods should take into account the discrepancy in MFPTs when a random walker moves first from a source to a target and then in the opposite dire...

Full description

Saved in:
Bibliographic Details
Published in:The European physical journal. B, Condensed matter physics Condensed matter physics, 2012-04, Vol.85 (4), Article 116
Main Authors: Torchala, M., Chelminiak, P., Bates, P. A.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Comparative analysis
Complex Systems
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Condensed Matter Physics
Exact sciences and technology
Fluid- and Aerodynamics
Information retrieval. Graph
Monte Carlo method
Physics
Physics and Astronomy
Regular Article
Software
Solid State Physics
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Accurate determination of mean first-passage times (MFPTs) between any two states of a complex network still attracts considerable attention. Appropriate methods should take into account the discrepancy in MFPTs when a random walker moves first from a source to a target and then in the opposite direction. In addition, it is desirable to allow fast evaluation of mean first-passage times when transition probabilities are allowed to vary over time. For our calculations we make use of Hill’s algorithm, which enables the exact calculation of MFPTs. As we show in this work, when given a fixed distance to travel, the calculation of a particular MFPT depends on the choice of source and target points and their relative position on a lattice. We also demonstrate, when the network contains a relatively low number of cycles, that this deterministic technique provides exact results much faster in comparison to the more standard, but computationally demanding, stochastic Monte Carlo simulation method, where only approximate results can be obtained that are highly dependent on the number of walkers. Therefore, our specific implementation of Hill’s algorithm should facilitate efficient and accurate computation of MFPTs on a variety of network topologies of practical interest to the broad scientific community.
ISSN:1434-6028
1434-6036
DOI:10.1140/epjb/e2012-20760-8