FAQs
The course staff will maintain an active FAQ as a Google document to answer your questions. Post your questions in Slack, but we will answer them in this document and send you the link.
This assignment handoutin PDF form: Project2_SimplifiedPageRank.pdf (https://ufl.instructure.com/courses/538770/files/97127669?wrap=1)
Problem Statement
In the late 90s, as the number of webpages on the internet was growing exponentially, different search engines were trying different approaches to rank the webpages. At Stanford, two computer science Ph.D. students, Sergey Brin and Larry Page, were working on the following questions: How can we trust information? Why are some webpages more important than others? Their research led to the formation of the Google search engine.
In this project, you are required to implement a simplified version of the original PageRank algorithm on which Google was built by representing the web as a graph and implementing this graph using an Adjacency List or an equivalent data structure. The PageRank algorithm is an algorithm that is used to order or rank different webpages on the internet.
Representing the Web as a Graph
Adjacency Matrix Representation
Now, for the sake of simplicity, we are explaining the project in the form of an Adjacency Matrix, M. We represent the internet in the form of |V|x|V| matrix where |V| is the total number of vertices in this graph or the total number of webpages on the internet. Each vertex, V , is a webpage on the entire internet. In the below graph, we have five vertices or webpages. Within our graph, if there is an edge from V to V (the from_page points to_page), we have the value in our adjacency matrix M = 1 and 0 otherwise.
Each webpage is thus a node in the directed graph and has incoming edges and outgoing edges. Each node has a rank, r. According to PageRank, this rank, r, is equally split among the node's outgoing links. In the below figure, the rank of node i is denoted by it, and this rank is similarly divided among node i's three outgoing edges.
Rank(i) = Rank(j)/out_degree(j) + Rank(k)/out_degree(k)
According to PageRank, this rank, r, is equal to the sum of the incoming ranks. In the above figure, the rank of node i, i = k /out_degree(k) + j /out_degree(j); Thus, the rank is based on the indegree (the number of nodes pointing to it) and the importance of an incoming node. This is important considering, let's say, you create your webpage and have a million links to other pages of importance, then you might artificially inflate your webpage's ranking if this is not the case. If, for calculating the rank, we used our links, we could have easily duped the algorithm. Therefore, the rank is only based on in-links.
Core Idea of PageRank
Each page will have a score, and the search results will be based on the page score (called page rank).
Goal
Input
Output
Constraints
Explanation of PageRank Through an Adjacency Matrix (Example)
Mapping for Simplicity
Use a map/associative array to map the URLs with a unique ID:
This means that the rank of the webpage at time t+1 is equal to the rank of that page at time t multiplied by matrix, M. To achieve this, we create our matrix M based on input. Next, we initialize r(t), which is a matrix of size |V|x1 and consists of the ranks of every webpage. We initialize r(t) to 1/|V|. Next, we compute power_iterations based on our input, p. There is mathematical proof that the matrix r converges, for example, r(t+1) = r(t), at which point the algorithm stops. However, this is difficult to test, and we, therefore, will be testing your algorithm on a fixed power iteration value, p.
Note: In our input case, the number of power_iterations, p, is 2. Therefore, we print r(1) of the URLs sorted in alphabetical order. If p was 1, then return the initializing rank matrix or r(0). If p>2, the process repeats where you multiply the matrix, M, with the new rank matrix r(t+1) at the next iteration.
Optional Template
This template is also provided in the P2 Catch Template (https://github.com/COP3530/P2-Catch-Template) . Even if you choose to make your own code structure, the template will likely still be useful to you as it sets up Catch testing for you.