Homework 4

Write a program that takes three inputs to help build a graph: the number of nodes, the average degree, and a randomness value (call this p) between 0 and 1. The input p will reflect the fraction of edges that should be randomly rewired. For example, if you have 10 edges in your network and p=0.1, then on average 1 edge will be removed and rewired.

Your program should generate a regular undirected graph (i.e. a lattice) with the input number of nodes and the average degree. You should then randomly rewire the correct number of edges based on p. You can either choose exactly p*n*d/2 edges to randomly rewire, or you can use a random number generator to help choose if each edge should be rewired. In the latter case, there will be some variation in the number of edges that are rewired. Either method is fine.

After your graph has been generated, compute the average clustering coefficient and average shortest path length for the graph.

Your program should produce output in the following format (where you will substitute the correct values):

Number of nodes: 100
Average Degree: 3
p: 0.01
Average Clustering Coefficient: 0.65
Average Shortest Path Length: 4


You may use any programming language you like for this assignment, as long as I can run it on my mac without installing anything. If you think I may not support the language you choose, please check with me first. Perl, C++, Java, and Python will all work.

Submit a zip file or tarball that contains

* All of your source code
* A shell script, run.sh, that will run your code. Note that this will have a different format than a windows bat file, so be sure to test it on a unix-based system