Can you create a random graph for me?

#network #graph #datastructure #graphstructure

It is pretty straightforward to ask others to generate a random number, right? Ask your friends to create a random number from 1 to 10, and they will generate a random number in the range.

But the question is, can they create a random graph for you?

Before jumping into the question, let's think of a scenario. Suppose, you have invited hundreds of your friends, and those friends or colleagues don't know each other earlier. When you announce start of your party, wait, you will see there will have some small clusters forming, and eventually the members will move from one clusters to another, will create a random graph for you.

In case of above scenario, let's pick up 3 persons, Bob, Rob and Daniel. Let's assume that, Bob and Rob have met earlier. That mentioned about an edge with Bob and Rob. Some moments later, Bob have changed his place and moved to Daniel. On top of that, we assume at the time of the party, Rob and Daniel never met each other. Although they never met each other, there is a subtle path between them. That is the way the random graph is being formed. The following image will show you the scenario how a random graph generates in our real life.

Definition

We can define random graphs in two ways:

G(N, L): N Nodes are being connected with L randomly picked edges.

G(N, p): N nodes are being connected with each other with a probability of p.

The second definition, G(N, p) is widely used and we will describe this in the following sections.

Algorithm

def random_graph(N, p):
    graph = initialize an empty graph with isolated N nodes
    node_pairs = N * (N-1) / 2
    for every pair in node_pairs:
        random_probability = random(0,1)
        if random_probability >= p:
           graph.add_edge(pair)
    return graph