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

Random Walks on Folded Hypercubes

摘要: 本文主要研究折叠超立方体(FQ_n)上随机游动的平均首达时间(MFPT)。当随机游动遍历图中所有顶点对时，可得到全局平均首达时间的一个显式表达，即，如果n是奇数，；如果n是偶数，。此外，还给出了折叠超立方体上随机游动的效率衡量：，以及讨论了折叠超立方体的基尔霍夫指数的计算。

In this paper, we mainly study the mean first-passage time (MFPT)) of random walks on folded hypercubes (FQ_n). 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.

1. 引言

图上的简单随机游动指的是质点在某个顶点i处，下一时刻到达它每一个邻点概率相等的游动过程。它实际上是一个马尔科夫过程： $X_0,X_1,\cdots ,X_n,\cdots$，其中 $X_n$ 表示质点在时刻n所处的位置。简单随机游动最初是由Pearson [1] 提出的，后来进行了大量的研究并且得到广泛的应用 [2] [3]。其中许多应用都与统计量有关，包括首达时间(FPT) [4]，平均首达时间(MFPT) [5]，全局首达时间(GFPT) [6]，全局平均首达时间(GMFPT) [7]。

对连通图 $G=\left(V,E\right)$，令 $T_{ij}=\min \left\{n:n\ge 0,X_n=j,X_0=i\right\}$，它表示一个质点从图上一顶点i出发，第一次到达顶点j所需要的时间为n或经过n步首次到达顶点j。则期望 $\overline{T_{ij}}=E_i{T}_j={\displaystyle {\sum }_{n=1}^{\infty }nP\left\{T_{ij}=n|X_0=i\right\}}$ 就是顶点i到顶点j的平均首达时间(MFPT)它表示从顶点i出发首次到达顶点 的期望时间。图上所有顶点

对的平均首达时间的平均值用 ${\langle T\rangle }_n=\frac{1}{n\left(n-1\right)}{\displaystyle {\sum }_i{\displaystyle {\sum }_{j\ne i}\overline{T_{ij}}}}$ 表示，称为全局平均首达时间(GMFPT)。

研究图上简单随机游动的一个重要方法是电网络方法。电网络方法为理解随机游动的某些参数提供了直观的基础，并通过随机游动过程中电阻距离与参数之间的关系，极大地简化了这些参数的计算和估计。本文就是利用电网络方法得到折叠超立方体上随机游动的全局平均首达时间的一个表达式。Doyle和Snell [8] 研究了随机游动和电网络之间的关系，他们指出一个无向图的每一条边都当成电阻值为1的单位电阻，则这个图就可以看作一个电网络。Klein和Randic [9] 提出了一个很有用的参数—电阻距离，记为 $r_{ij}$ (1安培的电流从顶点i流进，顶点j流出这个电网络，则i，j之间的电势差称为i，j之间的等效电阻或电阻距离)。基于电阻距离的一个著名的拓扑指数为基尔霍夫指数 [9]，它被定义为图G上所有顶点对的电阻距离之和，记为 $K_f={\displaystyle {\sum }_{i<j}{r}_{ij}}$。

然而设计计算电阻距离与基尔霍夫指数的有效算法是有困难的。因此，对于某些特殊结构的图类，寻找它的基尔霍夫指数的显式表达是有意义的。折叠超立方体网络近年来引起了人们对广泛关注。由EI-Amawy和Latifi [10] 首次提出的折叠超立方体( $F{Q}_n$ )是超立方体( $Q_n$ )的一个重要变形。但是在很多性

质上折叠超立方体要优于超立方体，例如 $F{Q}_n$ 的直径为 $\left[\frac{n}{2}\right]$，约为 $Q_n$ 的一半。更多的性质可参见 [11] [12] [13] [14]。n维折叠超立方体是定义在集合 ${\left\{0,1\right\}}^n$ 上的含有 $2^n$ 个顶点的图。它的一个顶点x可以由序列 $x=\left(x_1,x_2,\cdots ,x_n\right)$ 编码，其中每一个 $x_i$ 取值为0或1，两个顶点之间有边相连当且仅当它们在一个坐标或全部坐标的值不同时。显然折叠超立方体的顶点数为 $N=2^n$，边数为 $E=\left(n+1\right)2^{n-1}$。

