Double图的撞击时间的期望值

Expected Hitting Time of Double Graphs

摘要: 令G为简单连通图，D_G为其double图，称图G的随机游走从点u首次到达点v所需步数的期望值为点u到点v的撞击时间的期望值。本文给出了D_G和G中任意两点撞击时间的期望值之间的关系。

Abstract: Let G be a simple connected graph and let D_G be its double graph. The expected hitting time from vertices u to v is the expected value of the minimum number of jumps the random walk needs from u to v. In this paper, a relation for the expected hitting time between any two vertices of D_G and G is displayed.

1. 引言

令 $G=\left(V_G,E_G\right)$ 为简单连通图。顶点v的邻域表示G中与v相邻的顶点的集合，记为 $N_G\left(v\right)$。v的度定义为 $N_G\left(v\right)$ 的元素个数，记为 $d_G\left(v\right)=\left|N_G\left(v\right)\right|$。G的邻接矩阵A(G)是如下的0~1方阵：如果u和v相邻，则它的(u, v)元为1，否则为0。D(G)为G的度对角矩阵。G的Laplacian矩阵定义为 $L\left(G\right)=D\left(G\right)-A\left(G\right)$。

对于图G而言，如果它的一个简单的随机游走满足从当前的一个顶点u以 $1/d_G\left(u\right)$ 的概率到达它的下一个邻点v，则该简单随机游走构成一个马尔可夫链。点u到点v的撞击时间的期望值定义为G的所有马尔科夫链中从点u首次到达点v所经过的步数的期望值，记为 $H_G\left(u,v\right)$。随机游走的撞击时间的期望值是一个很重要的图参数 [1] [2] 并已被广泛研究 [3] [4] [5] [6]。通常，很难从其定义中给出两个给定顶点之间的撞击时间的期望值的表达式，尤其是在复杂的网络结构的情况下。计算撞击时间的期望值的一项非凡成就归功于 [7]，他根据正则Laplacian特征值及其对应的特征向量给出了一个公式(请参见下面的引理2.1)。因此，获得正则Laplacian特征值及其对应的特征向量是计算撞击时间的期望值的最有效方法之一。但是，对于一般图要给出正则Laplacian特征值及其对应的特征向量非常困难。然后，许多研究人员试图研究一些特殊类别的图，例如参见 [8] [9] [10]。

令G是顶点集为 $V_G=\left\{v_1,v_2,\cdots ,v_n\right\}$ 的图。取G的一个复制，其对应顶点集记为 $\left\{{v^{\prime }}_1,{v^{\prime }}_2,\cdots ,{v^{\prime }}_n\right\}$，对每个i，令 ${v^{\prime }}_i$ 与 $N_G\left(v_i\right)$ 中所有点相连接，我们将所得的图称为G的double图，记为D_G，显然 $\left|V_{D_G}\right|=2\left|V_G\right|$ 和 $\left|E_{D_G}\right|=4\left|E_G\right|$。有关double图的更多性质和应用，请参考 [11] [12] [13]。本文主要结论如下：

定理1.1设G为边数为m的连通图， $V_G=\left\{v_1,v_2,\cdots ,v_n\right\}$。令D_G为G的double图， $V_{D_G}=\left\{v_1,v_2,\cdots ,v_n,{v^{\prime }}_1,{v^{\prime }}_2,\cdots ,{v^{\prime }}_n\right\}$，其中 ${v^{\prime }}_i$ 对应于 $v_i,1\le i\le n$，则

1) $H_{D_G}\left(v_i,v_j\right)=H_{D_G}\left({v^{\prime }}_i,{v^{\prime }}_j\right)=H_G\left(v_i,v_j\right)+\frac{2m}{d_G\left(v_j\right)},i,j\in \left\{1,2,\cdots ,n\right\}$ ；

2) $H_{D_G}\left(v_i,{v^{\prime }}_i\right)=H_{D_G}\left({v^{\prime }}_i,v_i\right)=\frac{4m}{d_G\left(v_i\right)},1\le i\le n$ ；

3) $H_{D_G}\left(v_i,{v^{\prime }}_j\right)=H_{D_G}\left({v^{\prime }}_i,v_j\right)=H_G\left(v_i,v_j\right)+\frac{2m}{d_G\left(v_j\right)},i,j\in \left\{1,2,\cdots ,n\right\}$。

2. 预备知识

在本节，我们给出一些基本定义和相关引理，这些结果将用于证明我们的主要结论。给定一个连通图G，G的Randi 矩阵 [14] 定义为

$R\left(G\right)=D{\left(G\right)}^{-1/2}A\left(G\right)D{\left(G\right)}^{-1/2}.$ (2.1)

设 ${\lambda }_1\ge {\lambda }_2\ge {\lambda }_3\ge \cdots \ge {\lambda }_n$ 为 $R\left(G\right)$ 的全部特征值， $x_1,x_2,\cdots ,x_n$ 为相应的两两正交的单位特征向量，则由文献 [15]， ${\lambda }_1=1,{\lambda }_2<1$ 当且仅当G是连通图。设 $U=\left(x_1,x_2,\cdots ,x_n\right)$，则U是正交矩阵，即

