  Ranking functions such as PageRank assign numeric values (ranks) to nodes of
graphs, most notably the web graph. Node rankings are an integral part of
Internet search algorithms, since they can be used to order the results of
queries. However, these ranking functions are famously subject to attacks by
spammers, who modify the web graph in order to give their own pages more rank.
We characterize the interplay between rankers and spammers as a game. We define
the two critical features of this game, spam resistance and distortion, based
on how spammers spam and how rankers protect against spam. We observe that all
the ranking functions that are well-studied in the literature, including the
original formulation of PageRank, have poor spam resistance, poor distortion,
or both. Finally, we study Min-PPR, the form of PageRank used at Google itself,
but which has received no (theoretical or empirical) treatment in the
literature. We prove that Min-PPR has low distortion and high spam resistance.
A secondary benefit is that Min-PPR comes with an explicit cost function on
nodes that shows how important they are to the spammer; thus a ranker can focus
their spam-detection capacity on these vulnerable nodes. Both Min-PPR and its
associated cost function are straightforward to compute.
