Random Walks & Google Page Rank II
* revist example showing random surfer
* what is steady state?
- motivate and explain P^n
- motivate pi  * P
* multiple ways to solve Markov chains
- eigenvectors
- Gauss
- power
- random walk
* P' pi' = 1 pi' <= eigenvector associated to eigenvalue 1
* show simple example
- compute eignvalues & eigenvectors
- proof that largest eigenvalue is 1
-- any row sum = 1
-- rho(M) = rho(M')
-- rho(M) <= 1
-- pi  = pi P  implies 1 is eigenvalue
- show that convergence depends on second eigenvalue
P'= V D V(-1)
* emphasize that Google Page rank is weighted average of ranks
- flow balance equations
* Clustering
- Shi-Malik algorithm, L=I-D^(-1/2) P D^(-1/2)
(2nd largest eigenvalue/eigenvector)
* What is the node closest related to x: y or z?
- compute # of visits to x starting from y or z
- two ways (to be described next class)
-- (I-Q)^(-1)
-- restart and compute pi0/pi0, pi1/pi0, pi2/pi0, ..., piM/pi0