Goals
In this assignment, you will use the python programming to implement variations of the classic PageRank algorithm. You will use an adjacency matrix to represent edges and compute the PageRank scores of the nodes.
PageRank
PageRank is an algorithm developed by Sergey Brin and Larry Page that built the early foundation of the Google search engine. We will use a simplified version.
The intuition behind PageRank is that the web can be represented as a graph, with links between pages as directed edges. The importance or "popularity" of a page on the web can be determined by how many other pages link to it. But should every link be treated equally? A link from a popular site like Google's homepage should be more important than a link from an unpopular blog. We want to weigh links from more important pages more than edges links from less important edges when computing the PageRank score of a page. We need PageRank values to determine other PageRank values, and since all nodes depend on each other and the graph isn't necessarily acyclic, this becomes a chicken and egg problem!
Problems
In this assignment, you will need to solve 6 problems. Please follow the instructions in the problem files.
Problem 1: 10 points
Problem 2: 10 points
Problem 3: 30 points (10 points for each subquestion)
Problem 4: 10 points
Problem 5: 20 points
Problem 6: 20 points
Debugging your program using python unit tests (nosetests)
You can use the provided unit tests to debug your code. For example, to debug the code of your solution to problem 3, type:
nosetests test3.py
If the code is correct, you will pass the unit tests.
How to submit?
Please submit problem[1-6].py (six python files) in Canvas system under “HW1 assignment”.
