2

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.

Zach Hunter
  • 1,828
  • I got the first part from this video: “https://simons.berkeley.edu/events/openlectures2014-fall-4” – Zach Hunter Jan 04 '19 at 20:08
  • How does the heat kernel equation in the title come into play in the question? – mathreadler Jan 05 '19 at 08:59
  • 1
    the first 5 minutes of the video I linked in the comments shows how this describes heat dispersion. if there's a more appropriate name, I'm all ears. – Zach Hunter Jan 05 '19 at 09:09
  • Ah ok, I did not see the link. Wow 79. That was like before C64 home computers. Must have been a big project making such computations back then. – mathreadler Jan 05 '19 at 09:40
  • Heh, I was just waiting for him to go over to electrical flows, and he did. – mathreadler Jan 05 '19 at 09:48
  • For the Max flow and Min cuts he mentions you can look into "spectral clustering" which closely related to what he talks about at the end of lecture. – mathreadler Jan 05 '19 at 20:28
  • I am not connected in cuts, I just want to evaluate $\Omega_t(G)$ through spectral methods, in accordance with the definition of $\omega_t(v)$ – Zach Hunter Jan 05 '19 at 20:34

0 Answers0