PhD course: Random walks on graphs and their applications
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:
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
Applications: Page-rank, individual page-rank, clustering
- 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:
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).
The exam is oral. Write me an email to schedule an exam which must take place before June 21st.
- 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.