Short introduction to random walks on graphs. For basic facts about random walks on graphs, any introductory text about markov chains will do it. For more special and more advanced questions there are some online references, such as Lovasz: Random walks on graphs, a survey, 1993 or D.Aldous and Fill: Reversible Markov Chains and Random Walks on Graphs (book in preparation). I wrote a small matlab demo where you can observe the behavior of the random walk, the eigenvectors, and the spectral gap.
Methods to compute eigenvectors of Matrices: Power method, Lanczos method. As literature I recommend Sections 7.3 and 9.1. of Golub/ van Loan: Matrix Computations (it contains more details than you need to know). Both topics should also be treated in most lecture notes for numerics.
PageRank (the algorithm used by google):
HITS: the hub/authority approach to ranking.
TrueSkill: This is a Bayesian approach to rank players in online multiplayer games to form teams and is described here, and a detailed description is in the technical report Ralf Herbrich, Thore Graepel: TrueSkill: A Bayesian Skill Rating System. 2006. Unfortunately we are running out of time and won't have time to discuss it :-(