此外，我们还需要介绍一下图的拉普拉斯谱。矩阵 $L\left(G\right)=D\left(G\right)-A\left(G\right)$ 称为图G的拉普拉斯矩阵，其中 $D\left(G\right)$ 是图G的度矩阵， $A\left(G\right)$ 是图G的邻接矩阵。 $L\left(G\right)$ 的特征值则为图G的拉普拉斯特征值，所有的拉普拉斯特征值： ${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_N$，构成图G的拉普拉斯谱，记为 $Spe{c}_L\left(G\right)$。拉普拉斯矩阵在图论研究中占有重要地位，利用拉普拉斯谱可以估计图的连通性，直径等不变量。Zhu et al. [15] 和Gutman [16] 给出了拉普拉斯谱与基尔霍夫指数的关系。M.Chen和B.X.Chen [17] 研究了折叠超立方体的拉普拉斯谱。下面给出一些我们需要应用的结果。

引理1.1：(Zhu et al. [15] ) $K_f=N{\displaystyle {\sum }_{i=2}^N\frac{1}{{\lambda }_i}}$。

引理1.2：(Chen et al. [17] ) $Spe{c}_L\left(F{Q}_n\right)=\left\{0,1,{\left[2t+2\right]}^{{\gamma }_t},{\left[2n+2\right]}^{{\gamma }_n}|t=1,2,\cdots ,n\right\}$， ${\gamma }_t={\displaystyle {\sum }_{j=0}^n\left(\begin{array}{c}n+1\\ 2j\end{array}\right)}$， ${\gamma }_n={\displaystyle {\sum }_{j=1}^n\left(\begin{array}{c}n\\ 2j-1\end{array}\right)}$。

引理1.3：(Chandra [18] ) $T_{ij}+T_{ji}=2E{r}_{ij}$。

引理1.4：(二项式定理) ${\left(x+y\right)}^n={\displaystyle {\sum }_{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^k{y}^{n-k}}$。

2. GMFPT的一个显式解

MFPT是衡量随机游动效率的一个重要指标。MFPT越小，网络上随机游动的速率就会越高。因此它有着重要而广泛的应用，其理论表达式和数值计算一直是研究的方向之一。不同网络结构的不同拓扑性质对随机游动行为有着不同影响。在正则格网络上，MFPT已有了严格的结果 [19] ；在分形网络上，MFPT得到了精确的表达式 [4] [20] ；在超立方体网络上，MFPT的显式表达式也已得出。在此基础上我们给出折叠超立方体上GMFPT的显式解。

定理2.1：折叠超立方体的GMFPT是

${\langle T\rangle }_n=\{\begin{array}{l}\frac{\left(n+1\right)2^{n-1}}{2^n-1}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{n+1}\left(\begin{array}{c}n+1\\ n+1\end{array}\right)\right],n为奇数\\ \frac{\left(n+1\right)2^{n-1}}{2^n-1}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{n}\left(\begin{array}{c}n+1\\ n\end{array}\right)\right],n为偶数\end{array}$

证明：由定义，折叠超立方体的GMFPT为 ${\langle T\rangle }_n=\frac{1}{N\left(N-1\right)}{\displaystyle {\sum }_{i\ne j}{\displaystyle {\sum }_j^{N-1}{T}_{ij}}}$。

结合引理1.1和引理1.2中的两个等式，可以得到 ${\langle T\rangle }_n=\frac{1}{N\left(N-1\right)}2E{K}_f=\frac{2E}{N-1}{\displaystyle {\sum }_{i=2}^N\frac{1}{{\lambda }_i}}$。

利用引理1.3可知 ${\displaystyle {\sum }_{i=2}^N\frac{1}{{\lambda }_i}}=\frac{1}{2}{\displaystyle {\sum }_{t=1}^{n-1}{\displaystyle {\sum }_{j=0}^n\left(\begin{array}{c}n+1\\ 2j\end{array}\right)\left(\begin{array}{c}0\\ t+1-2j\end{array}\right)\frac{1}{t+1}}}+\frac{1}{2}{\displaystyle {\sum }_{j=1}^n\left(\begin{array}{c}n\\ 2j-1\end{array}\right)\left(\begin{array}{c}0\\ n-2j+1\end{array}\right)\frac{1}{n+1}}$。

由于 $\{\begin{array}{l}\left(\begin{array}{c}0\\ t+1-2j\end{array}\right)=1,t+1-2j=0\\ \left(\begin{array}{c}0\\ t+1-2j\end{array}\right)=0,t+1-2j\ne 0\end{array}$。

可将 ${\displaystyle {\sum }_{i=2}^N\frac{1}{{\lambda }_i}}$ 展开式的第一个多项式化为

$\frac{1}{2}{\displaystyle {\sum }_{t=1}^{n-1}{\displaystyle {\sum }_{j=0}^n\left(\begin{array}{c}n+1\\ 2j\end{array}\right)\left(\begin{array}{c}0\\ t+1-2j\end{array}\right)\frac{1}{t+1}}}=\{\begin{array}{l}\frac{1}{2}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{n-1}\left(\begin{array}{c}n+1\\ n-1\end{array}\right)\right],n为奇数\\ \frac{1}{2}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{n}\left(\begin{array}{c}n+1\\ n\end{array}\right)\right],n为偶数\end{array}$

同样的，由于 $\{\begin{array}{l}\left(\begin{array}{c}0\\ n-2j+1\end{array}\right)=1,n-2j+1=0\\ \left(\begin{array}{c}0\\ n-2j+1\end{array}\right)=0,n-2j+1\ne 0\end{array}$

可将 ${\displaystyle {\sum }_{i=2}^N\frac{1}{{\lambda }_i}}$ 展开式的第二个多项式化为

$\frac{1}{2}\underset{j=1}{\overset{n}{{\displaystyle \sum }}}\left(\begin{array}{c}n\\ 2j-1\end{array}\right)\left(\begin{array}{c}0\\ n-2j+1\end{array}\right)\frac{1}{n+1}=\{\begin{array}{l}\frac{1}{2\left(n+1\right)},n为奇数\\ 0,n为偶数\end{array}$

综合上述讨论即得证。

定理2.2： $\frac{N}{2}\le {\langle T\rangle }_n\le \frac{N}{4}\left(n+1\right)$。

证明：定理2.1中的结果可改写为 ${\langle T\rangle }_n=\frac{\left(n+1\right)2^{n-1}}{2^n-1}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{2n}\left(\begin{array}{c}n+1\\ 2n\end{array}\right)\right]$，当n为奇数时，利用 $\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n-1\\ k\end{array}\right)+\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ 有

$\begin{array}{l}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ n+1\end{array}\right)\\ =\left(\begin{array}{c}n\\ 2\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 4\end{array}\right)+\left(\begin{array}{c}n\\ 3\end{array}\right)+\cdots +\left(\begin{array}{c}n\\ n+1\end{array}\right)+\left(\begin{array}{c}n\\ n\end{array}\right)\\ =\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\cdots +\left(\begin{array}{c}n\\ n\end{array}\right)=2^n-1\end{array}$ .

