Effective Resistance from a Laplacian

Theory of Effective Resistance

Let G = (V, E) be an undirected graph with edge conductances c_(uv) > 0. The graph Laplacian is a symmetric matrix L where:

• L_(uu) = \sum_(v ~ u) c_(uv)
• L_(uv) = -c_(uv) if (u, v) ∈ E
• L_(uv) = 0 otherwise

By injecting 1 unit of current at a source node s and removing it at a target node t, we can find the node potentials v by solving L v = b, where b_s = 1, b_t = -1, and b_i = 0 otherwise. Since L is singular (its rows sum to zero), we pin the potential of the target node to zero (ground it, v_t = 0), and solve for the remaining potentials in its connected component. The potential at the source node, v_s, is exactly the effective resistance between s and t. The energy dissipated as heat is \sum_((u,v) ∈ E) c_(uv) (v_u - v_v)², which matches v_s.

Worked Example

Consider a Path graph with 4 vertices: 0-1, 1-2, 2-3, and conductance c=1 for each edge. Let's find the effective resistance between Source 0 and Target 3.

The Laplacian L is:

1 -1  0  0 -1  2 -1  0 0 -1  2 -1 0  0 -1  1

Grounding target 3 (v_3 = 0) leaves the reduced system for vertices 0, 1, 2:

[  1 -1  0 ] [ v0 ]   [ 1 ] [ -1  2 -1 ] [ v1 ] = [ 0 ] [  0 -1  2 ] [ v2 ]   [ 0 ]

1. From row 3: -v_1 + 2v_2 = 0 ⇒ v_1 = 2v_2
2. From row 2: -v_0 + 2v_1 - v_2 = 0 ⇒ v_0 = 2v_1 - v_2 = 4v_2 - v_2 = 3v_2
3. From row 1: v_0 - v_1 = 1 ⇒ 3v_2 - 2v_2 = 1 ⇒ v_2 = 1

Substituting back gives v_1 = 2 and v_0 = 3. The effective resistance is R = v_0 = 3.0. The total dissipated power is 1·(3-2)² + 1·(2-1)² + 1·(1-0)² = 1+1+1 = 3.0, verifying the certificate.

Interactive Experiment

You can test various graph topologies, conductances, and terminal choices in the interactive effective resistance module.

1. Select the Graph topology and Conductance from the available controls.
2. Choose a Source node to inject current into, and a Target node to ground.
3. Observe the resulting Resistance, Dissipated power, and node potentials in the Results panel.
4. View the computed edge currents in the interactive Canvas visualization.

Limitations

This implementation solves the exact linear system for 4 vertices. For large graphs, direct inversion is computationally intractable, and iterative solvers or approximate methods like Laplacian solvers based on spanning trees or low-stretch spanning trees are used in practice.

References

The primary reference for effective resistance, graph Laplacians, and their algebraic properties used in this module is the following lecture notes:

• Spielman, D. A. (2012). Spectral and Algebraic Graph Theory.
  https://www.cs.yale.edu/homes/spielman/561/2012/lect08-12.pdf