Random Walks and Graph Properties
By Ravi Kumar
Random walks, an inspiration for PageRank, are natural ways to explore a graph. We will study the use of uniform random walks to estimate various properties such as the size of the graph, average degree, number of triangles, etc. Less obvious random walks can also be designed to do other tasks such as uniformly generating a node or counting network motifs. Our perspective is that one has to be careful in using random walks for other applications.