0
$\begingroup$

I'm trying to refresh my memory on diffusion kernels, and am reading this paper. I don't understand the derivation of equation 11 on page 3.

EDIT: I don't understand how the two equations:

  1. $Z_i(t+1)=Z_i(t)+\alpha\sum_j \left[Z_j(t)-Z_i(t)\right]$
  2. $Z(t)=\left(1+\alpha H\right)^tZ(0)$

are equivalent. I actually thought I had proven them unequal (false proof included below for posterity) but Didier pointed out I made a mistake and I'm really interested in the more general question anyway.


They define $Z_i(t+1)=Z_i(t)+\alpha\sum_j \left[Z_j(t)-Z_i(t)\right]$. One property graph-invariant property of this is that if all $Z_k$ are equal, $Z_k(t+1)=Z_k(t)$.

Now it claims $Z(t)=\left(1+\alpha H\right)^tZ(0)$. I don't see how this maintains my observation, i.e. for some matrices $H$ it seems that $Z_i(t+1)\not=Z_i(t)$ even if all $Z_i(0)$ are equal.

I tried this out with a simple (directed) graph: $V=\{a,b,c\}$, $E=\left\{(a,b),(a,c),(c,b)\right\}$. From their definition, I think

$ H=\left( \begin{array}{ccc} -2 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & -1 \end{array} \right) $

Setting $Z(0)=(\begin{array}{ccc}1 & 1 & 1\end{array})^T$ I get that $Z(1)=(\begin{array}{ccc}3 & 0 & 2\end{array})^T$ using the definition of Z involving H, but $(\begin{array}{ccc}1 & 1 & 1\end{array})^T$ with the summation version.

Can anyone help me figure out what's going on?

  • 0
    $(1+\alpha H)(1,1,1)^T$ is $(1,1,1)^T$, not $(3,0,2)^T$.2012-01-29
  • 0
    Are you sure about your title? I see no diffusion nor any stochastic process here.2012-01-29
  • 0
    @DidierPiau: The task is to model diffusion in a graph as a stochastic process - certainly open to better names if you know of any. I may have made an error in my calculation, I'll double check. I guess the more important problem I'd like answered is "why are these two formulae equivalent". I'll rework the question.2012-01-29
  • 0
    As I said, there is no trace whatsoever of a diffusion or a stochastic process in your question. These might enter your motivations for asking the question but, as the question stands, its title is misleading.2012-01-29
  • 0
    @DidierPiau: If you think "Basic linear algebra question" or whatever will attract a better audience, please do edit the title.2012-01-29

1 Answers 1

1

Hint: Start by showing that equation 1. is the same as $Z(t+1)=(1+\alpha H) Z(t)$.

From the definition of the matrix $H$, we find that the $i$th coordinate of the vector $(1+\alpha H) Z(t)$ is $$\begin{eqnarray*}Z_i(t)+\alpha\sum_j H_{ji} Z_j(t)&=&Z_i(t)+\alpha\sum_{j\sim i} Z_j(t)-\alpha d_i Z_i(t)\\ &=&Z_i(t)+\alpha\sum_{j\sim i} [Z_j(t)- Z_i(t)]. \end{eqnarray*}$$

  • 0
    I almost have it but I get an extra term. Can you see what I'm doing wrong? http://mathbin.net/883072012-01-31
  • 0
    @Xodarap I think that they mean the identity matrix for "$1$". Unfortunate notation, I agree...2012-01-31
  • 0
    Haha wow... all that because I didn't understand the notation. Live and learn.2012-02-01