ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 14 Apr 2017 21:13:55 +0200- networkx can't compute algebraic connectivityhttps://ask.sagemath.org/question/37273/networkx-cant-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?Thu, 13 Apr 2017 03:55:30 +0200https://ask.sagemath.org/question/37273/networkx-cant-compute-algebraic-connectivity/
- Answer by dan_fulea for <p>I can compute the algebraic connectivity of the complete graph on 20 vertices in a fraction of a second using</p>
<pre><code>import networkx
D = {}
for i in range(20):
D[i] = [j for j in range(20)]
G = networkx.Graph(D)
networkx.algebraic_connectivity(G)
</code></pre>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>Any reasons why it is so, and any idea on how to fix it?</p>
https://ask.sagemath.org/question/37273/networkx-cant-compute-algebraic-connectivity/?answer=37281#post-id-37281
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](https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.linalg.algebraicconnectivity.algebraic_connectivity.html)
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]
Thu, 13 Apr 2017 20:01:14 +0200https://ask.sagemath.org/question/37273/networkx-cant-compute-algebraic-connectivity/?answer=37281#post-id-37281
- Comment by k1monfared for <p>2nd version of the answer...</p>
<p>For <strong>SHORT</strong>: Use an explicit favorable <code>method=</code>, for instance...</p>
<pre><code>networkx.algebraic_connectivity( GD, method='tracemin_lu' )
</code></pre>
<p>Possible methods are listed e.g. here:</p>
<p><a href="https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.linalg.algebraicconnectivity.algebraic_connectivity.html">networkx.linalg.algebraicconnectivity.algebraic_connectivity</a></p>
<p>but not all methods run smoothly (in the given example).</p>
<p>The <strong>LOOONG</strong> story, this is an edited and extended version of the first answer, where <strong>all</strong> eigenvalues were computed <strong>in sage</strong> (not in <code>networkx</code>).
After the comment
<<em>Practically speaking, I don't want to compute all the eigenvalues, that's why I'm using networkx's implemented method.</em>>
that i fully understand and support in the meantime, had to look closer to the situation...</p>
<p>So the following worx for me now, and hopefully also for you:</p>
<pre><code>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
</code></pre>
<p>This gives:</p>
<pre><code>Algebraic connectivity = 18.0
</code></pre>
<p>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.</p>
<pre><code>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]
</code></pre>
<p>And we get:</p>
<pre><code>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
</code></pre>
<p>The best solution for me was (initially) to stay completely in sage,
and define the graph data <code>D</code> as above,
and after this compute with exactity:</p>
<pre><code>sage: EV = Graph(D).laplacian_matrix().eigenvalues(); EV.sort(); EV[1]
18
</code></pre>
<p>Two notes follow now:</p>
<p>Note: <strong>Methods</strong> that work for the given graph. I also tried:</p>
<pre><code>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
</code></pre>
<p>If we print the values, then we get <code>18.0</code>...</p>
<p>Note: Some <strong>other test graphs</strong> with a repeated highest eigenvalue, of the same kind.</p>
<pre><code>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 )
</code></pre>
<p>Then we have for instance:</p>
<pre><code>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]
</code></pre>
https://ask.sagemath.org/question/37273/networkx-cant-compute-algebraic-connectivity/?comment=37300#post-id-37300Practically speaking, I don't want to compute all the eigenvalues, that's why I'm using networkx's implemented method.Fri, 14 Apr 2017 21:13:55 +0200https://ask.sagemath.org/question/37273/networkx-cant-compute-algebraic-connectivity/?comment=37300#post-id-37300