6
$\begingroup$

I was just wondering what the complexity of the PageRank problem is. A description can be found here: http://en.wikipedia.org/wiki/PageRank . (I am referring to the problem that is solved by the PageRank algorithm, i.e., the question of how one should reasonably distribute "ranking" throughout a graph in a way that is consistent with the model presented in the article I've linked to.)

I've always been curious as to whether or not there is a deterministic polynomial time algorithm that can do as well as the actual PageRank algorithm that Google uses.

It's clear to me that the problem is FNP at worst, as it's easy to verify if a given "arrangement" of rankings for a series of nodes is consistent and valid. I'm not sure beyond that, though. Is it NP-hard? I cannot think of which NP-complete problem would reduce to it.

Thank you,

Philip

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ A nitpick. Pagerank is an algorithm, not a problem. I suspect that the problem itself is something about eigenvalues and fixed points. $\endgroup$
    – Suresh Venkat
    Commented Oct 5, 2010 at 4:16
  • $\begingroup$ Sorry. How do I refer to the problem that is solved by the PageRank algorithm? $\endgroup$
    – user1338
    Commented Oct 5, 2010 at 4:17
  • $\begingroup$ (I tried to clarify above.) $\endgroup$
    – user1338
    Commented Oct 5, 2010 at 4:19
  • 7
    $\begingroup$ "How one should reasonably distribute a ranking..." is not a sufficient specification of a problem to be able to analyze its complexity. I would say you should either formulate a concrete question or ask about the running time of the pagerank algorithm itself. $\endgroup$
    – Lev Reyzin ♦
    Commented Oct 5, 2010 at 4:37

1 Answer 1

Reset to default
9
$\begingroup$

As pointed out on the wikipedia page you cite, PageRank is simply computing the eigenvector corresponding to the maximum eigenvalue of the (modified) adjacency matrix of the web graph. Since this is simple linear algebra, it should definitely be in FP, if not much smaller classes.

Part of the issue with Google's implementation is that the web is so large that its adjacency matrix doesn't fit into the memory of any single (or even any 10,000) computers. So although the complexity of PageRank is technically in FP, the scale at which Google is doing it doesn't really fit into the realm of traditional single-processor complexity. To discuss the complexity of actually computing PageRank on a graph as large as the whole web, you'd at the very least have to consider some sort of distributed computation model.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Did Google compute the eigenvector directly each time or did they just update it each time the graph changed? $\endgroup$
    – Kaveh
    Commented Oct 5, 2010 at 14:51
  • $\begingroup$ @Kaveh: Well, I assume they update it on-the-fly, since I imagine computing it from scratch would be rather expensive. From that perspective this starts to get into streaming algorithms, distributed dynamic data structures, etc. I wonder what the best complexity of an update is? (But the OQ was simply about computing PageRank of a graph.) $\endgroup$
    – Joshua Grochow
    Commented Oct 5, 2010 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.