${\displaystyle \underset{k=1}{\overset{n}{\sum }}{x}_{ik}{x}_{jk}}={\displaystyle \underset{k=1}{\overset{n}{\sum }}{x}_{ki}{x}_{kj}}=\{\begin{array}{c}1,i=j;\\ 0,i\ne j.\end{array}$ (2.2)

设 $x_i={\left(x_{i1},x_{i2},\cdots ,x_{in}\right)}^t$，其中t表示转置，则容易得到

$x_1={\left(\sqrt{d_G\left(v_1\right)/2m},\sqrt{d_G\left(v_2\right)/2m},\cdots ,\sqrt{d_G\left(v_n\right)/2m}\right)}^t.$ (2.3)

1993年，Lovász [7] 给出了关于撞击时间的期望的公式，如下所示：

引理2.1 ( [7] )设G为具有m条边的n阶图，则对于任意 $v_i,v_j\in V_G$，

$H_G\left(v_i,v_j\right)=2m{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{1-{\lambda }_k}}\left[\frac{x_{kj}^2}{d_G\left(v_j\right)}-\frac{x_{ki}{x}_{kj}}{\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right].$

给定一个连通图G，其中 $\left|V_G\right|=n,\left|E_G\right|=m$，则 $\left|V_{D_G}\right|=2n,\left|E_{D_G}\right|=4m$，我们有

$A\left(D_G\right)=\left(\begin{array}{cc}A\left(G\right)& A\left(G\right)\\ A\left(G\right)& A\left(G\right)\end{array}\right),D\left(D_G\right)=\left(\begin{array}{cc}2D\left(G\right)& 0\\ 0& 2D\left(G\right)\end{array}\right).$

再由(2.1)得出

$\begin{array}{c}R\left(D_G\right)=D{\left(D_G\right)}^{-1/2}A\left(D_G\right)D{\left(D_G\right)}^{-1/2}\\ =\left(\begin{array}{cc}\frac{1}{\sqrt{2}}D{\left(G\right)}^{-1/2}& 0\\ 0& \frac{1}{\sqrt{2}}D{\left(G\right)}^{-1/2}\end{array}\right)\left(\begin{array}{cc}A\left(G\right)& A\left(G\right)\\ A\left(G\right)& A\left(G\right)\end{array}\right)\left(\begin{array}{cc}\frac{1}{\sqrt{2}}D{\left(G\right)}^{-1/2}& 0\\ 0& \frac{1}{\sqrt{2}}D{\left(G\right)}^{-1/2}\end{array}\right)\\ =\frac{1}{2}\left(\begin{array}{cc}R\left(G\right)& R\left(G\right)\\ R\left(G\right)& R\left(G\right)\end{array}\right)\end{array}$ (2.4)

接下来，我们求出 $R\left(D_G\right)$ 的特征值和相应的正交特征向量，如下所示：

引理2.2设G为具有m条边的n阶图， $1={\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n\ge -1$ 为 $R\left(G\right)$ 的特征值， $x_1,x_2,\cdots ,x_n$ 为相应的正交特征向量，则 $R\left(D_G\right)$ 的特征值和相应的正交特征向量如下：

1) 特征值1的重数为1及其相应的特征向量为

${\left(\sqrt{d_G\left(v_1\right)/4m},\cdots ,\sqrt{d_G\left(v_n\right)/4m},\sqrt{d_G\left(v_1\right)/4m},\cdots ,\sqrt{d_G\left(v_n\right)/4m}\right)}^t;$

2) 特征值0的重数为n及其相应的特征向量为

$\frac{1}{\sqrt{2}}\left(\begin{array}{c}{x}_i\\ -x_i\end{array}\right)$

其中 $i=1,2,\cdots ,n$。

3) ${\lambda }_k\left(k=2,3,\cdots ,n\right)$ 为 $R\left(D_G\right)$ 的特征值，其相应的特征向量为

$\frac{1}{\sqrt{2}}\left(\begin{array}{c}{x}_k\\ x_k\end{array}\right).$

证明：1) 因为 $\left|E_{D_G}\right|=4m$， $\forall v_i,{v^{\prime }}_i\subseteq V_{D_G},i=1,2,\cdots ,n$。 $d_{D_G}\left(v_i\right)=d_{D_G}\left({v^{\prime }}_i\right)=2d_G\left(v_i\right)$，则由(2.3)得出：特征值1相应的特征向量为

${\left(\sqrt{d_G\left(v_1\right)/4m},\cdots ,\sqrt{d_G\left(v_n\right)/4m},\sqrt{d_G\left(v_1\right)/4m},\cdots ,\sqrt{d_G\left(v_n\right)/4m}\right)}^t.$

2) 由(2.4)，我们有

$R\left(D_G\right)\left(\begin{array}{c}{x}_i\\ -x_i\end{array}\right)=\frac{1}{2}\left(\begin{array}{cc}R\left(G\right)& R\left(G\right)\\ R\left(G\right)& R\left(G\right)\end{array}\right)\left(\begin{array}{c}{x}_i\\ -x_i\end{array}\right)=0.$

