networkx can't compute algebraic connectivity

answered 2017-04-13 20:01:14 +0200

dan_fulea
5337 ●5 ●43 ●90

updated 2017-07-28 20:48:28 +0200

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]

edit flag offensive delete link

Comments

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

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

add a comment

networkx can't compute algebraic connectivity

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

networkx can't compute algebraic connectivity edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

networkx can't compute algebraic connectivity