Stanford CS224W: Machine Learning with Graphs - Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 4.2 - PageRank: How to Solve?

For more information about Stanford’s Artificial Intelligence professional and graduate programs, visit: https://stanford.io/3jCeHZW Jure Leskovec Computer Science, PhD After introducing PageRank and its formulation, we now discuss methods to solve for PageRank. We present the power iteration method for solving for the principle eigenvector of a graph’s stochastic adjacency matrix (i.e. the PageRank). Additionally, we introduce two problems in the previous implementation of PageRank: dead ends (node’s with no out links) and spider traps (node groups with no out links). To address these issues we present the idea of random uniform teleportation and reveal the Google Matrix for leveraging power iteration to solve for PageRank while avoiding the issues presented. To follow along with the course schedule and syllabus, visit: http://web.stanford.edu/class/cs224w/ 0:00 Introduction 0:16 PageRank: How to solve? 1:49 Power Iteration Method 4:38 PageRank: Three Questions 5:18 PageRank: Problems 5:56 Does this converge? 7:01 Does it converge to what we want? 7:44 Solution to Spider Traps 9:20 Solution to Dead Ends 10:26 Why Teleports Solve the problem? 12:21 Solution: Random Teleports 14:29 The Google Matrix PageRank equation Brin-Page, '98 16:15 Random Teleports (B = 0.8) 18:03 PageRank Example 20:10 Solving PageRank: Summary