Python: how to compute a fast measure of robustness on a network?
Question: I am working with a regular `NxN` network, and I need to determine a measure
of its robustness (namely, the ability to withstand failures). To do this, I
am using the [average node
connectivity](https://en.wikipedia.org/wiki/Connectivity_\(graph_theory\)),
which is described by [this
function](https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.connectivity.connectivity.average_node_connectivity.html#networkx.algorithms.connectivity.connectivity.average_node_connectivity).

However, this calculation is proving extremely slow and computationally
demanding, as you can see below. I am supposed to run the script below
`60,000` times, so time is a very crucial factor. For this reason I am willing
to reduce the size of the network, but I want to find the best compromise
between network size and computational demand.

**My question:**

**Is there a faster way to come up with the same result? Or is there another
measure you suggest in order to avoid long computations?**

The script and the timings:

    
    
    '''
    Timing the average node connectivity function
    '''
    
    from __future__ import division
    import networkx as nx
    import time
    
    #Lattice network
    N=10 #This can be 10, 20, 30, ...
    G=nx.grid_2d_graph(N,N)
    pos = dict( (n, n) for n in G.nodes() )
    labels = dict( ((i, j), i + (N-1-j) * N ) for i, j in G.nodes() )
    nx.relabel_nodes(G,labels,False)
    inds=labels.keys()
    vals=labels.values()
    inds.sort()
    vals.sort()
    pos2=dict(zip(vals,inds))
    
    start_time = time.clock()
    conn=nx.average_node_connectivity(G)
    print('N: '+str(N))
    print('Avg node conn: '+str(round(conn, 3)))
    print("--- %s seconds ---" % (time.clock() - start_time))
    

The first two timings:

    
    
    N: 10
    Avg node conn: 3.328
    --- 6.80954619325 seconds --- #This must be multiplied by 60,000
    
    N: 20
    Avg node conn: 3.636
    --- 531.969059161 seconds --- #This must be multiplied by 60,000
    


Answer: The average node connectivity calculated here is the average of local node
connectivity over all **pairs** of nodes of G. So this function will go over
all possible pairs which makes it so slow. One suggestion would be to leave
the size of your network as you want it but then randomly sample from all
possible pairs of nodes and compute a connectivity estimate based on that
sample.

