Ask Your Question
0

networkx can't compute algebraic connectivity

asked 2017-04-12 20:55:30 -0500

k1monfared gravatar image

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

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-04-13 13:01:14 -0500

dan_fulea gravatar image

updated 2017-07-28 13:48:28 -0500

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 more

Comments

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

k1monfared gravatar imagek1monfared ( 2017-04-14 14:13:55 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-04-12 20:55:30 -0500

Seen: 155 times

Last updated: Jul 28