当n为偶数时，利用引理1.4中的二项式定理，则有

$\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ n\end{array}\right)=\left(\begin{array}{c}n+1\\ n-1\end{array}\right)+\left(\begin{array}{c}n+1\\ n-3\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ 1\end{array}\right)=\frac{1}{2}\left(2^{n+1}-2\right)=2^n-1.$

由此可知 $\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ 2n\end{array}\right)=2^n-1$。

显然，

$\begin{array}{l}\frac{1}{n+1}\left[\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ 2n\end{array}\right)\right]\\ \le \frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{2n}\left(\begin{array}{c}n+1\\ 2n\end{array}\right)\\ \le \frac{1}{2}\left[\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ 2n\end{array}\right)\right]\end{array}$ .

因此， $2^{n-1}\le {\langle T\rangle }_n\le 2^{n-2}\left(n+1\right)$。

3. 基尔霍夫指数

由定理2.1可以很容易得到折叠超立方体的基尔霍夫指数。

定理3.1：折叠超立方体的基尔霍夫指数为

$\begin{array}{l}{K}_f\left(F{Q}_n\right)\\ =\{\begin{array}{l}{2}^{n-1}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{n-1}\left(\begin{array}{c}n+1\\ n-1\end{array}\right)+\frac{1}{n+1}\left(\begin{array}{c}n+1\\ n+1\end{array}\right)\right],n为奇数\\ 2^{n-1}\left[\frac{1}{2}\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\frac{1}{4}\left(\begin{array}{c}n+1\\ 4\end{array}\right)+\cdots +\frac{1}{n-1}\left(\begin{array}{c}n+1\\ n-1\end{array}\right)+\frac{1}{n}\left(\begin{array}{c}n+1\\ n\end{array}\right)\right],n为偶数\end{array}\end{array}$

