MATH_2250_001_FALL_2023_PSET10

University of Utah Fall 2023 MATH 2250-001 PSet 10 Specification Instructor: Alp Uzman Subject to Change; Last Updated: 2023-11-13 1 Background In this problem set, we delve into the intricacies of PageRank, a simple but then- revolutionary algorithm that lies at the heart of Google’s search engine. Developed by Sergey Brin and Lawrence Page, and patented by Lawrence Page, PageRank offers a unique approach to ranking web pages by assessing their relative importance within the vast network of the internet. Throughout, 0 ≤ α ≤ 1 denotes the damping factor and B = ( B 1 , B 2 , ..., B n ) denotes the bias vector (aka the personalization vector). Here n is the number of webpages in the network in question, for any i = 1 , 2 , ...n , B i ≥ 0 and ∑ n i =1 B i = B 1 + B 2 + · · · + B n = 1 , so that B is a probability vector . If S is an n × n column- stochastic matrix , so that each entry of S is a nonnegative number and the entries of each columns add up to one, we say that S is the hyperlink matrix associated to a network if the ( i, j ) -th entry S ij of S is given by: S ij = ( c j , if there is a hyperlink from webpage j to webpage i 0 , otherwise where c j is the reciprocal of the number of webpages the j th webpage contains a hyperlink to. Given a network of webpages with associated hyperlink matrix S , the Google matrix G ( α, B ) with damping factor α and bias vector B is by definition G ( α, B ) = αS + (1 − α ) B 1 , where 1 is the 1 × n row matrix 1 = ( 1 1 · · · 1 ) ; Recall that we take tuples as column vectors, so that B 1 is an n × n matrix. The unique probability vector PR ( α, B ) that satisfies the eigenvector equation PR ( α, B ) = G ( α, B ) PR ( α, B ) Alp Uzman Page 1 of 6 uzman@math.utah.edu

University of Utah Fall 2023 is the PageRank vector (when it exists). When α = 1 , the bias vector B has no effect, hence we simply write G (1) for G (1 , B ) and PR (1) for PR (1 , B ) . The entries of the PageRank vector PR ( α, B ) , when reordered from the largest to the smallest, rank the webpages in the network in question, and signify in which order the webpages ought to be presented to a user of a search engine. See the PageRank page under the Pages tab on Canvas for further materials. You may also find this account of stochastic matrices useful. Finally it might also be useful to compare description of PageRank in problem set 4 . 2 What to Do Solve the problems below. Though they may seem long, the additional text is meant to guide you. When documenting your solutions, be thorough. Your goal is not just to find the answer, but to create a clear, logical pathway to it that you or anyone else could follow in the future. For the problems in this problem set, the use of a computational tool such as WolframAlpha is recommended. As an example, this is the output WolframAlpha produces when the input is the matrix ( 2 1 1 1 ) ; one would input this matrix in WolframAlpha like so: {{ 2 , 1 } , { 1 , 1 }} 1. List all networks with at most three websites. For each such network, also write down the hyperlink matrix. 2. Consider all networks with exactly three websites. Represent each such network as a node in another, "meta-network". Put at arrow from network N 1 to N 2 if the network N 2 can be obtained by adding one arrow to network N 1 . For this meta-network, perform the following tasks: (a) Draw the meta-network. (b) How many connected components does the meta-network have? (c) Does the meta-network have any dangling nodes? (d) Compute the associated hyperlink matrix. Is the hyperlink matrix stochas- tic? If the hyperlink matrix is not stochastic, complete it to a stochastic by first adding one "virtual" hyperlink from any dangling node to all nodes (including the dangling node itself), and then computing the hyperlink matrix again. 3. Consider the following network consisting of four webpages: Alp Uzman Page 2 of 6 uzman@math.utah.edu

University of Utah Fall 2023 (b) Take as damping factor α = 0 . 85 and as bias vector B = (1 / 2 , 1 / 2 , 0 , 0) , and compute the PageRank vector PR ( α, B ) . Based on your calculation, which webpage is the highest ranking? 5. Consider the following network consisting of five webpages: 1 3 5 2 4 Perform the following tasks: (a) Compute the hyperlink matrix associated to the network. (b) Find all eigenvectors of the hyperlink matrix associated to the eigenvalue 1 . (c) Take as bias vector B = (1 / 5 , 1 / 5 , 1 / 5 , 1 / 5 , 1 / 5) , and find all damping factors α such that the dimension of the eigenspace of the Google matrix G ( α, B ) associated to the eigenvalue 1 is one. 6. Consider the column-stochastic matrix   0 1 2 1 2 0 0 1 2 1 1 2 0   . (a) Draw the network associated to this matrix. (b) Take as bias vector B = (1 , 0 , 0) , and find all damping factors α such that G ( α, B ) is not diagonalizable. Alp Uzman Page 4 of 6 uzman@math.utah.edu

University of Utah Fall 2023 3 ChatGPT Regulations This section is in case you decide to use ChatGPT in this problem set. If you will not be using ChatGPT you may skip this section. 3.1 ChatGPT Versions • You may use either the GPT3.5 (freely available with a ChatGPT account) or GPT4 (available with a ChatGPT Plus account). • Turn off all Custom Instructions before you start a chat. If you don’t, it will be apparent in the archived version that you didn’t. 3.2 Chat Guidelines • Your first message in any given chat must be the following guardrails paragraph; you may copy and paste it: Hello. I am working on a differential equations and linear algebra problem as part of a university class. My instructor has permitted the use of ChatGPT, but only under specific guidelines to encourage independent critical thinking. Please assist me by asking probing questions, encouraging reflection, and providing general insights about the concepts involved. Do not offer direct hints, strategies, solutions, or step-by-step guidance. I seek to understand the underlying principles and want to develop my own approach to the problem. Your role is to facilitate my learning process without directly leading me to the answer. Thank you! • You may copy and paste parts of this specification document, as well as parts of the textbook or other sources. • You may not ask ChatGPT to write for you the solution for any one of the problems in complete detail. 3.3 Archiving Chats • Once you are done with a chat with ChatGPT, click the "Share chat" icon on the top righthand corner; see the documentation for details. In your chat don’t include any personal information, and keep your user name hidden when you are creating a link for anonymity. • Next you will use Wayback Machine to take a "snapshot" of your chat, see the documentation for the "Save Page Now" feature. You do not need an Internet Archive account to do this, but having such an account (which is free) would provide you with further options. Alp Uzman Page 5 of 6 uzman@math.utah.edu