复杂网络上随机游走具有概率保证的首达时间与覆盖时间及其应用

In the study of random walks, there are two highly desired quantities, first-passage time and cover time. In particular, there have been a lot of works focusing on calculation and analysis of mean first-passage time and mean cover time. However, under some scenarios, the expectation values of first-passage time and cover time cannot directly measure the efficiency of random walks. For example, in the random search task requiring high stable performance, it is desirable to know the time with guaranteed probability that walker can attain target nodes. Thus, in this project, we will propose two novel quantities, probability-guaranteed first-passage time and cover time, which separately characterize the time required to attain and cover target nodes with high probability. We will first build a framework to derive the theoretical prediction for probability-guaranteed first-passage time and cover time in a general network. Then we will unveil the inner theoretical relations between first-passage time and cover time, mean value and probability-guaranteed value of both quantities. In addition, we will develop a series of algorithms to optimize the probability-guaranteed first-passage time and cover time under different scenarios. At last, we will apply our theoretical results to the research of real-life large-scale traffic network. Through modeling the congestion in traffic flow by random walks and utilizing probability-guaranteed random walk times as key indicators, we will design online algorithms for congestion detection.

首达时间与覆盖时间是衡量随机游走的重要动力学指标。过去对于这两个量值的计算与研究主要围绕平均首达时间与期望覆盖时间展开。然而，在许多现实动力学中，如随机搜索，这两个量值并不能全面地描述随机游走的效率。特别是在对稳定性要求较高的搜索任务中，需要知道在多大时间内有极大概率可以访问到目标。这些方面还鲜有研究。因此，本项目提出两类新的随机游走时间：具有概率保证的首达时间与覆盖时间，即游走者具有极大概率在该时间内到达目标集合或覆盖所有目标节点。本项目将首先提出一般网络上这两个量值的评估方法，并进一步探讨首达时间与覆盖时间之间、这两类随机游走的期望值与概率保证值之间的内在联系。此外，本项目还将建立一系列算法，实现不同目标下对具有概率保证的首达时间与覆盖时间的优化。最后，本项目将利用随机游走对现实大规模交通流上的拥塞进行建模，应用具有概率保证的随机游走时间相关理论作为指导，设计拥塞检测的实时算法。

随机游走是复杂网络上最基础且最重要的动力学过程之一。本项课题通过运用统计物理、谱图理论、组合数学、图论等方法，对复杂网络中的几类特殊、重要的网络（无标度网络、分形网络、加权网络）上随机游走的理论、应用及其它相关问题进行了深入的研究。课题研究了首达时间、混合时间等随机游走的核心度量，提出了新的基于边性质的偏好游走，并对随机游走的关键问题——拉普拉斯矩阵的谱进行了深入研究。除了随机游走，我们还在图论其他领域做了一些研究。我们研究了幂律图的若干组合问题，研究了小世界层次图的拓扑和谱特性，证明了伪分形无标度网络和谢尔宾斯基分形垫的最小边支配集存在差异是由于无标度的拓扑性质。项目实施三年中，在国际重要SCI期刊上和顶级会议上发表标注项目资助的论文13余篇，其中期刊《The Computer Journal》7篇，《IEEE Transactions on Cybernetics》2篇，《Fractals》1篇，会议Proceedings of ACM International Conference on Information and Knowledge Management (CIKM) 2021年 1篇，Proceedings of The Web Conference (WWW) 2篇， 2020年和2021年各1篇。