Revision history [back]
 | 1 | initial version |
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...
| | 2 | No.2 Revision |
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
| | 3 | No.3 Revision |
The 2nd version of the answer...
SHORT answer: Use an explicit favorable method=, for instance...
networkx.algebraic_connectivity( GD, method='tracemin_lu' )
LOOONG answer...
This is an edited verision of the previous answer, where all eigenvalues were computed in sage. 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, had to look closer to the situation.
So the following worx for me:me, 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 ] }
d = len(D)
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.
d = len(D)
GDLM = networkx.laplacian_matrix( G 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
I could not convince networkx to do the job either...
The best solution is than for me was (initially) to stay completely in sage, sage,
and define the graph data D as above, above,
and after this:this compute with exactity:
sage: EV = Graph(D).laplacian_matrix().eigenvalues(); EV.sort(); EV[1]
18
Some notes follow now:
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...
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]
| | 4 | No.4 Revision |
2nd version of the answer...
For SHORT answer: : 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 answer...story, an edited and extended version of the first answer...
This is an edited verision of the previous 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, support in the meantime, had to look closer to the situation.situation...
So the following worx for me, 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.graph.
Here come complementary computation that explain the above $18$.
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
Some 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 other test graphs with a repeated highest eigenvalue 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]
| | 5 | No.5 Revision |
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...
This is an edited verision of the previous 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, 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 computation that explain the above $18$.
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]
| | 6 | No.6 Revision |
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, 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 computation computations that explain place of the above $18$.$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]
