Let $L$ be a graph Laplacian. What is the meaning of the entries of its (pseudo)inverse $L^{-1}$? In other words, are there any interpretations which might help with understanding the entries of $L^{-1}$?
2
-
2$\begingroup$ There is no graph - your link is missing. $\endgroup$– joseph hFeb 6 at 2:14
-
$\begingroup$ I fixed it, thank you. $\endgroup$– ZuzaFeb 6 at 9:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I originally wanted to pose the question, but then I started investigating and found a few very helpful interpretation that haven't been collected anywhere (to my knowledge). Hence, I will write my results here for future reference:
Interpretation of the entries of $L^{-1}$:
The i'th row (or column, it's symmetric) of $L^{-1}$ represents the voltage at vertices required such that the unique electrical flow sends a total of 1 unit of flow from the i'th vertex in a way that each vertex receives $1/|V|$ units of flow.
Let the energy of a flow $f \in \mathbb{R}^E$ be $\sum_{e \in E} f_i^2$. Let the effective resistance between two vertices $u, v$ be the minimum energy requred to send a unit of flow from $u$ to $v$. The effective resistance between $u, v \in V$ is $(1_u - 1_v)^T L^{-1} (1_u - 1_v)$ where $1_i$ is the i'th canonical basis vector.
(Assume the graph is connected, degree regular, and not bipartite.) Let $s, t \in V$. Start with +1 units of "supply" in $s$ and -1 of "supply" in $t$. Do a random walk (each vertex chooses a random incident edge and pushes all of its supply to the other node). The expected amount of supply at node j (summed up over all steps) is exactly $M_{sj} - M_{tj}$ where $M := L^{-1}$ (I had to introduce M due to some MathJax+SE formatting issue).