python 中两个不同种群的修正 Erdos-Renyi 随机图与 networkx

Question

我想实现以下模型：

取2*n个节点。前n个节点代表A型个体，剩下的n个节点代表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 部分。

python 中两个不同种群的修正 Erdos-Renyi 随机图与 networkx

Modified Erdos-Renyi random graph with two different population in python with networkx

python

networkx

graph-algorithm