The final question in this project describes how eigenvectors made some people v

Question

The final question in this project describes how eigenvectors made some people very, very rich. More specifically, we explore the workings of an early version of Google's PageRank algorithm1. After Google has found the webpages it thinks are relevant to your search, the PageRank algorithm is used to determine the order in which the results are presented. A directed graph is a set of dots (called vertices), some of which are linked to others by arrows (called edges). The direction of the edges matters, so if v and w are vertices then an edge from v to w is not the same as an edge from w to v. To simplify matters for this project, we assume there is never an arrow from a vertex to itself, and if v and w are vertices then there is at most one edge going from v to w. The internet can be thought of as a directed graph. Each webpage is represented by a vertex. There is an edge from a vertex v to a vertex w exactly when there is a hyperlink from the page represented by v to the page represented by w A picture of the directed graph corresponding to the real-life internet can be found at http://www.opte.org/the-internet/. That directed graph has billions of vertices, and calculating things about it requires significant computational power For the following questions we will use the following, much smaller, directed graph, for an "internet" with only 7 pages: 6 (a) One simple method for deciding which page is the most important is to count the number of incoming links to that page. Use this method to rank the pages in our "internet" from most important to least important (your ranking should include each page, but some pages might be tied for importanc. Do not use MATLAB for this task.

Explanation / Answer

Direct link count: Here we will list for each vertex, the number of edges that goes into that vertex and order the vertex list in decreasing order of number of vertex leading to it.

So the order of importance for the 7 websites are 4 > 1 > 2=3 > 5=6=7, the greater than sign refers to more important and equality refers to a tie.

Weighted lik count: There is another better alternative to finding the importance of the internet pages. Instead of directly counting the number of edges leading to a webpage, we should also consider the indirect links to a webpage. e.g. 5 leads to 4 which in turn leads to 1. So indirectly 5 leads to 1.

An easy way to find the weighted importance of a webpage is to count each direct link as '1', a 2 step indirect link as '0.5' and so on.

Counting in the above fashion leads to weighting an r-step indirect link as 1/2r.

The above table modified according to weighing logic is as below:

So when weighted, the importance of webpages change very slightly,

the new order is: 1 > 4 > 2=3 > 5=6=7

Note: For your problem, the direct link count is the correct answer, but the weighted link count is a more refined way of calculating webpage importance.

Vertex Name (Internet page) Number of edges leading to vertex 4 4 1 3 2 1 3 1 5 0 6 0 7 0

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.