MATH 261C
Topics in Probabilistic Combinatorics and Algorithms
Spring, 2010
Lecturer: Professor Fan Chung Graham
Time: MW 1:00-2:20pm
Place: B412 APM
Office Hours: W 3-4pm APM7101
In this course, the main topic will be
spectral graph theory and
random walks in graphs.
We will cover both the basic theory and advanced methods
for dealing with diffusion type problems. Applications include
Pagerank of graphs, local graph algorithms, percolation on
complex graphs, and network games.
This course is NOT a continuation of 261A and 261B earlier. The only prerequisites
are some basic linear algebra, graph theory and probability.
The main books:
An outline of lectures (subject to change):
-
Lecture 1: Introduction. New directions in graph theory based on
spectral graph theory and
random walks.
-
Lecture 2: The Random walk, PageRank and their relation to the Laplacian.
-
Lecture 3: The original PageRank and the personalized PageRank
-
Lecture 4: Fast approximation algorithm for computing PageRank
-
Lecture 5:
The classical Matrix-tree theorem and a Matrix-forest theorem for PageRank.
-
Lecture 6: The classical Cheeger inequality and the PageRank Cheeger inequuality
-
Lecture 7: Spectral graph partitioning and local partitioning using Pagerank
-
Lecture 8: Mixing inequalities for random walks and PageRanks
-
Lecture 9: Electrical network theory using PageRank
-
Lecture 10: The heat kernel pagerank and the associated mixing inequality
-
TBA
Announcements
|Lecture Notes and Exercises
|Reading
|Midterm
|Final
Back