For probabilistic algorithms such as PageRank and EigenTrust, the stopping case is given as $|R_{t+1} - R_{t}| < \epsilon$ (i.e. convergence is assumed). Neither the papers on EigenTrust or PageRank, or the PageRank wiki page, give any clear indication of what $\epsilon$ should be.

I believe it might be something to do with the damping factor $d = 0.85$; specifically $\epsilon = 1 - d = 0.15$, but I can't be sure.

How is $\epsilon$ determined, and if it's nothing more than an abitrary value $0 \leq \epsilon \leq 1$, how would you choose a sensible value?

  • 3
    $\begingroup$ The value of $\epsilon$ is probably determined experimentally. These are practical algorithms, and there are practical considerations, speed vs. accuracy. $\endgroup$ – Yuval Filmus Mar 10 '14 at 12:10
  • $\begingroup$ @YuvalFilmus OK, that makes sense. Still, is there a ballpark? $0.1$, $0.1^{-10}$? Or a source which would tell me what is used in practice? $\endgroup$ – Anthony Mar 11 '14 at 20:44
  • 1
    $\begingroup$ Sadly, I have no idea. Nobody probably uses the vanilla version of the algorithms, so it's not even clear who to ask. There could be research papers on that in the area of search engines - did you try looking for such papers? $\endgroup$ – Yuval Filmus Mar 12 '14 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.