Christopher Engström: PageRank as an expectation on a terminating random walk and applications to large partitioned graphs

Abstract: In this talk we will discuss a definition of PageRank defined as an expectation on a terminating random walk and show how this can be used to calculate PageRank for certain types of vertices as well as a graph partitioned into multiple strongly connected components (SCC's). We will start by discussing these variants of PageRank and why they are useful by looking at 5 different types of vertices and later look at how this can be used in the general case of a graph partitioned into SCC's. Finally we will take a look at some results of an implementation of our ideas on a large graph showing how this leads to a significant reduction in the number of required iterations required and other computational aspects.