PhD course: Random walks on graphs and their applications

Michal Koucký
<koucky@math.cas.cz>

Spring Semester 2012

Duration: 6 weeks (first lecture April 10)
Time and place: Tue 12:30-2:15pm in Nygaard-297 and Thu 10:15-noon in Nygaard-298

In this course I plan to give an introduction to Markov chains, random walks on graphs and their applications. This course assumes a reasonable knowledge of mathematics and probability theory. It is intended for computer science PhD students. It is expected to be possible for PhD students to take the course for credit, the exact number of ECTS and exam form will be negotiated later.

The tentative list of topics:

• Markov chains
• Stationary distribution, convergence
• Applications: self-adjusting queues
• Random walks on graphs
• Hitting time, cover time
• Applications: testing connectivity, treasure hunt
• Short random walks
• Dynamically changing graphs
• Graph resistance
• Applications: Page-rank, individual page-rank, clustering

References:

• Hand-out lecture notes.
• James R. Norris. Markov Chains, Cambridge University Press, 1998.
• Olle Häggström. Finite Markov Chains and Algorithmic Applications, Cambridge University Press, 2002.
• László Lovász. Random Walks on Graphs: A Survey.
• David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs.
  
  
• Greg Barnes and Uriel Feige. Short random walks on graphs. SIAM J. Discrete Math. 9(1): 19-28 (1996).
• Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, and Masafumi Yamashita. Impact of local topological information on random walks on finite graphs. ICALP 2003.
• Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). ICALP 2008.
  
  
• Prasad Tetali. Random Walks and the Effective Resistance of Networks. Journal of Theoretical Probability 4 (1991), 101-109.
• Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The Electrical Resistance of a Graph Captures its Commute and Cover Times. Computational Complexity, 6(4): 312-340 (1997).
  
  
• Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank vectors to locally partition a graph. Internet Math. 4(1):35-64 (2007).

Probability overview.

Exam

Exam topics

• Stationary distribution and convergence of random walks.
• Hitting time, Matthews bound.
• Cover time of undirected graphs.
• Random walks on trees.
• Short random walks, the Metropolis chain.
• Random walks on dynamically changing graphs.
• Graph resistance.