# networkx can't compute algebraic connectivity

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

Sort by ยป oldest newest most voted

For SHORT: Use an explicit favorable method=, for instance...

networkx.algebraic_connectivity( GD, method='tracemin_lu' )


Possible methods are listed e.g. here:

networkx.linalg.algebraicconnectivity.algebraic_connectivity

but not all methods run smoothly (in the given example).

The LOOONG story, this is an edited and extended version of the first answer, where all eigenvalues were computed in sage (not in networkx). After the comment <Practically speaking, I don't want to compute all the eigenvalues, that's why I'm using networkx's implemented method.> that i fully understand and support in the meantime, had to look closer to the situation...

So the following worx for me now, and hopefully also for you:

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    ] }

GD   = networkx.Graph( D )
conn = networkx.algebraic_connectivity( GD, method='tracemin_lu' )
print "Algebraic connectivity = %s" % conn


This gives:

Algebraic connectivity = 18.0


and is in concordance with the computation of the full spectrum of the matrix associated to the graph. Here come complementary computations that explain place of the above $18$ in the spectrum of the laplacian matrix.

d = len(D)
GDLM = networkx.laplacian_matrix( GD ).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


The best solution for me was (initially) to stay completely in sage, and define the graph data D as above, and after this compute with exactity:

sage: EV = Graph(D).laplacian_matrix().eigenvalues(); EV.sort(); EV[1]
18


Note: Methods that work for the given graph. I also tried:

sage: networkx.algebraic_connectivity( GD, method='tracemin_chol' )
---------------------------------------------------------------------------
NetworkXError                             Traceback (most recent call last)
:::::::::::::::::::::::::::::::::::::::::::::::::: many traceback error lines
NetworkXError: Cholesky solver unavailable.

sage: networkx.algebraic_connectivity( GD, method='lanczos' )
17.999999999999996

sage: networkx.algebraic_connectivity( GD, method='lobpcg' )
18.0

sage: networkx.algebraic_connectivity( GD, method='tracemin_lu' )
18.000000000000004


If we print the values, then we get 18.0...

Note: Some other test graphs with a repeated highest eigenvalue, of the same kind.

def testGraph( V, K ):
"""use V vertices,
the first K vertices are not connected to themselves,
but else all connections (not to self) are allowed.
"""
D = {}
R = [1..V]
X = [1..K]
for r in R:
D[r] = [ s
for s in R
if  s != r and ( r not in X or s not in X ) ]
return networkx.Graph( D )

def getInfo( GD, showLaplaceMatrix=False ):
"""provide information for the graph GD,
which is e.g. constructed by the above routine testGraph
"""
d = len( GD.nodes() )

GDLM = networkx.laplacian_matrix( GD ).todense()
GDLM = matrix( QQ, d, d, [ GDLM[ j, k ] for k in range(d) for j in range(d) ] )
GDLMEV = GDLM.eigenvalues()
GDLMEV . sort()
if showLaplaceMatrix:
print GDLM
for method in ( 'tracemin_lu', 'lanczos', 'lobpcg' ):
conn = networkx.algebraic_connectivity( GD, method=method )
print "networkx :: Algebraic connectivity = %s (%s)" % ( conn, method )
print "eigenvalues: %s" % ( GDLMEV )


Then we have for instance:

sage: getInfo( testGraph( 6,2 ), True )
[ 4  0 -1 -1 -1 -1]
[ 0  4 -1 -1 -1 -1]
[-1 -1  5 -1 -1 -1]
[-1 -1 -1  5 -1 -1]
[-1 -1 -1 -1  5 -1]
[-1 -1 -1 -1 -1  5]
networkx :: Algebraic connectivity = 4.0 (tracemin_lu)
networkx :: Algebraic connectivity = 4.0 (lanczos)
networkx :: Algebraic connectivity = 4.0 (lobpcg)
eigenvalues: [0, 4, 6, 6, 6, 6]

sage: getInfo( testGraph( 8,3 ), True )
[ 5  0  0 -1 -1 -1 -1 -1]
[ 0  5  0 -1 -1 -1 -1 -1]
[ 0  0  5 -1 -1 -1 -1 -1]
[-1 -1 -1  7 -1 -1 -1 -1]
[-1 -1 -1 -1  7 -1 -1 -1]
[-1 -1 -1 -1 -1  7 -1 -1]
[-1 -1 -1 -1 -1 -1  7 -1]
[-1 -1 -1 -1 -1 -1 -1  7]
networkx :: Algebraic connectivity = 5.0 (tracemin_lu)
networkx :: Algebraic connectivity = 5.0 (lanczos)
networkx :: Algebraic connectivity = 5.0 (lobpcg)
eigenvalues: [0, 5, 5, 8, 8, 8, 8, 8]

sage: getInfo( testGraph( 23,3 ) )
networkx :: Algebraic connectivity = 20.0 (tracemin_lu)
networkx :: Algebraic connectivity = 20.0 (lanczos)
networkx :: Algebraic connectivity = 20.0 (lobpcg)
eigenvalues: [0, 20, 20, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23]

sage: getInfo( testGraph( 20, 8 ) )
networkx :: Algebraic connectivity = 12.0 (tracemin_lu)
networkx :: Algebraic connectivity = 12.0 (lanczos)
networkx :: Algebraic connectivity = 12.0 (lobpcg)
eigenvalues: [0, 12, 12, 12, 12, 12, 12, 12, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20]

more

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

( 2017-04-14 21:13:55 +0100 )edit