使用 Python 洗牌大型网络

Question

我要分析一个大网络。例如：

import networkx as nx
import random

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

我必须在保持度数分布不变的情况下打乱边缘。 Maslov介绍了基本思想。因此，我和我的同事编写了一个 shuffleNetwork 函数，其中我们在网络对象 G 上工作了 num 次。 edges 是一个列表对象。

问题是此函数对于大型网络运行速度太慢。我尝试对边缘对象使用 set 或 dict 而不是 list （set 和 dict 是散列table)。但是，由于我们还需要对其进行删除和添加元素，时间复杂度变得更大。

您对进一步优化此功能有什么建议吗？

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

文档是 here。它看起来完全符合您的要求，但修改了图形。

我不确定它是否会解决速度问题，但它确实避免了生成列表，所以我认为它会比你现有的更好。

你可以用 nx.double_edge_swap(G,nswap=number)

来称呼它

使用 Python 洗牌大型网络

Shuffling a large network using Python

python

list

hash

networkx

shuffle