3.6. Lab 5: Scale-Free Networks

Due Date: 11:59pm February 13, 2024 Labs should be submitted as a single Jupyter notebook to CourseLink Dropbox This lab counts for 4% of the final grade

3.6.1. Exercises

Complete the exercises corresponding to Exercise 4.1 – 4.3 in Chapter 4 of Think Complexity (version 2):

1. In Section 4.8 we discussed two explanations for the small world phenomenon, “weak ties” and “hubs”.

   1. Are these explanations compatible; that is, can they both be right? Which do you find more satisfying as an explanation and why?

   2. Is there data you could collect, or experiments you could perform, that would provide evidence in favour of one model over the other?

   3. Choosing among competing models is the topic of Thomas Kuhn’s essay, Objectivity, Value Judgment, and Theory Choice.

   • What criteria does Kuhn propose for choosing among competing models?

   • Do these criteria influence your opinion about the WS and BA models?

   • Are there other criteria you think should be considered?

   Please use a separate Markdown cell to respond to each part.

2. NetworkX provides a function called powerlaw_cluster_graph that implements the “Holme and Kim algorithm for growing graphs with power law degree distribution and approximate average clustering”. Read the documentation of this function and see if you can use it to generate a graph that has the same number of nodes as the Facebook dataset, the same average degree, and the same clustering coefficient. How does the degree distribution in the model compare to the actual distribution?

3. The actor collaboration data from the Barabasi and Albert paper is included in the repository for Think Complexity in a file called actor.dat.gz. The following function reads the file and builds the graph:

   import gzip
   
   def read_actor_network(filename, n=None):
       G = nx.Graph()
       with gzip.open(filename) as f:
           for i, line in enumerate(f):
               nodes = [int(x) for x in line.split()]
               G.add_edges_from(thinkcomplexity.all_pairs(nodes))
               if n and i >= n:
                   break
       return G
   

   Compute the number of actors in the graph and the average degree. Plot the PMF of degree on a log-log scale. Also plot the CDF of degree on a log-x scale, to see the general shape of the distribution, and on a log-log scale, to see whether the tail follows a power law.

   Note: The actor network is not connected, so you might want to use nx.connected_components to find connected subsets of the nodes.

3.6.2. Submission

Please submit a single Jupyter notebook which completes the above exercises, filling in Allen Downey’s Chapter 4 notebook. There are already placeholders in the notebook for most of your work.