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, save your assignment as cs380hw4_lastname.pdf
(substituting in your last name), and e-mail it to me with the
subject of "CS380 Assignment 4 Lastname". Make sure you
give me a hard-copy of your write-up for the assignment.
1.) A real-world power law
network (60 pts)
Download the file gnutella.net,
a snapshot of a Gnutella peer-to-peer file-sharing network in
the year 2000.
Compute and plot the degree distribution of the network
(using your favorite plotting software, e.g. Matlab, Excel,
etc.). You can use Pajek to calculate the degree of
each individual node (Network > Create Partition >
Degree > All). Then export the partition as a '.clu' file
by clicking on the save icon to the left of the Partitions
box on the main screen. Now you can import it into Excel or
another program and compute a histogram of it. Try plotting
it on both linear axes and log-log axes.
Compute the average shortest path (Network > Create
Vector > Distribution of Distances).
Construct an Erdos-Renyi random graph with the same number
of vertices and same average degree of each vertex
(Network>Create Random Network>Small World). Check
that the random graph you have obtained has the same number
of vertices and a similar numbers of edges as the gnutella
network. Calculate and export the degrees of all vertices.
Turn in a plot that shows the two-degree distributions
superimposed. In Matlab, you can plot two data sets together
as follows: plot(x1,y1,'r-',x2,y2,'b:'). This will
plot y1 vs. x1 as a red solid line, and y2 vs. x2 as a blue
Comment on the difference in degree distribution between
the gnutella network and the equivalent Erdos-Renyi random
graph? How does this explain the differences you observed in
average shortest path in a previous lab (or you can
recalculate the average shortest paths now)?
2.) Hierarchical clustering (40 pts)
Use Pajek to hierarchically cluster the Gnutella network.
Visualize the permuted adjacency matrix as a spy plot (see
examples on the course slides)
Visualize the dendrogram
Briefly describe what the hierarchical clustering reveals about