3.5. Lab 4: Small World Graphs

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

3.5.1. Exercises

There are a few short exercises embedded in the Chapter 3 notebook. Complete these in-place.

Then, complete the exercises corresponding to Exercise 3.1 – 3.6 in Chapter 3 of Think Complexity (version 2):

1. In a ring lattice, every node has the same number of neighbors. The number of neighbors is called the degree of the node, and a graph where all nodes have the same degree is called a regular graph.

   All ring lattices are regular, but not all regular graphs are ring lattices. In particular, if \(k\) is odd, we can’t construct a ring lattice, but we might be able to construct a regular graph.

   Write a function called make_regular_graph that takes \(n\) and \(k\) and returns a regular graph that contains \(n\) nodes, where every node has \(k\) neighbors. If it’s not possible to make a regular graph with the given values of \(n\) and \(k\), the function should raise a ValueError.

2. Allen Downey’s implementation of reachable_nodes_bfs is efficient in the sense that it is in \(O(n + m)\), but it incurs a lot of overhead adding nodes to the queue and removing them. NetworkX provides a simple, fast implementation of BFS, available from the NetworkX repository on GitHub at https://github.com/networkx/networkx/blob/master/networkx/algorithms/components/connected.py.

   Here is a version that Downey modified to return a set of nodes:

   def plain_bfs(G, start):
       seen = set()
       nextlevel = {start}
       while nextlevel:
           thislevel = nextlevel
           nextlevel = set()
           for v in thislevel:
               if v not in seen:
                   seen.add(v)
                   nextlevel.update(G[v])
       return seen
   

   Compare this function to reachable_nodes_bfs and see which is faster. Then see if you can modify this function to implement a faster version of shortest_path_dijkstra.

3. The following implementation of a BFS contains two performance errors. What are they? What is the actual order of growth for this algorithm?

   def bfs(G, start):
       visited = set()
       queue = [start]
       while len(queue):
           curr_node = queue.pop(0)    # Dequeue
           visited.add(curr_node)
   
       # Enqueue non-visited and non-enqueued children
       queue.extend(c for c in G[curr_node]
                    if c not in visited and c not in queue)
   return visited
   

4. In Section 3.10, Downey claimed that Dijkstra’s algorithm does not work unless it uses BFS. Write a version of shortest_path_dijkstra that uses DFS and test it on a few examples to see what goes wrong.

5. (BONUS) A natural question about the Watts and Strogatz paper is whether the small world phenomenon is specific to their generative model or whether other similar models yield the same qualitative result (high clustering and low path lengths).

   To answer this question, choose a variation of the Watts and Strogatz model and repeat the experiment. There are two kinds of variation you might consider:

   • Instead of starting with a regular graph, start with another graph with high clustering. For example, you could put nodes at random locations in a 2-D space and connect each node to its nearest k neighbors.

   • Experiment with different kinds of rewiring.

   If a range of similar models yield similar behavior, we say that the results of the paper are robust.

6. (BONUS) Dijkstra’s algorithm solves the “single source shortest path” problem, but to compute the characteristic path length of a graph, we actually want to solve the “all pairs shortest path” problem.

   Of course, one option is to run Dijkstra’s algorithm \(n\) times, once for each starting node. And for some applications, that’s probably good enough. But there are are more efficient alternatives. Find an algorithm for the all-pairs shortest path problem and implement it. See https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths.

   Compare the run time of your implementation with running Dijkstra’s algorithm n times. Which algorithm is better in theory? Which is better in practice? Which one does NetworkX use?

3.5.2. Submission

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