python - 使用networkx在python中修改具有两个不同群体的Erdos-Renyi随机图

Question

我想实现以下模型:

• 取 2*n 个节点。前 n 个节点代表 A 型个体，其余节点代表 B 型个体。

• 以概率 p，来自 A 的个体和来自 B 的另一个个体之间存在边缘。

我就是这样做的，但我希望它更快:

def modified_Erdos_Renyi(n,p):
    G = nx.empty_graph(2*n)
    for i in range (n):       
        for j in range(n,2*n):
            r = rd.random()
            if r<=p:
                G.add_edge(i,j)
    return G

我在networkx源码中看到有一个针对传统G_np的快速算法:

def fast_gnp_random_graph(n, p):
    G = empty_graph(n)
    G.name="fast_gnp_random_graph(%s,%s)"%(n,p)

    w = -1
    lp = math.log(1.0 - p)
    v = 1
    while v < n:
        lr = math.log(1.0 - random.random())
        w = w + 1 + int(lr/lp)
        while w >= v and v < n:
            w = w - v
            v = v + 1
        if v < n:
            G.add_edge(v, w)
    return G

如何使用修改后的模型实现该算法？

Answer 1

您尝试创建的算法是 already implemented in networkx如nx.bipartite.random_graph(m,n,p)。 m 是组 A 中的数字，n 是组 B 中的数字，p 是边缘概率。

顺便说一句 - 如果您想了解为什么 fast_gnp_random_graph 有效，我推荐 this paper I cowrote with one of the original developers of networkx 的第 2 部分.