网络上随机游走的平均首达时间研究

随机游走作为重要的网络动力学之一,获得了足够的重视和广泛的应用。网络上随机游走的关键度量是平均首达时间。本文综述了网络上随机游走及其平均首达时间的相关研究。

广义伪分形网络上随机游走的平均首达时间的精确幂律

研究具有一个吸收点的广义伪分形网络上随机游走的平均首达时间.广义伪分形网络的显著特点是在每一次迭代中,每条现有的边会产生有限个节点.根据网络的演化算法,得到了平均首达时间的精确表达式.当网络的阶数足够大时,平均首达时间是按照网络节点数的幂律在增长.此外,可以通过改变网络参数来改善此类网络的随机游走的效率.这些研究结果是对伪分形网络相应结果的推广,将为深入研究各类分形网络的随机游走提供帮助.

强正则图与完全图字典积的平均首达时间及其应用

随着有限图上随机游走理论的发展,作为衡量传输效率的关键参数平均首达时间成为了数学家们致力研究的重要课题。本文利用多项式方法研究图上的随机游走,推导出强正则图与完全图字典积对应的转移概率矩阵及其特征值的完整信息,进一步研究字典积图上任意两点间的平均首达时间及电阻距离的计算公式,得到了该字典积图的度积基尔霍夫指数、凯梅尼常数及该图的电阻直径。该代数方法得到的表达式大大简化了强正则图与完全图字典积上随机游走平均首达时间的计算。

四面体图与完全图字典积的平均首达时间

利用多项式方法研究Johnson图J(n,3)与完全图字典积的图上随机游走。根据Hoffman多项式推导出该字典积的邻接矩阵和概率转移矩阵。进一步研究这个字典积上任意两点间的平均首达时间和电阻距离的显式公式。根据该字典积的邻接谱得到了度积基尔霍夫指数、凯梅尼常数和生成树数目。

折叠超立方体上的随机游动

本文主要研究折叠超立方体(FQn)上随机游动的平均首达时间(MFPT)。当随机游动遍历图中所有顶点对时,可得到全局平均首达时间的一个显式表达,即,如果n是奇数,;如果n是偶数,。此外,还给出了折叠超立方体上随机游动的效率衡量:,以及讨论了折叠超立方体的基尔霍夫指数的计算。In this paper, we mainly study the mean first-passage time (MFPT)) of random walks on folded hypercubes (FQn). We obtain an explicit expression of the mean first-passage time over all node pairs, that is, if n is odd,;if n is even, . Moreover, the scaling efficiency characterizing the random walks on is given: , and the Kirchhoff index of folded hypercubes is discussed.

空间网络上的随机游走

本文以一维均匀环为基础,通过添加有限数量的长程连接构造出了一维有限能量约束下的空间网络,环上任意节点i与j之间存在一条长程连接的概率满足p_(ij)∝d_(ij)^(-α)(α≥0),其中d_(ij)为节点i与j之间的网格距离,并且所有长程连接长度总和受到总能量Λ=cN(c≥0)的约束,N为网络节点总数.通过研究该空间网络上的随机游走过程,存在最优幂指数α_0使得陷阱问题的平均首达时间最短.进一步研究发现,平均首达时间与网络规模N之间存在着幂律关系,随着网络规模N和总能量Λ的增加,最优幂指数α_0单调增加,并趋近最优值1.5.

马尔科夫链中群逆稳定性分析

令P是有限状态离散马尔科夫链的转移矩阵,群逆(I-P)#在马尔科夫链分析中有着重要应用.给出了当P的每一个元素有小的相对扰动时,(I-P)#在范数意义下的相对扰动误差界.所得的界只依赖于矩阵的阶数,而与马尔科夫链本身的性质无关.

带有倾向性的环状网络Small-World现象的分析

一个环状网络可以由马尔科夫链来描述,并且通过求解该马尔科夫链的平均首达时间等指标来描述该网络的特点.一个带有倾向性的环状网络,其上马尔科夫链的平均首达时间解可以被精确求出.带有倾向性的环状网络上的Small-World现象与对称环状网络也有一定的差异.