1

I am building an Erdos-Renyi graph from a set of nodes, which are class objects of different types. The class is taken from [blob example] (https://pythonprogramming.net/many-blob-objects-intermediate-python-tutorial/)

I start with an empty graph, create nodes that are the red and blob objects, but to have an Erdos-Renyi graph, I want these nodes to be connected with probability p. Using the Networkx syntax for such a graph creates it from scratch.

I found some similar posts here [complete graph] (Networkx: Creating a complete graph for a given set of nodes), but they did not help me with this random graph.

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()

How can I keep my nodes and have such a random graph using them? Thank you very much,

user710
  • 161
  • 2
  • 12

1 Answers1

1

From the the Wikipedia page Erdős–Rényi model:

In the G(n, p) model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability p independent from every other edge.

To create an ER graph based on a predetermined set of nodes, you simply need to do the following:

  1. Create an empty undirected networkx.Graph.
  2. Add the nodes to the graph.
  3. Iterate over all possible edges (i.e. all pairs of nodes) and add the edge to the graph with probability p.

Here's some python-ish pseudocode to give you an idea:

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)

This should give you a perfectly valid ER graph using a predetermined set of nodes. Note, that this method won't be particularly efficient for generating massive graphs.

jakee
  • 18,486
  • 3
  • 37
  • 42
  • Thank you so much for the response. I was actually having more issues when defining my nodes as objects and wanted to change an attribute of an object and was expecting to see the node attribute changes as well. I have just ran into this: https://stackoverflow.com/questions/48543460/how-to-use-user-defined-class-object-as-a-networkx-node which tremendously helped me deal with my node objects well and could easily modify attributes. – user710 Jan 24 '19 at 17:38
  • A question. I defined a function with your code which returns g as G. If I change node colors of G and draw the graphs before and after change, the two graphs should look the same, right? `G = Erdos() nx.draw(G, node_color="red") plt.show() nx.draw(G, node_color="green") plt.show()` I see the second graph looks a bit different. Logically, calling G again and again should not connects edges randomly again, is that right? I think I need to investigate all the nodes' degrees to make sure they're the same, but I am wondering why they are not depicted totally the same. – user710 Jan 24 '19 at 17:50
  • I just actually noticed they have different edges!, and I do not know what I am doing wrongly. – user710 Jan 24 '19 at 17:58