Random Graphs and Models of Small Worlds -- Solutions (20 points)
Scoring
- 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.
1. Random Graph
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.
2. Random Proxy Graph
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.