Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/85363

Multiple random walks on complex networks: A harmonic law predicts search time

Authors Weng, Tongfeng HKUST affiliated (currently or previously).
Zhang, Jie
Small, Michael
Hui, Pan View this author's profile
Issue Date 2017
Source Physical Review E , v. 95, (5), May 2017, article number 052103
Summary We investigate multiple random walks traversing independently and concurrently on complex networks and introduce the concept of mean first parallel passage time (MFPPT) to quantify their search efficiency. The mean first parallel passage time represents the expected time required to find a given target by one or some of the multiple walkers. We develop a general theory that allows us to calculate the MFPPT analytically. Interestingly, we find that the global MFPPT follows a harmonic law with respect to the global mean first passage times of the associated walkers. Remarkably, when the properties of multiple walkers are identical, the global MFPPT decays in a power law manner with an exponent of unity, irrespective of network structure. These findings are confirmed by numerical and theoretical results on various synthetic and real networks. The harmonic law reveals a universal principle governing multiple random walks on networks that uncovers the contribution and role of the combined walkers in a target search. Our paradigm is also applicable to a broad range of random search processes. © 2017 American Physical Society.
ISSN 2470-0045
2470-0053
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science
Find@HKUST