Modifying Heat Kernel Equation for Graphs

92 Views Asked by At

In spectral graph theory, I am aware that the following weight recurrence:

$$ w_t(v_i) = \frac{1}{2}w_{t-1}(v_i)+\sum_{v_j \mid \exists e_{ij} }\frac{1}{2deg(v_i)} w_{t-1}(v_j) $$

Can be expressed in terms of eigen-vectors and eigenvalues of the Laplacian, $L=D-A$, nicely: $\left( W_{ii} = \frac{1}{2}, W_{ij} = \frac{1}{deg(v_i)+deg(v_j)} \right)$

$$ W^t u = \sum_{k=1}^n \lambda_i^t a_i v_i $$

For the following recursion formula, would this equation work?

$$ \omega_t(v_i) = \sum_{v_j \mid \exists e_{ij} }\frac{\omega_{t-1}(v_j)}{deg(v_i)} $$

$$ \Omega^t u = \sum_{k=1}^n (2\lambda_i-1)^t a_i v_i $$

My logic is that "$2\lambda_i$" will double the weight, and the "$-1$" will subtract off the weight that a vertex directs back onto itself. This is not for a class, my school does not offer spectral graph theory.