q3 1) b) c)

QUESTION 3: COMPUTING POPULARITYAND THE PAGERANK ALGORITHM How does the Google search engine decide how to rank pages in your search results? We'll start with a simple problem that illustrates the general ideas. Suppose there are four people named Alice, Bob, Carol and Dave. They want to work out who in their group is the most popular. They each list who is their friend a follows: Alice is friends with Bob and Carol. Bob is friends with Alice, Carol and Dave. Carol is friends with Alice, Bob and Dave. Dave is friends with Alice and Carol. This can be rewritten as a table: Alice Bob Carol Dave Alice 0 1 1 1 Bob 1 0 1 0 Carol 1 1 0 1 Dave 0 1 1 0 FIGURE 1. A friendship table where a 1 indicates a friendship (from the column name to the row name, but not necessarily vice versa. How- ever, some people list more friends than others. To compensate for that, we normalize (divide each column by the number of people in it) to get the friendship matrix F: 1 1 1 '13 3 i g F = i l 3 l 3 i 1 S 3 3 TA We want to compute the popularity vector F = :1; which contains the popularity of each member of the group. 1'1) The basic property that we will use is the following: A person's popularity is the weighted sum of the popularity of people who reference that person. For instance, we have that rA = rB + rc + in). In this equation, Bob's 221 MATLAB ASSIGNMENT E 3 contribution to Alice's popularity is r3 because Alice makes up one third of Bob's 'iends. Similarly, Carol and Dave make contributions based on their friendships and their own popularity. Written as a matrix equation, this is L? = F, or equivalently, F is an eigenvector of L with eigenvalue 1. (a) Use Matlab to nd the popularity vector for these people. Store F as popvector. Moving on to Google: this is essentially the method that is used to rank search results. You input some words (which we will call the set K) and the software nds vast numbers of webpages WK containing the words in K. The big challenge is to rank the pages to nd those few good (popular) webpages. What the Google founders did was have the software look at each webpage w in WK and determine which other web pages in WK it links to, thus associating to each webpage to a \"friendship vector" FL, of 0's and 1's, just as we did above with the list of students. Next, it builds a matrix L whose columns are the vectors EU and proceeds just as in the popularity problem. Google computes 'r' very quickly and returns the webpages in order of their apparent popularity. The idea of Page Rank is as follows: the popularity of any web page is judged by the pages that have links to it. If we create a webpage i and include a link to the web page j, this likely means that j is relevant to the topic of our webpage i. Also, if there are a lot of pages that link to j, this means that many independent writers think that page j is relevant to the topic. Ifon the other hand, j has only one incoming link, but that comes from an popular site k, we imagine that kpasses on its popularity to j. Let's consider avery small intemet with just ve sites, let's call them A, B, C, D and E. Suppose that the links are given as in this picture and table (remember, a 1 means that the column links to the row and zero means no link). WI'llIBIl as a matrix equatlon, [Ills IS LT = 1', 01' equivalently, 1' IS an BlgBIIVBCIOE OI L Wll'Il eigenvalue 1. (a) Use Matlab to nd the popularity vector for these people. Store 1" as popvector. Moving on to Google: this is essentially the method that is used to rank search results. You input some words (which we will call the set K) and the software nds vast numbers of webpages WK containing the words in K. The big challenge is to rank the pages to nd those few good (popular) webpages. What the Google founders did was have the software look at each webpage w in WK and determine which other web pages in WK it links to, thus associating to each webpage w a \"friendship vector" E, of 0's and 1's, just as we did above with the list of students. Next, it builds a matrix L whose columns are the vectors 15;, and proceeds just as in the popularity problem. Google computes 7' very quickly and returns the webpages in order of their apparent popularity. The idea of Page Rank is as follows: the popularity of any web page is judged by the pages that have links to it. If we create a webpage i and include a link to the web page j, this likely means than is relevant to the topic of our webpage i. Also, if there are a lot of pages that link to j, this means that many independent writers think that page j is relevant to the topic. Ifon the other hand, j has only one incoming link, but that comes from an popular site k, we imagine that kpasses on its popularity to j. Let's consider a very small internet with just ve sites, let's call them A, B, C, D and E. Suppose that the links are given as in this picture and table (remember, a 1 means that the colurrm links to the row and zero means no link). r2. FIGURE 2. A graph of a small network 4 DUE 27 NOVEMBER 2020 Ideally, your vector should have all entries 2 0, and have length 1, but for the sake of this assignment, we will accept any scalar multiple of the 'correct' vector. (c) Suppose you control webpage E and you would like to improve your standing in the ranking by adding or subtracting links from your page. So you try adding a link to site B. Store the new popularity vector as GEvecl. Did this manoeuvre help improve the ranking of your site? Finally, you put your page back as it was to start with and call your friend who runs website A and ask her to add a link. She does that. Store the new popularity vector as GEve c3, Did that help your ranking? (Note: an answer called GEvec2 was originally required by this assignment. but was removed.)