Using polynomial chaos to compute the influence of multiple random surfers in the PageRank model

Abstract. The PageRank equation computes the importance of pages in a web graph relative to a single random surfer with a constant tele-portation 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 ran-dom variable distributed according to user behavior. With this correc-tion, 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 poly-nomial 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.