This wiki article seems quite helpful: http://en.wikipedia.org/wiki/Random_walk#Random_walk_on_graphs **EDIT** If you don't like the wikipedia, see http://www.fis.unipr.it/stat/PAPERS/PRStPh0027.pdf