Shuffling a large network using Python

Question

I have a large network for analysis. For instance:

import networkx as nx
import random

BA = nx.random_graphs.barabasi_albert_graph(1000000, 3)
nx.info(BA)

I have to shuffle the edges while keeping the degree distribution intact. The basic idea has been presented of Maslov . So my colleague and I wrote a shuffleNetwork function in which we work on a G network object for num times. edge is a list object.

The problem is that this feature is too slow for large networks. I tried using set or dict instead of a list for an edge object (set and dict is a hash table). However, since we also need to remove and add elements to it, the complexity of time becomes even greater.

Do you have any suggestions for further optimization of this feature?

def shuffleNetwork(G,Num):
    edges=G.edges()
    l=range(len(edges))
    for n in range(Num):
        i,j = random.sample(l, 2)
        a,b=edges[i]
        c,d=edges[j]
        if a != d and c!= b:
            if not (a,d) in edges or (d, a) in edges or (c,b) in edges or (b, c) in edges:
                edges[i]=(a,d)
                edges[j]=(c,b)
    K=nx.from_edgelist(edges)
    return K



import timeit
start = timeit.default_timer()
#Your statements here
gr = shuffleNetwork(BA, 1000)
stop = timeit.default_timer()
print stop - start 

Answer 1

nx.double_edge_swap

. , , , .

, , , , , .

nx.double_edge_swap(G,nswap=number)