1. Consider an G(n,p)-type Erds-Rnyi random graph (network) constructed by randomly connecting n la- beled vertices...

 

Transcribed Image Text:

1. Consider an G(n,p)-type Erds-Rnyi random graph (network) constructed by randomly connecting n la- beled vertices (nodes). Each possible edge is included in the graph with probability p, independently from every other edge. (a) Shown below is a G(n, p)-type Erds-Rnyi random graph with n = 100. This graph has 55 edges and many connected components. Estimate the value of p used and carefully explain your reasoning. (The answer is in the sequence p = 0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005,...). (b) Let M be a random variable for the number of edges in a G(n, p)-type Erds-Rnyi random graph. The minimum possible value of M is 0. The maximum possible value of M is (2) n(n-1)/2. What is the expected number of edges E[M]? (Your answer will be a function of n and p.) (c) Sketch a graph of Var[M], the variance of M, as a function of p. What value of p maximizes Var[M]? What is the maximum possible value of Var[M]? (d) What is the probability that the edges of a G(n, p)-type Erds-Rnyi random graph will be spanning, that is, the probability that every node will have degree 1 or greater? (e) What is the probability that a G(n,p)-type Erds-Rnyi random graph will have precisely one connected component? Your answer will be a function of n and p. 1. Consider an G(n,p)-type Erds-Rnyi random graph (network) constructed by randomly connecting n la- beled vertices (nodes). Each possible edge is included in the graph with probability p, independently from every other edge. (a) Shown below is a G(n, p)-type Erds-Rnyi random graph with n = 100. This graph has 55 edges and many connected components. Estimate the value of p used and carefully explain your reasoning. (The answer is in the sequence p = 0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005,...). (b) Let M be a random variable for the number of edges in a G(n, p)-type Erds-Rnyi random graph. The minimum possible value of M is 0. The maximum possible value of M is (2) n(n-1)/2. What is the expected number of edges E[M]? (Your answer will be a function of n and p.) (c) Sketch a graph of Var[M], the variance of M, as a function of p. What value of p maximizes Var[M]? What is the maximum possible value of Var[M]? (d) What is the probability that the edges of a G(n, p)-type Erds-Rnyi random graph will be spanning, that is, the probability that every node will have degree 1 or greater? (e) What is the probability that a G(n,p)-type Erds-Rnyi random graph will have precisely one connected component? Your answer will be a function of n and p.