比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 269 - combinatorics
fan chung graham
ucsd
the pagerank and heat kernel of a graph
abstract:
we will give four proofs of the cheeger inequality which relates the eigenvalues of a graph with various isoperimetric variations of the cheeger constant. the first is a simplified proof of the classical cheeger inequality using eigenvectors. the second is based on a rapid mixing result for random walks by lov\\'asz and simonovits. the third uses pagerank, a quantitative ranking of the vertices introduced by brin and page. the fourth proof is by an improved notion of the heat kernel pagerank. the four proofs lead to further improvements of graph partition algorithms and in particular the local partition algorithms with cost proportional to its output instead of in terms of the total size of the graph.
november 27, 2007
3:00 pm
ap&m 7321
****************************