Analytical and Iterative Methods of Computing PageRank of Networks

This thesis is about variants of PageRank, methods of PageRank computation and perturbation analysis of a PageRank vector as a stationary distribution of a kind of perturbed Markov chain model. Chapter 2 of this thesis gives closed form formulae for ordinary and lazy PageRanks for some specific simple line graphs. Different cases of changes made to the simple line graph are considered and for each case, a corresponding formula for each of the two variants of PageRank is provided. Chapter 3 is dedicated to the exploration of relationships that exist between three known variants of PageRank: ordinary PageRank, lazy PageRank and random walk with backstep PageRank in terms of their convergence and consistency in rank scores for different graph structures with reference to PageRank parameters, the damping factor c and backstep parameter β. In Chapter 4, we discuss numerical methods used in solving the PageRank problem as a linear system and evaluate some stopping criteria that can be employed in such methods. Finally, in Chapter 5, we address the PageRank problem as a first order perturbed Markov chain problem and study the perturbation analysis for stationary distributions of Markov chains with damping component. We illustrate our results on asymptotic perturbation analysis by using different computational examples