A convex principle of search time for a multi-biased random walk on complex networks. (June 2021) - Wang, Yan; Cao, Xinxin; Weng, Tongfeng; Yang, Huijie; Gu, Changgui
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.