重启策略对网络随机搜索效率影响研究

作     者：陈永金 

作者单位：广州大学 

学位级别：硕士

导师姓名：彭俊好

授予年度：2024年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：伪分形无标度网络 Barab(?)si-Albert网络 重启策略 

摘      要：对于一般的随机搜索过程中,游走者在每一时间步长移动到当前位置的其中一个邻居节点上,直到首次找到目标节点。该过程中,我们关注于如何减少游走者的平均首次通过目标节点的时间（mean first-passage time,MFPT）。而重启策略的加入,可以很好的使得游走者首次通过目标的平均时间存在最佳值,这可以通过选取最优的重启概率来实现。在大规模的复杂网络的背景下,关于受重启策略影响的随机游走的众多研究成果不断涌现。 我们研究了在不知目标位置的情况下,不同的重启策略对离散时间随机搜索效率的影响。我们特别关注了具有不断增长节点的伪分形无标度网络（pseudofractal scale-free web,PSFW）中的几何分布重启策略,其中,游走者每一次有两种选择:以1-的概率移动到当前节点中的相邻位置,或以的概率重新启动到初始位置。针对这种重启策略,我们探究了从不同的位置出发的情景,给出了相应的平均首次通过时间的精确结果,确定了使得MFPT达到最小值的最优重启概率*,并评估了每种情景下的MFPT与未重启的MFPT的比值。此外,我们还研究了这样一种情景,即在大型PSFW中重启到从稳态分布中随机选择的节点的重启策略。同时,我们也给出固定周期重启策略和稳态分布重启策略的MFPT的谱表示公式,在Barab′asi-Albert网络中计算从任意节点出发到达目标节点的MFPT的平均值（global mean first-passage time,GMFPT）,并通过对比未重启的GMFPT得出这两种重启策略对网络搜索效率的影响。 对于在大规模网络的PSFW上的几何分布重启离散时间随机搜索中,重启位置选择为具有最高度值且与目标节点相邻的节点,或选择为距离目标节点最远的节点和节点,几何分布重启策略都会阻碍着游走者找到目标节点。然而,重启位置选择为具有第二或第三大度值且与目标节点相邻的节点,几何分布重启策略总是可以在一定程度上加快搜索过程以达到目标。重启位置选择为与目标节点相邻且度值最低的邻居,几何分布重启策略可以显著加快行走者到达目标节点的过程。当重启位置是从稳态分布中随机选择的节点时,则该重启也可以显著加速游走者在大型PSFW中到达目标节点的搜索过程。研究结果表明,对于较大规模的PSFW,重启位置的度值和目标与重启位置之间的距离对搜索效率都有显著影响。重启位置的度值越大,游走者向目标的收敛速度越慢。 此外,在Barab′asi-Albert网络上的固定周期重启离散时间随机搜索中,当目标节点的度值较大时,固定周期重启策略是可以加快对网络全局的搜索过程。而对于稳态分布重启下的离散时间随机搜索中,影响全局首次通过时间的因素与目标节点的度值大小有关。当目标节点的度值较大,稳态分布重启策略总可以加快网络全局的搜索过程。而当目标节点度值越小时,则稳态分布重启策略可以显著加快游走者在Barab′asi-Albert网络中任意节点到达目标节点的过程。结果表明,目标节点的度值大小对网络全局搜索过程有明显影响。