2nd version of the answer...
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
Two notes follow now:
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]