时间戳

首页 > 解决方案 > 在 python 中使用类对象创建 Erdos-Renyi 图

python-3.x - 在 python 中使用类对象创建 Erdos-Renyi 图

问题描述

我正在从一组节点构建一个 Erdos-Renyi 图，这些节点是不同类型的类对象。该类取自 [blob 示例] ( https://pythonprogramming.net/many-blob-objects-intermediate-python-tutorial/ )

我从一个空图开始，创建红色和 blob 对象的节点，但是要拥有 Erdos-Renyi 图，我希望这些节点以概率 p 连接。对此类图使用 Networkx 语法从头开始创建它。

我在这里找到了一些类似的帖子 [完整图]（Networkx：为给定的一组节点创建完整图），但他们没有帮助我处理这个随机图。

import pygame
import random
import networkx
from matplotlib import pyplot as plt

STARTING_BLUE_BLOBS = 10
STARTING_RED_BLOBS = 3

WIDTH = 800
HEIGHT = 600
WHITE = (255, 255, 255)
BLUE = (0, 0, 255)
RED = (255, 0, 0
class Blob:
    def __init__(self, color):
        self.x = random.randrange(0, WIDTH)
        self.y = random.randrange(0, HEIGHT)
        self.size = random.randrange(4,8)
        self.color = color
def main():
       blue_blobs = dict(enumerate([Blob(BLUE) for i in 
range(STARTING_BLUE_BLOBS)]))
    red_blobs = dict(enumerate([Blob(RED) for i in range(STARTING_RED_BLOBS)]))
    Gb = nx.Graph()

    for i in range(10):
        Gb.add_node(blue_blobs[i])
    for i in range(3):
        Gb.add_node(red_blobs[i])
    Gb = nx.erdos_renyi_graph(13,0.5) 
    nx.draw(Gb, with_labels=True)
    plt.draw()
    plt.show()
if __name__ == '__main__':
    main()

我怎样才能保留我的节点并使用它们有这样一个随机图？非常感谢，

标签： python-3.xnetworkx

解决方案

来自维基百科页面Erdős–Rényi 模型：

在 G(n, p) 模型中，通过随机连接节点来构建图。每条边都包含在图中，概率 p 独立于所有其他边。

要基于预定的节点集创建 ER 图，您只需执行以下操作：

  1. 创建一个空的无向networkx.Graph.
  2. 将节点添加到图中。
  3. 迭代所有可能的边（即所有节点对）并以概率 将边添加到图中p。

这里有一些 python-ish 伪代码给你一个想法：

import random
import networkx as nx
from itertools import combinations

# probability for an edge to exist
p = 0.5

# ASSUMPTION: This array contains all desired nodes
nodes = [...]

g = nx.Graph()
g.add_nodes_from(nodes)

for u, v in combinations(g, 2):
    if random.random() < p:
        g.add_edge(u, v)

这应该使用预先确定的一组节点为您提供一个完全有效的 ER 图。请注意，这种方法对于生成海量图形并不是特别有效。

推荐阅读