We study the spammablility of ranking functions on the web. Although graph-theoretic ranking functions, such as Hubs and Authorities and PageRank exist, there is no graph theoretic notion of how spammable such functions are. We introduce a very general cost model that only depends on the observation that changing the links of a page that you own is free, whereas changing the links on pages owned by others requires effort or money. We define spammability to be the ratio between the amount of benefit one receives for one's spamming efforts and the amount of effort money one must spend to spam. The more effort money it takes to get highly ranked, the less spammable the function. Our model helps explain why both hubs and authorities and standard PageRank are very easy to spam. Although standard PageRank is easy to spam, we show that there exist spam-resistant PageRanks. Specifically, we propose a ranking method, Min-k-PPR, that is the component-wise min of a set of personalized PageRanks centered on k trusted sites. Our main results are that Min-k-PPR is, itself, a type of PageRank and that it is expensive to spam. We elucidate a surprisingly elegant algebra for PageRank. We define the space of all possible PageRanks and show that this space is closed under some operations. Most notably, we show that PageRanks are closed under (normalized) component-wise min, which establishes that (normalized) Min-k-PPRis a PageRank. This algebraic structure is also key to demonstrating the spam resistance of Min-k-PPR.
Recent web search techniques augment traditional text matching with a global notion of "importance" based on the linkage structure of the web, such as in Google's PageRank algorithm. For more refined searches, this global notion of importance can be specialized to create personalized views of importance--for example, importance scores can be biased according to a user-specified set of initially-interesting pages. Computing and storing all possible personalized views in advance is impractical, as is computing personalized views at query time, since the computation of each view requires an iterative computation over the web graph. We present new graph-theoretical results, and a new technique based on these results, that encode personalized views as partial vectors. Partial vectors are shared across multiple personalized views, and their computation and storage costs scale well with the number of views. Our approach enables incremental computation, so that the construction of personalized views from partial vectors is practical at query time. We present efficient dynamic programming algorithms for computing partial vectors, an algorithm for constructing personalized views from partial vectors, and experimental results demonstrating the effectiveness and scalability of our techniques. Web spam pages use various techniques to achieve higher-than-deserved rankings in a search engine's results. While human experts can identify spam, it is too expensive to manually evaluate a large number of pages. Instead, we propose techniques to semi-automatically separate reputable, good pages from spam. We first select a small set of seed pages to be evaluated by an expert. Once we manually identify the reputable seed pages, we use the link structure of the web to discover other pages that are likely to be good. In this paper we discuss possible ways to implement the seed selection and the discovery of good pages. We present results of experiments run on the World Wide Web indexed by AltaVista and evaluate the performance of our techniques. Our results show that we can effectively filter out spam from a significant fraction of the web, based on a good seed set of less than 200 sites. 