- 1 point for questions 1-8 and 2 points for question 9
- 10 points in section 1, 10 points in section 2

In this homework, you will extend your work from the previous homework and generate random graphs using some properties of the real graph you created/used last time.

Choose one of the networks you created with Lost Circles, the Wikipedia code, or the Twitter notebook in the prior homeworks, which we'll call **Yg**, and use NetworkX to create a random graph (i.e., an Erdos-Renyi graph), we'll call **ER**, using the same number of nodes and approximately the same number of edges as your **Yg** graph.

What value of

*p*did you use to construct your**ER**graph?**Solution:***p*should be equal to the density of your**Yg**graph.

Provide a visualization of this

**ER**and your**Yg**graph.**Solution:**You should notice the**ER**graph looks much more like a ball with few communities or separate structures than your**Yg**graph. In class, we discussed this difference's source as being a lack of heterogeneous mixing in an**ER**graph.

How many nodes are in

**ER**?**Solution:***n*should be the same number of nodes as your**Yg**graph.

How many edges are in

**ER**and in**Yg**?**Solution:**Edge count should be approximately*p x n(n-1)/2*, where*n*is taken from the previous answer.

What are the densities of

**ER**and**Yg**?**Solution:**These densities should be equal or very close.

What are the average local clustering coefficients of

**ER**and**Yg**?**Solution:**For**ER**, the average local clustering coefficient should be the nearly the same as the density.**Yg**can vary much more.

What are the diameters of the largest connected components in ER and Yg?

**Solution:**Both should have relatively low diameters, especially with respect to*n*(on the order of*log(n)*).

Construct a histogram for the degree distributions in both

**ER**and**Yg**.**Solution:**The histogram for**ER**should be centered on*p(n-1)*and be approximately normally distributed around that mean with no high-degree nodes. For**Yg**, we should see more high-degree nodes. For real-world graphs, we discussed how their degree distributions should look linear in a log-log graph, but I don't expect you to plot the histograms in log-log space.

Describe your observations about the differences and similarities between these two graphs.

**Solution:**Potential differences could include differences in local clustering, structural/community differences in the visualization, presence of high-degree nodes in the real-world graph that aren't in the**ER**graph, etc.

With the **Yg** network you chose above, create a Watts Strogatz network with the same number of nodes, which we'll call **WS**, to approximate your graph.

What value of

*d*did you use to construct your**WS**graph?**Solution:***d*should be an even value that's approximately equal to the average degree in your**Yg**graph.

Provide a visualization of this

**WS**and your**Yg**graph.**Solution:**This visualization will likely look more like the**ER**graph than your**Yg**graph.

How many nodes are in

**WS**?**Solution:**Should be the same as your**Yg**graph and**ER**graph above.

How many edges are in

**WS**and in**Yg**?**Solution:**Edge count for**WS**should be approximately*n x d/2*.

What are the densities of

**WS**and**Yg**?**Solution:**The**WS**graph should have a relatively low density, close to that of**Yg**and**ER**.

What are the average local clustering coefficients of

**WS**and**Yg**?**Solution:**Both graphs should have higher local clustering coefficients than the**ER**graph.

What are the diameters of

**WS**and**Yg**?**Solution:**Both graphs should similarly have low diameters (e.g., log(n)).

Construct a histogram for the degree distributions in both

**WS**and**Yg**.**Solution:**The histogram for**WS**should have a very high peak around*d*with limited spreading (based on the*p*value you used).

Describe your observations about the differences and similarities between these two graphs.

**Solution:**Likely similar to this question in the previous section, but with notes about**WS**having a low density and higher clustering than the**ER**graph.