PageRank and Polynomial Chaos

@INPROCEEDINGS{constantine2007-pagerank-pce,
  author = {Paul G. Constantine and David F. Gleich},
  title = {Using Polynomial Chaos to Compute the Influence of Multiple Random
    Surfers in the {PageRank} Model},
  booktitle = {Proceedings of the 5th Workshop on Algorithms and Models 
    for the Web Graph ({WAW2007})},
  year = {2007},
  editor = {Anthony Bonato and Fan Chung Graham},
  volume = {4863},
  series = {Lecture Notes in Computer Science},
  pages = {82--95},
  publisher = {Springer},
  abstract = {The PageRank equation computes the importance of pages in a 
web graph relative to a single random surfer with a constant teleportation
coefficient. To be globally relevant, the teleportation coefficient
should account for the influence of all users. Therefore, we correct
the PageRank formulation by modeling the teleportation coefficient as
a random variable distributed according to user behavior. With this
correction, the PageRank values themselves become random. We present
two methods to quantify the uncertainty in the random PageRank: a
Monte Carlo sampling algorithm and an algorithm based the truncated
polynomial chaos expansion of the random quantities. With each of
these methods, we compute the expectation and standard deviation
of the PageRanks. Our statistical analysis shows that the standard
deviation of the PageRanks are uncorrelated with the PageRank vector.},
  doi = {10.1007/978-3-540-77004-6_7},
  key = {CG2007},
  keywords = {pagerank, polynomial chaos},
}