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, which is described by this function.

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 1

That NetworkX function has to work with a digraph, so it's using the brute force algorithm of computing V*(V-1) flows. Since you have an undirected graph, you can instead compute the Gomory--Hu tree in V-1 flows and then use the tree structure to determine min cuts quickly (actually, you can compute the average node connectivity from the G--H tree in linear or maybe linearithmic time, but I expect that quadratic will probably be fine).

(Shameless plug: since you're working with planar graphs with unit capacities, if you're desperate for speed, you could implement my and Philip Klein's linear-time max flow algorithm, but I expect that the usual algorithms will be roughly linear-time in practice.)