Question

Consider the following model to generate random graphs. Start with one single node. At each time step, to every node of the network either zero, one or two new nodes are connected by means of a single link with probability 𝑞0 = 0.1, 𝑞1 = 0.3 and 𝑞2 = 0.6, respectively. If at any time step no node gains a new neighbour, the algorithm stops.

Starting with one single node, what is the probability that a network with only 3 nodes is generated? Explain step by step your answer by describing all possibilities of how this could happen in each time step.

Answer 1

To determine the probability that a network with only 3 nodes is generated using the given model, let's analyze the possibilities step by step:

Step 1: At the beginning, we have one single node in the network. Since no new nodes are connected at this step, the network remains with only one node.

Step 2: In this step, we consider the three possible cases based on the given probabilities:

1. Zero new nodes: The probability of no new nodes being connected is q0 = 0.1. In this case, the network remains with only one node.

2. One new node: The probability of one new node being connected is q1 = 0.3. In this case, the network will have two nodes.

3. Two new nodes: The probability of two new nodes being connected is q2 = 0.6. In this case, the network will have three nodes.

So, there are two possibilities in Step 2: either the network remains with one node (probability q0) or it grows to two nodes (probability q1).

Step 3: We again consider the three possibilities for each case in Step 2:

1. If the network remains with one node (probability q0), it will still have only one node.

2. If the network grows to two nodes (probability q1), we have the following options: a. Zero new nodes: The probability of no new nodes being connected is q0 = 0.1. In this case, the network remains with two nodes. b. One new node: The probability of one new node being connected is q1 = 0.3. In this case, the network will have three nodes. c. Two new nodes: The probability of two new nodes being connected is q2 = 0.6. In this case, the network will have four nodes.

Again, there are two possibilities in Step 3: either the network remains with one node (probability q0), or it grows to two nodes and then either remains with two nodes (probability q0) or grows to three nodes (probability q1).

Step 4 and Beyond: We continue the same analysis for subsequent steps, considering the possibilities of each case.

Based on the given model, the algorithm stops when no new node gains a new neighbor. This means that if the network reaches three nodes at any step, it will not grow further, and the algorithm will stop.

To determine the probability of generating a network with only three nodes, we need to sum up the probabilities of all paths that lead to having exactly three nodes at any step.

Considering all possibilities and their respective probabilities, the probability of generating a network with only three nodes can be calculated as follows:

Probability = q1 + q1 * q1 * q1 + q1 * q1 * q2 + q1 * q2 + q2 * q1 * q1

= 0.3 + 0.3 * 0.3 * 0.3 + 0.3 * 0.3 * 0.6 + 0.3 * 0.6 + 0.6 * 0.3 * 0.3

= 0.3 + 0.027 + 0.054 + 0.18 + 0.054

= 0.615

Therefore, the probability of generating a network with only three nodes is 0.615 or 61.5%.