---- > [!definition] Definition. ([[resistance distance in networks]]) > Let $G=(V,E,\boldsymbol W)$ be a [[simple graph|simple]] [[connected]] [[weighted network|weighted]] [[network]]. The **resistance distance** between two nodes $s$ and $t$ of $G$, denoted $d_{R}(s,t)$ or $\Omega_{st}$, is the (effective) [[resistance]] between the corresponding points of the electrical circuit obtained by replacing a given edge between nodes $i$ and $j$ with a $R_{ij}$-Ohm resistor, where $R_{ij}:=W_{ij}$. > > $d_{R}(s,t)$ admits computation via... > (Figures are from Klein, 1993.) ![[CleanShot 2025-03-07 at [email protected]|400]] ![[CleanShot 2025-03-07 at [email protected]|400]] > [!basicexample] > - If $G$ is a [[tree]], then the [[geodesic distance in networks|geodesic]] and resistance [[metric|metrics]] $d_{G}$ and $d_{R}$ on $G$ are identical. ^basic-example > [!justification] Computing $d_{R}(-, -)$ with the [[graph Laplacian]]. > > **Calculating voltage.** Let $\boldsymbol A$ be the (unweighted) [[adjacency matrix]] of $G$. Note that $\frac{A_{ij}}{R_{ij}}=W_{ij}$ where defined. Let $\boldsymbol I \in \mathbb{R}^{|V|}$ be a vector whose $i$th entry $I_{i}$ captures the external current (if any) being injected into (+) or extracted from (-) node $i$. (Note that physical constraints enforce $\sum_{i}I_{i}=0$, i.e., $\boldsymbol 1^{\top} \boldsymbol I=0$.) Let $\boldsymbol V \in \mathbb{R}^{|V|}$ be a vector whose $i$th entry $V_{i}$ captures the voltage at node $i$, measured relative to some reference potential. Kirchoff's current law at the junction $i$ implies $\sum_{j}{ A_{ij} }\underbrace{ \frac{V_{i}-V_{j}}{R_{ij}} }_{ \text{Ohm's Law} } = I_{i}.$ > With $d_{i}=\sum_{j}W_{ij}$ denoting the (weighted) degree of node $i$, this equation may also be written as $V_{i} d_{i} + \sum_{j} W_{ij }V_{j} = I_{i}$, or $\sum_{j}(\delta_{ij} d_{i} - W_{ij})V_{j} = I_{i},$ > which in [[matrix|matrix form]] is $\boldsymbol L \boldsymbol V = \boldsymbol I,$ > where $\boldsymbol L=\boldsymbol D- \boldsymbol W$ denotes the standard [[graph Laplacian]]. Because $G$ is [[connected]], $\ker \boldsymbol L=\langle \boldsymbol 1 \rangle$ and hence $\boldsymbol I \in (\ker \boldsymbol L)^{\perp}$. Now, $\boldsymbol L$ is symmetric, so $\boldsymbol I \in ( \ker \boldsymbol L)^{\perp}=(\ker \boldsymbol L^{\top} )^{\perp}=\im \boldsymbol L,$ > meaning the matrix equation REF has a solution. By standard [[least squares]] theory, the minimal-norm solution is $\boldsymbol V= \boldsymbol L^{+} \boldsymbol I,$ > where $\boldsymbol L^{+}$ denotes the [[Moore-Penrose pseudoinverse]] of $\boldsymbol L$. > > **Calculating resistances.** In general, the effective resistance between two junctions $s$ and $t$ of a circuit may be detected by injecting a $1$-Ampere 'test current' at $s$ and extracting at $t$, for then Ohm's Law specifies $R$ to be exactly the voltage drop: $V_{s}-V_{t}=\cancel{ I }^{=1}R_{\text{effective}}.$ > Now that we know $\boldsymbol V$ for any current distribution $\boldsymbol I$, this means we can compute the resistance distance $d_{R}(s,t)$ between a pair of nodes $s$ and $t$ by considering in particular $\boldsymbol I=\boldsymbol e_{s} - \boldsymbol e_{t}$. Indeed, $d_{R}(s, t)=V_{s}-V_{t}=(\boldsymbol e_{s}-\boldsymbol e_{t})^{\top} \boldsymbol V=(\boldsymbol e_{s}-\boldsymbol e_{t})^{\top} \boldsymbol L^{+} (\boldsymbol e_{s}-\boldsymbol e_{t})$ > and expanding yields the familiar formula[^1] $d_{R}(s, t)= L^{+}_{ss}+ L_{tt}^{+}-2 L^{+}_{st}.$ [^1]: Computation:$\begin{align}d_{R}(s, t) &= (\boldsymbol e_{s}-\boldsymbol e_{t})^{\top} \boldsymbol L^{+} (\boldsymbol e_{s}-\boldsymbol e_{t}) \\ & = (\boldsymbol e_{s}^{\top} -\boldsymbol e_{t}^{\top}) (\boldsymbol L^{+}_{:, s} - \boldsymbol L^{+}_{: ,t}) \\ &= \boldsymbol e_{s}^{\top} \boldsymbol L^{+}_{:, s} - \boldsymbol e_{s}^{\top} \boldsymbol L^{+}_{: ,t} - \boldsymbol e_{t}^{\top} \boldsymbol L_{:,s}^{+} + \boldsymbol e_{t}^{\top} \boldsymbol L_{:, t}^{+} \\ &= L^{+}_{ss} - L_{st}^{+} - L_{ts}^{+} + L^{+}_{tt} \end{align}$and the formula follows by symmetry of $\boldsymbol L^{+}$. ---- #### (Definition taken from Wikipedia.) (Pictures taken from the Klein Paper.) ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```