Random search processes, Levy fllights, and random walks on complex networks

通过对随机搜索过程的分析和数值研究，本项目旨在通过分析随机行走者的首次到达时间、搜索可靠性和随机搜索过程的效率来理解随机行走者的搜索策略。该项目阐明了搜索优化中不对称Levy飞行背后的机制。这将通过在没有和存在外部偏置的情况下研究带有δ -汇项的福克-普朗克方程，并在另一方面应用朗之万方程方法来实现。该项目还涉及复杂网络和图上的有偏和无偏随机漫步的研究，包括空间随机图和有向图。所开发的方法和工具预计将适用于物理、化学和生物学中出现的各种现象，以及基本上采用随机工作过程来执行所需任务的各种算法。虽然我们主要关注的是搜索算法，特别是页面排名及其变体，但其他知名的基于随机游走的算法，如BLAST（用于蛋白质和DNA比对）、推荐引擎和链接预测算法也可以从我们的分析中受益。

By providing analytical and numerical investigations of random search processes, this project aims at understanding the search strategy of a random walker by analyzing the first arrival time, search reliability, and the efficiency of the random search process. The project clarifies the mechanism behind asymmetric Levy flights in the search optimization. This will be enabled by investigating the Fokker-Planck equation with delta-sink term in absence and presence of external bias, at one hand and applying the Langevin equation approach on the other. The project also relates to investigation of biased and unbiased random walks on complex networks and graphs, including spatial random graphs and directed graphs. The methods and tools which will be developed are expected to be applicable for various phenomena arising in physics, chemistry, and biology as well as for various algorithms that essentially employ random work processes for performing a desired task. Although our primary focus is on search algorithms, in particular Page Rank and its variants, the other well-known algorithms based on random walks such as BLAST (for protein and DNA alignment), recommendation engines, and link predictions algorithms could also benefit from our analysis.