Network Metrics
In this assignment, you are required to write a program to compute several metrics you’ve learned in the class against any given network. We provided a sample network in this package (see the file net-sample.txt in the left menu) that contains a sample graph. You can use this network to run your experiments and make sure the resulting output of your program are in the required format (see below). We will grade your assignment based on a test network which is different from the sample network.
Your program should compute the following metrics for a given network and generate an output file named output.txt that must be in the following format (numbers on the same line are separated by single spaces):
• Line 1: density of the graph (rounded to 5 decimal digits) (5 pts).
• Next line: diameter of the graph (5 pts).
• Next line: number of connected components (5 pts).
• Next line: maximum degree of a node (5pts).
• Next n lines (n is the number of nodes in the graph): where line i contains the following two values about node i: node degree centrality and node closeness centrality separated by space (rounded to 5 decimal digits). For this assignment, set the edge weights to 1 for all edges. Moreover, if there is no path between two nodes, their distance should be set to 103 (40 pts).
• Next K lines (K is the number of connected components in the graph): where line i lists all nodes belonging to component i. The nodes in the same component have to be listed in increasing order, and the components have to be listed in increasing order of their first nodes (40 pts)
Figure 1: A example graph with two connected components.
For example, given the network in Figure 1, your output.txt should contain: 0.33333
2
2
2
0.33333 0.002 0.33333 0.002
1
Assignment 1, Due date: 3/18, 3:30 PM
COMP5800. UMASS, Lowell
0.33333 0.002 0.33333 0.002 0.33333 0.0015 0.33333 0.0015 0.33333 0.0015 1234
567
Important Notes
You must submit a single zip file named NAME STUDENTID.zip that contains the following three files in its root:
1. One script named compute-metrics for computing the graph metrics. You can use any programming language. However, we highly recommend Python.
2. One text file named output.txt containing the metrics computed against the input graph. This file should be produced by your compute-metrics script.
3. One text file named README.txt explaining steps to run your program.
We expect your script will be EASY to run. Specifically, if you use Python, we will run this command:
$ python compute-metrics.py net-sample.txt
If you use C++, we will run these commands:
$ g++ compute-metrics.cpp -o compute-metrics -O2 -Wall
$ ./compute-metrics net-sample.txt
Also note that:
• Thetestnetworkwillhavethesameformatastheprovidedsamplenetwork,net-sample.txt. Your program has to follow this input format.
• Your output.txt should be in the exact format as described above. Your file must have n + K + 4 lines. Do NOT omit any line. Otherwise you will receive a 0 grade. If you don’t know how to compute certain lines, use a blank line instead.
• Your Zip file must be submitted to the link available at the course homepage, otherwise it will be ignored. Do not email your files.
That’s it. Good luck with the assignment!
2