Ask Your Question

# 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

## Comments

What do you mean by "not accurate"?

( 2017-07-18 09:37:10 +0200 )edit

Why did you write from scipy import linalg?

( 2017-07-18 09:37:35 +0200 )edit

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.

( 2017-07-18 09:45:35 +0200 )edit

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.

( 2017-07-18 15:43:36 +0200 )edit

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

( 2017-07-18 16:00:43 +0200 )edit

## 1 Answer

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

## Comments

Thank you very much, its working.

( 2017-07-19 05:48:04 +0200 )edit
1

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

( 2017-07-19 11:12:34 +0200 )edit

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

( 2017-08-08 07:20:01 +0200 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2017-07-18 06:32:29 +0200

Seen: 249 times

Last updated: Jul 18 '17