Description
Questions 1, 2 and 3 are based on Chapter 6 on Games1
.
2 Question 1 (2 points)
In Section 6.11 (Exercises), solve Problem (3).
1https://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch06.pdf
1
3 Question 2 (4 points)
In Section 6.11 (Exercises), solve Problem (4). In part (b), you must show the precise steps
to arrive at your answers. Each part carries 2 points.
4 Question 3 (9 points)
In Section 6.11 (Exercises), solve Problem (6). You must show precise steps on how you
arrive at your answer for each part. Each part carries 3 points.
5 Programming Question (15 points)
The objective of the programming assignment is to give you a better understanding of page
rank. We have provided you two graphs with 100 nodes each. You can find the list of the
node ids and their categories in the file nodes.txt. The edges for the graphs can be found
in the files network1 edges.txt and network2 edges.txt respectively.
Apply the page rank algorithm on the graphs separately for 100 iterations. You are free
to use methods from existing libraries like NetworkX (https://networkx.github.io), SNAP
(https://snap.stanford.edu/snappy/), etc.
Now, answer the following questions based on your result of Page Rank Algorithm.
1. For a search query on category Sports, list out the top-10 nodes in decreasing order
of pagerank for network1.
2. For a search query on category Politics, list out the top-10 nodes in decreasing order
of pagerank for network2.
3. Plot a graph showing the variation in page rank value of node with id 2 for network1
over 100 iterations.
4. Plot a graph showing the variation in page rank value of node with id 2 for network2
over 100 iterations.
5. Explain the difference in the page rank of Node 2 for the two networks.
Include the answers for the questions in the pdf for the non-programming part. You need
to submit the code for page rank in Compass.
2
