Let $G=(V,E)$ be a graph, with node set $V$ and edge set $E$, along with a weighted adjacency matrix $W$. In this context, I'm interested by the commute-time distance between nodes of the graph. For undirected graphs, it is known to be defined as $$d(i,j) = \Gamma_{ii}+\Gamma_{jj}-2\Gamma_{ij}\tag{1}\label{1}$$ where $\Gamma$ is the pseudo-inverse of the graph laplacian $L=D-W$, where $D$ is a diagonal matrix with entries $d_i=\sum_{j=1}^n W_{ij}$.

There is also another definition: $d(i,j)=h(i,j)+h(j,i)$, where $h(i,j)$ is the average first hitting time from $i$ to $j$ and is defined as $$h(i,j)=1+\sum_{k=1}^nP_{ik}h(j,k)-P_{ij}h(i,j)\tag{2}\label{2}$$

I would like to know how to go from \eqref{2} to \eqref{1}.


1 Answer 1


I have found a nice answer here.

The random walker can get from $x_i$ to $x_j$ either directly in one step with probability $P_{ij}$, or it first goes from $x_i$ to $x_k$ ($k\ne j)$ with probability $P_{ik}$ and the expected time to get to $x_j$ is $1+M_{kj}$. Formally: \begin{align} M_{ij}&=P_{ij}+\sum_{k\ne j}P_{ij}(1+M_{ij})\\ &=1+\sum_{k=1}^n P_{ij}M_{kj}-P_{ij}M_{jj} \end{align} One can observe that $$M=E+P(M-M_d)\tag{1}\label{1}$$ where $E=11^\top$ and $M_d$ is the diagonal matrix with entries $M_{11},\dots,M_{nn}$.

First, we want to figure out $M_d$. To that end, let $\psi=\begin{pmatrix}d_1&\dots&d_n\end{pmatrix}^\top$, this is a left eigenvector of $P$: $$\psi^\top P=\psi$$ We get: \begin{align} \psi^\top M&=\psi^\top E+\psi^\top A(M-M_d)\\ &=\psi^\top E+\psi^\top(M-M_d) \end{align} Thus, we have $$\psi^\top M_d=\psi^\top E=\psi^\top 11^\top=\left(\sum_{i=1}^kd_k\right)1^\top$$ equivalently, $$d_iM_{ii}=\sum_{k=1}^nd_k$$ Hence, $$M_{ii}=\frac{1}{d_k}\sum_{k=1}^n d_k=\frac{vol(G)}{d_k}$$ Now, we assume $P$ is irreducible, then the solution $M$ to \eqref{1} is unique: Assume $M'$ is another solution: $$M'=E+P(M'-M_d)$$ then $$M-M'=P(M-M')$$ The columns on $M-M'$ are right eigenvectors of $P$ with eigenvalue $1$. But if $P$ is irreducible, the only eigenvector with eigenvalue $1$ is the all-ones vector. Therefore, $$M-M'=1u^\top$$ for some $u$. However, $diag(M)=diag(M')=M_d$. Therefore, $u=0$ and $M=M'$. Now, the mean first passage time matrix can be written as $$T=M-M_d$$ Therefore, \eqref{1} is equivalent to $$(I-P)T=E-M_d$$ $(I-P)$ is not invertible, however, the graph Laplacian is defined as $$L=(D-W)=D(I-P)$$ Hence, $$LT=DE-DM_d$$ Now, $$\Gamma L=I-\frac{1}{n}11^\top$$ So, we get \begin{align} (\Gamma L)T&=\Gamma DE-\Gamma DM_d\\ T&=\Gamma DE-\Gamma DM_d+1u^\top \end{align} for some vector $u$. $$T_{ij}=\sum_{k=1}^n\Gamma _{ik}d_k-vol(G)\Gamma _{ij}+u_j$$ because $DM_d=vol(G)I$. Since $T_{ii}=0$, we find $$u_i=-\sum_{k=1}^n\Gamma _{ik}d_k+vol(G)\Gamma_{ii}$$ And from the last equations: $$d(i,j)=T_{ij}+T_{ji}=vol(G)\left(\Gamma _{ii}+\Gamma _{jj}-2\Gamma _{ij}\right)$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .