A convex principle of search time for a multi-biased random walk on complex networks. (June 2021)

• Record Type: Journal Article
• Authors: Wang, Yan; Cao, Xinxin; Weng, Tongfeng; Yang, Huijie; Gu, Changgui
• Is Part Of: Chaos, solitons and fractals. Volume 147(2021)
• Publication Date: 2021-06
• Subjects: Multi-biased random walk -- Convex function -- Complex networks; Chaotic behavior in systems -- Periodicals; Solitons -- Periodicals; Fractals -- Periodicals; Chaotic behavior in systems; Fractals; Solitons; Periodicals; 003.7
• DOI: 10.1016/j.chaos.2021.110990
• Languages: English
• ISSNs: 0960-0779

Abstract

Highlights: We propose multi-biased random walk search strategy on complex networks. We provide analytical expressions to calculate mean first passage time and mean first encounter time for finding a static and a mobile targets, respectively. We find that the search time of multi-biased random walk is governed by the convex principle. Abstract: We propose a mixed strategy named multi-biased random walk on complex networks, i.e., a walker simultaneously adopts different biased random walks with respective proportions. An analytical expression of mean first passage time is derived to quantify the expected time required to find a given target. The global mean first passage time of our strategy turns out to obey a convex function with respect to that of their associated pure strategies no matter the target is static or mobile. It is a fundamental law governing this mixed search strategy. These findings are confirmed by numerical and theoretical results on a number of synthetic and real networks.