进而，

${\left(\begin{array}{c}{x}_i\\ -x_i\end{array}\right)}^t\left(\begin{array}{c}{x}_j\\ -x_j\end{array}\right)=2x_i^t{x}_j=\{\begin{array}{c}2,i=j;\\ 0,i\ne j.\end{array}$

因此，0为 $R\left(D_G\right)$ 的特征值， $\frac{1}{\sqrt{2}}\left(\begin{array}{c}{x}_i\\ -x_i\end{array}\right),i=1,2,\cdots ,n$ 为相应的单位特征向量。

3) 由(2.4)，我们有

$R\left(D_G\right)\left(\begin{array}{c}{x}_k\\ x_k\end{array}\right)=\frac{1}{2}\left(\begin{array}{cc}R\left(G\right)& R\left(G\right)\\ R\left(G\right)& R\left(G\right)\end{array}\right)\left(\begin{array}{c}{x}_k\\ x_k\end{array}\right)={\lambda }_k\left(\begin{array}{c}{x}_k\\ x_k\end{array}\right).$

另外，

${\left(\begin{array}{c}{x}_k\\ x_k\end{array}\right)}^t\left(\begin{array}{c}{x}_j\\ x_j\end{array}\right)=2k_i^t{x}_j=\{\begin{array}{c}2,k=j;\\ 0,k\ne j.\end{array}$

因此， ${\lambda }_k$ 为 $R\left(D_G\right)$ 的特征值， $\frac{1}{\sqrt{2}}\left(\begin{array}{c}{x}_k\\ x_k\end{array}\right),k=2,3,\cdots ,n$ 为相应的单位特征向量。

3. 定理1.1的证明

在本节，我们根据引理2.1和引理2.2给出定理1.1的证明。

证明：1) 回顾： $\left|E_{D_G}\right|=4\left|E_G\right|=4m$，由引理2.1和引理2.2，我们有

$\begin{array}{c}{H}_{D_G}\left(v_i,v_j\right)=8m\left[{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{1-{\lambda }_k}}\left(\frac{x_{kj}^2}{4d_G\left(v_j\right)}-\frac{x_{ki}{x}_{kj}}{4\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right)+{\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(\frac{x_{kj}^2}{4d_G\left(v_j\right)}-\frac{x_{ki}{x}_{kj}}{4\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right)}\right]\\ =2m{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{1-{\lambda }_k}}\left(\frac{x_{kj}^2}{4d_G\left(v_j\right)}-\frac{x_{ki}{x}_{kj}}{4\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right)+\frac{2m}{d_G\left(v_j\right)}=H_G\left((v_i,v_j\right)+\frac{2m}{d_G\left(v_j\right)}\end{array}$ (3.1)

其中 $i\ne j$，由(2.2)可得(3.1)中等号成立。由D_G的对称性， ，其中 $i\ne j$。

2) 由引理2.1、引理2.2和(2.2)可得：

$H_{D_G}\left(v_i,{v^{\prime }}_i\right)=8m{\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(\frac{x_{ki}^2}{4d_G\left(v_i\right)}+\frac{x_{ki}^2}{4d_G\left(v_i\right)}\right)}=\frac{4m}{d_G\left(v_i\right)}.$

由D_G的对称性， $H_{D_G}\left({v^{\prime }}_i,v_i\right)=\frac{4m}{d_G\left(v_i\right)}$，其中 $1\le i\le n$。

3) 再由引理2.1、引理2.2和(2.2)，我们有

$\begin{array}{c}{H}_{D_G}\left(v_i,{v^{\prime }}_j\right)=8m\left[{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{1-{\lambda }_k}}\left(\frac{x_{kj}^2}{4d_G\left(v_j\right)}-\frac{x_{ki}{x}_{kj}}{4\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right)+{\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(\frac{x_{kj}^2}{4d_G\left(v_j\right)}+\frac{x_{ki}{x}_{kj}}{4\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right)}\right]\\ =2m{\displaystyle \underset{k=2}{\overset{n}{\sum }}\frac{1}{1-{\lambda }_k}}\left(\frac{x_{kj}^2}{d_G\left(v_j\right)}-\frac{x_{ki}{x}_{kj}}{\sqrt{d_G\left(v_i\right)d_G\left(v_j\right)}}\right)+\frac{2m}{d_G\left(v_j\right)}=H_G\left(v_i,v_j\right)+\frac{2m}{d_G(\; v\; j\; )}\end{array}$

其中 $i\ne j$，由D_G的对称性， $H_{D_G}\left({v^{\prime }}_i,{v^{\prime }}_j\right)=H_G\left(v_i,v_j\right)+\frac{2m}{d_G\left(v_j\right)}$，其中 $i\ne j$。

致谢

本论文在写作过程中和黄晶博士进行了有益的讨论，在此表示感谢！

基金项目

本论文由广州市基础与应用基金(项目编号：201804010102)支持。