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

$\endgroup$
  • 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 Oct 5 '10 at 4:16
  • $\begingroup$ Sorry. How do I refer to the problem that is solved by the PageRank algorithm? $\endgroup$ – Philip White Oct 5 '10 at 4:17
  • $\begingroup$ (I tried to clarify above.) $\endgroup$ – Philip White Oct 5 '10 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 Oct 5 '10 at 4:37
8
$\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.

$\endgroup$
  • $\begingroup$ Did Google compute the eigenvector directly each time or did they just update it each time the graph changed? $\endgroup$ – Kaveh Oct 5 '10 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 Oct 5 '10 at 16:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.