Ask Your Question
1

How to obtain the resistance distance matrix of a graph?

asked 2017-07-17 23:32:29 -0600

Deepak Sarma gravatar image

updated 2017-07-18 02:36:26 -0600

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 flag offensive close merge delete

Comments

What do you mean by "not accurate"?

vdelecroix gravatar imagevdelecroix ( 2017-07-18 02:37:10 -0600 )edit

Why did you write from scipy import linalg?

vdelecroix gravatar imagevdelecroix ( 2017-07-18 02:37:35 -0600 )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.

Dima gravatar imageDima ( 2017-07-18 02:45:35 -0600 )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.

Deepak Sarma gravatar imageDeepak Sarma ( 2017-07-18 08:43:36 -0600 )edit

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

vdelecroix gravatar imagevdelecroix ( 2017-07-18 09:00:43 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-07-18 09:06:37 -0600

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.

edit flag offensive delete link more

Comments

Thank you very much, its working.

Deepak Sarma gravatar imageDeepak Sarma ( 2017-07-18 22:48:04 -0600 )edit
1

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

vdelecroix gravatar imagevdelecroix ( 2017-07-19 04:12:34 -0600 )edit

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

Deepak Sarma gravatar imageDeepak Sarma ( 2017-08-08 00:20:01 -0600 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2017-07-17 23:32:29 -0600

Seen: 63 times

Last updated: Jul 18