并且 ${\lim }_{n\to \infty }{K}_f\left(F{Q}_n\right)=\frac{N^2}{4}$。

证明：与定理2.2中的讨论类似，

$\frac{2^n-1}{n+1}{2}^{n-1}\le K_f\left(F{Q}_n\right)\le \frac{2^n-1}{2}{2}^{n-1}\left(n\to \infty \right)$

$\frac{2^n-1}{2\left(n+1\right)}N\le K_f\left(F{Q}_n\right)\le \frac{2^n-1}{4}N\left(n\to \infty \right)$

$\frac{N}{4}N\le K_f\left(F{Q}_n\right)\le \frac{N}{4}N-\frac{N}{4}\left(n\to \infty \right)$

因此 ${\lim }_{n\to \infty }{K}_f\left(F{Q}_n\right)=\frac{N^2}{4}$。

基尔霍夫指数是一种基于距离的拓扑指数。其在物理，化学，图论等领域的应用引起了人们的广泛关注 [21] [22] [23]。基尔霍夫指数的计算在圈图，完全图和一些合成图上已经取得了许多结果。近年来超立方体和折叠超立方体的基尔霍夫指数研究也取得了进展 [24] [25]，关于折叠超立方体的基尔霍夫指数有如下结果。对任意的正整数n有：

1) $K_f\left(F{Q}_n\right)=2^n{\displaystyle {\sum }_{i=1}^{\frac{n}{2}}\frac{\left(\begin{array}{c}n\\ n-i\end{array}\right)+\left(\begin{array}{c}n\\ n-i-1\end{array}\right)}{4i}}$， $i=1,2,\cdots ,\frac{n}{2}$，当 $n\equiv 0\left(\mathrm{mod}2\right)$

2) $K_f\left(F{Q}_n\right)=2^n{\displaystyle {\sum }_{i=1}^{\frac{n-1}{2}}\frac{\left(\begin{array}{c}n\\ 2i-1\end{array}\right)+\left(\begin{array}{c}n\\ 2i\end{array}\right)}{4i}}+\frac{2^{n-1}}{n+1}$， $i=1,2,\cdots ,\frac{n-1}{2}$，当 $n\equiv 1\left(\mathrm{mod}2\right)$

本文运用拉普拉斯谱方法，得到了折叠超立方体的基尔霍夫指数更简单的一种表达形式。

4. 结论

本文给出了折叠超立方体上GMFPT的表达式，并且得到了GMFPT的上下界。另外还讨论了折叠超立方体的基尔霍夫指数的闭合表达式。一般地，拉普拉斯谱方法也可以用来研究加强超立方体上的随机游动，但对于GMFPT等一些参数计算的简化还需要进一步的工作。

基金项目

本文得到了中国自然科学基金(11671296)和山西省优青青年学术带头人项目支持。