[SOLVED] AMSC808N - Homework 6

Description

(5 pts) Implement the DFS to check experimentally the theoretical result for the Poisson random graph with mean degree z = p(n − 1).

• • The fraction S of vertices in the giant component is the largest solution of

S = 1 − exp(−zS);

• Let v be a randomly chosen vertex from a non-giant component. The average size of the component to which v belongs is

1

⟨s⟩=   .

1 − z + zS

Proceed as follows. Program the DFS (from scratch). Set the number of vertices n = 1000. Define a grid of values of z ranging between 0 and 4. For each z, generate r = 100 random graphs G(n,p) where p = z/(n − 1). For each graph, use the DFS to find its connected components. Calculate ⟨s(z)_⟩ and S(z). Make two figures:

• Figure 1: find numerically and plot the theoretical values S(z) versus z. Also plot the experimentally found values for S(z).
• Figure 2: plot the theoretical value for ⟨s(z)_⟩=[1−z +zS(z)]⁻¹ and the experimentally found values for ⟨s(z)_⟩.

Comment on your findings. Link files with your codes to the pdf file with your report.

2. (5 pts) Implement the BFS to obtain estimates for the average length of shortest paths in the Poisson random graph:

.                                                                         (1)

Proceed as follows. Program the BFS (from scratch). Set z = 4 so that almost all vertices belong to the giant component. For n = 2^p, p = 10,11,12,13, generate a random graph G(n,p). Randomly select r = 100 vertices, and use each of them as a seed for the BFS. Average the found path lengths and find l(n). Plot the found l(n) versus n as well as the theoretical estimate (1). Comment on your observations. Link files with your codes to the pdf file with your report.

3. (5 pts) Read Sections II.A, II.C, and II.D in Newman, Strogats, Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E, 64, 026118. Consider a random graph with a prescribed degree distribution p_k. Let v be a randomly chosen vertex from a non-giant component. Write a book report with a

detailed derivation of the formula for the average size of the component to which v belongs to:

⟨s⟩=.                                                        (2)