Ask Your Question
0

networkx can't compute algebraic connectivity

asked 2017-04-12 20:55:30 -0500

k1monfared gravatar image

I can compute the algebraic connectivity of the complete graph on 20 vertices in a fraction of a second using

import networkx
D = {}
for i in range(20):
    D[i] = [j for j in range(20)]
G = networkx.Graph(D)
networkx.algebraic_connectivity(G)

However, in a process I generate a graph (on 20 nodes) that I ask networkx to compute its algebraic connectivity, and it keeps running for ever with no errors. Here is the graph:

import networkx

D = {0: [32, 33, 19, 5, 21, 37, 6, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 5: [32, 0, 33, 19, 37, 21, 6, 22, 38, 39, 41, 26, 42, 11, 43, 44, 28, 15, 31], 6: [0, 32, 33, 19, 5, 37, 21, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 11: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 42, 43, 28, 44, 15, 31], 15: [0, 32, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 31], 19: [0, 32, 33, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 21: [32, 0, 33, 19, 37, 5, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 22: [32, 33, 19, 5, 21, 37, 6, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 26: [0, 32, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 42, 11, 43, 28, 44, 15, 31], 28: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 42, 11, 43, 44, 15, 31], 31: [32, 0, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15], 32: [0, 33, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 31, 15], 33: [0, 32, 19, 5, 21, 37, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 37: [32, 0, 33, 19, 5, 21, 6, 22, 38, 39, 41, 26, 42, 11, 43, 28, 44, 31, 15], 38: [32, 0, 33, 19, 21, 37, 5, 6, 22, 39, 41, 26, 42, 11, 43, 28, 44, 15, 31], 39: [0, 32, 33, 19, 5, 21, 37, 6, 22, 38, 41, 26, 42, 11, 43, 28, 44, 15, 31], 41: [32, 0, 33, 19, 21, 37, 5, 38, 6, 22, 39, 26, 42, 11, 43, 28, 44, 15, 31],  42: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 11, 43, 28, 44, 15, 31], 43: [32, 0, 33, 19, 21, 37, 5, 6, 22, 38, 39, 41, 26, 42, 11, 28, 44, 15, 31], 44: [32, 0, 33, 19, 5, 21, 37, 38, 6, 22, 39, 41, 42, 26, 11, 43, 28, 15, 31]}

G = networkx.Graph(D)
networkx.algebraic_connectivity(G)

Any reasons why it is so, and any idea on how to fix it?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-04-13 13:01:14 -0500

dan_fulea gravatar image

updated 2017-04-13 13:49:30 -0500

The following worx for me:

import networkx

D = \
{ 0 : [   5, 6, 11, 15, 19, 21,     26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  5 : [0,    6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  6 : [0, 5,    11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  11: [0, 5, 6,     15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  15: [0, 5, 6, 11,     19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  19: [0, 5, 6, 11, 15,     21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  21: [0, 5, 6, 11, 15, 19,     22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  22: [   5, 6, 11, 15, 19, 21,     26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  26: [0, 5, 6, 11, 15, 19, 21, 22,     28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  28: [0, 5, 6, 11, 15, 19, 21, 22, 26,     31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  31: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28,     32, 33, 37, 38, 39, 41, 42, 43, 44] ,
  32: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31,     33, 37, 38, 39, 41, 42, 43, 44] ,
  33: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32,     37, 38, 39, 41, 42, 43, 44] ,
  37: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33,     38, 39, 41, 42, 43, 44] ,
  38: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37,     39, 41, 42, 43, 44] ,
  39: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38,     41, 42, 43, 44] ,
  41: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39,     42, 43, 44] ,
  42: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41,     43, 44] ,
  43: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42,     44] ,
  44: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43    ] }

d = len(D)

GD   = networkx.Graph( D )
GDLM = networkx.laplacian_matrix( G ).todense()
# the scipy sparse matrix access is i.m.h.o. ill,
# as it took a while to discover the method todense,
# as a step in between to access the entries (!) of a scipy matrix...
GDLM = matrix( QQ, d, d, [ GDLM[ j, k ] for k in range(d) for j in range(d) ] )

GDLMEV = GDLM.eigenvalues()
GDLMEV . sort()

print ( "The Laplacian Matrix of D is:\n%s\n\nExplicitly:\n%s\n\n"
        % ( GDLM, '\n'.join( str(row) for row in GDLM.rows() ) ) )
print "The EigenValues of the laplacian matrix GDLM of the graph GD of D are:\n%s\n" % GDLMEV
print "The Algebraic Connectivity is the second smallest EV in the above list, namely:\n%s" % GDLMEV[1]

And we get:

The Laplacian Matrix of D is:
20 x 20 dense matrix over Rational Field

Explicitly:
(18, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1)
(-1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1)
(0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 18, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19)


The EigenValues of the laplacian matrix GDLM of the graph GD of D are:
[0, 18, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20]

The Algebraic Connectivity is the second smallest EV in the above list, namely:
18

I could not convince networkx to do the job either...

The best solution is than to stay completely in sage, and define the graph data D as above, and after this:

sage: EV = Graph(D).laplacian_matrix().eigenvalues(); EV.sort(); EV[1]
18
edit flag offensive delete link more

Comments

Practically speaking, I don't want to compute all the eigenvalues, that's why I'm using networkx's implemented method.

k1monfared gravatar imagek1monfared ( 2017-04-14 14:13:55 -0500 )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

1 follower

Stats

Asked: 2017-04-12 20:55:30 -0500

Seen: 60 times

Last updated: Apr 13