Effective graph resistance

I've mentioned the Moore-Penrose pseudoinverse of a matrix a few times, most recently last week. This post will give an application of the pseudoinverse: computing effective graph resistance.

Given a graphG, imagine replacing each edge with a one Ohm resistor. The effective resistance between two nodes inG is the electrical resistance between those the two nodes.

Calculating graph resistance requires inverting the graph Laplacian, but the graph Laplacian isn't invertible. We'll resolve this paradox shortly, but in the mean time this sounds like a job for the pseudoinverse, and indeed it is.

The graph Laplacian of a graphGis the matrix L=D-AwhereDis thediagonal matrix whoseentries are the degrees of each node andA is the adjacency matrix. The vector of all 1's

1 = (1, 1, 1, ..., 1)

is in the null space ofL but ifG is connected then the null space is one dimensional. More generally, the dimension of the null space equals the number of components inG.

Calculating graph resistance requires solving the linear system

Lw = v

wherev andw are orthogonal to1. If the graphG is connected then the system has a unique solution. The graph Laplacian L is not invertable over the entire space, but it is invertable in the orthogonal complement to the null space.

The Moore-Penrose pseudoinverseL⁺ gives the graph resistance matrix. The graph resistance between two nodes a and b is given by

R_ab = (e_a - e_b)^T L⁺ (e_a - e_b)

where e_i is is the vector that has all zero entries except for a 1 in theith slot.

For more on graph resistance see Effective graph resistance by Wendy Ellens et al.

More spectral graph theory posts

• Measuing graph connectivity with eigenvalues
• Adding an edge increases eigenvalues
• Can you hear the shape of a network?

The post Effective graph resistance first appeared on John D. Cook.