# How to obtain the resistance distance matrix of a graph? I tried to compute resistance distance matrix of a graph g by first evaluating the Moore-Penrose inverse of the Laplacian matrix, but the result is not accurate, the entries are slightly different. I tried with the following algorithm.

L=g.laplacian_matrix()
from scipy import linalg
M=matrix(linalg.pinv(L))
R=matrix(QQ, g.order())
for i in range(g.order()):
for j in range(g.order()):
if i!=j:
R[i,j]=M[i,i]+M[j,j] -M[i,j]-M[j,i]

edit retag close merge delete

Why did you write from scipy import linalg?

I imagine that scipy does not convert the pseudo-inverse exactly. Anyhow, please specify the example of a graph on which you see the problem.

For any tree classical distance matrix and resistance distance matrices are same. But the above program is giving me slightly different values. for example instead of 3, it gives 3.002176 for all the entries. I think its because linalg.pinv(L) does not give the accurate g-inverse.

Indeed, scipy works mostly with floating point numbers (= finite precision)

Sort by » oldest newest most voted

If you want exact results, you would better use exact pseudo inverse instead of scipy

sage: g = graphs.GridGraph((3,2))
sage: L = g.laplacian_matrix()
sage: L.pseudoinverse()   # exact version
[ 83/180  17/180  -1/180 -19/180 -37/180 -43/180]
[ 17/180  83/180 -19/180  -1/180 -43/180 -37/180]
[ -1/180 -19/180  47/180  -7/180  -1/180 -19/180]
[-19/180  -1/180  -7/180  47/180 -19/180  -1/180]
[-37/180 -43/180  -1/180 -19/180  83/180  17/180]
[-43/180 -37/180 -19/180  -1/180  17/180  83/180]
sage: matrix(linalg.pinv(L))    # floating point version
[     0.461111111111111    0.09444444444444366 -0.0055555555555548185   -0.10555555555555467   -0.20555555555555652    -0.2388888888888887]
[   0.09444444444444444    0.46111111111111003   -0.10555555555555454  -0.005555555555554606   -0.23888888888889012    -0.2055555555555555]
[ -0.005555555555555647   -0.10555555555555535     0.2611111111111109   -0.03888888888888898 -0.0055555555555552305    -0.1055555555555554]
[  -0.10555555555555546  -0.005555555555555619   -0.03888888888888879    0.26111111111111107   -0.10555555555555557  -0.005555555555555813]
[   -0.2055555555555557   -0.23888888888888798  -0.005555555555556556   -0.10555555555555653     0.4611111111111124    0.09444444444444448]
[   -0.2388888888888887   -0.20555555555555471   -0.10555555555555617  -0.005555555555556528    0.09444444444444547    0.46111111111111075]


Scipy is using floating point arithmetic. It makes it fast but approximative.

more

1

Can you set my answer as valid so that the question does not appear as "not answered" anymore?

Sorry, can u please tell me how to do so? I don't see any link of that kind.