Skip to main content
Engineering LibreTexts

2.6: Generating ER graphs

  • Page ID
    46581
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    chap02-4.png
    Figure \(\PageIndex{1}\): An ER graph with n=10 and p=0.3.

    The ER graph G(n, p) contains n nodes, and each pair of nodes is connected by an edge with probability p. Generating an ER graph is similar to generating a complete graph.

    The following generator function enumerates all possible edges and chooses which ones should be added to the graph:

    def random_pairs(nodes, p): 
        for edge in all_pairs(nodes): 
            if flip(p): 
                yield edge
    

    random_pairs uses flip:

    def flip(p): 
        return np.random.random() < p
    

    This is the first example we’re seen that uses NumPy. Following convention, I import numpy as np. NumPy provides a module named random, which provides a method named random, which returns a number between 0 and 1, uniformly distributed.

    So flip returns True with the given probability, p, and False with the complementary probability, 1-p.

    Finally, make_random_graph generates and returns the ER graph G(n, p):

    def make_random_graph(n, p): 
        G = nx.Graph() 
        nodes = range(n) 
        G.add_nodes_from(nodes) 
        G.add_edges_from(random_pairs(nodes, p)) 
        return G
    

    make_random_graph is almost identical to make_complete_graph; the only difference is that it uses random_pairs instead of all_pairs.

    Here’s an example with p=0.3:

    random_graph = make_random_graph(10, 0.3)
    

    Figure \(\PageIndex{1}\) shows the result. This graph turns out to be connected; in fact, most ER graphs with n=10 and p=0.3 are connected. In the next section, we’ll see how many.


    This page titled 2.6: Generating ER graphs is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?