You should submit a write-up of your assignment both in pdf form and in hardcopy.  The pdf is due by electronic submission before the due date and time.  The electronic submission timestamp is what counts for determining whether your assignment was submitted on-time.  You may turn the hardcopy printout in up to three days later, but it must be identical to the electronic submission.  You will also submit your code electronically.

To submit your assignment, place a copy of your write-up (pdf preferred) and implementation into a directory called cs380hw3_lastname (substituting in your last name), then tar and gz this directory.  Name the file cs380hw3_lastname.tar.gz.  Submit it to me by attaching it to an e-mail with the subject of "CS380 Assignment 3 Lastname".  Make sure you give me a hard-copy of your write-up for the assignment.

1.)  [14 points]  Small World Networks

[This same question was deferred from the previous assignment.  If you already answered it on the previous homework, please duplicate your answer here.]

a.)  [6 pts] Which of the following graphs has the highest clustering coefficient? (You don’t need to actually compute it!)  Justify your answer.

b.) [8 pts] We introduced two variants of the Watts/Strogatz small world model (edge rewiring and edge addition).  Which model leads to the larger clustering coefficient? The larger average path length?  Justify your answers.



2.)  [20 points]  Minimum Spanning Trees

a.)  [5 pts] Using one of the algorithms discussed in class, find a minimum spanning tree for the network below.  Describe the intuition behind that algorithm and give the MST.


b.)  [10 pts] "If G is an arbitrary connected, undirected graph with a non-negative weight on every edge, and e* is the edge with the lowest weight in G, then there is a minimum spanning tree T of G that contains the edge e*."  Is this statement true or false?  Justify your answer.

c.)  [5 pts]  Does squaring the weights of a non-negative weighted graph change the minimum spanning tree?  Why or why not?



3.)  [16 points]  Learning in Networks

Given the following network, construct a naive Bayes classifier to predict the color of a vertex based on its degree and unnormalized betweenness centrality. Discretize each of these features into either two or three bins, as appropriate.  Start by specifying a table of the training data for the classifier.  Then, specify the naive Bayes classifier by listing all prior and conditional probabilities necessary for the model and their corresponding values.  (If you can derive some of the parameters from others, than these parameters can be omitted.) 



What color would the model predict for the uncolored node (?) in the network?  Show your computations!




4.)  [50 points]  Small World Networks

Write a small world network generator that supports both Watts/Strogatz small world variants that we discussed in class.  Conduct a small scientific experiment of how the network properties change as you vary the number of vertices N, the probability p of either rewiring or adding edges, and the number of nearest neighbors k for both small world model variants.  Show how the following change:

• average localized clustering coefficient
• average path length (for this one it will probably be easiest to implement Floyd-Warshall)
• average degree centrality
• centralization
  

by plotting the ratio of their values for the small world network vs the original lattice (e.g., C(p) / C(0) and l(p) / l(0), as shown on the slides).  Your answer should include a number of 2D plots (3D is okay as well, if you'd like a challenge) and a written explanation explaining the results and comparing them for both small world model variants.