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.
Other work is geared towards modifications of the mechanism. For instance, Global Hitting Time @cite_12 was designed as a transformation of to counter cross-reference link spam, where nodes link each other to increase their rank, but it still suffers if the number of spammers is large. Variants include Personalized Hitting Time @cite_14 .
@cite_14 @cite_12
2403531831 2037242246
Informative and scalable trust mechanisms that are robust to manipulation by strategic agents are a critical component of multi-agent systems. While the global hitting time mechanism (GHT) introduced by Hopcroft and Sheldon is more robust to manipulation than PageRank, strategic agents can still benefit significantly under GHT by performing sybil attacks. In this paper, we introduce the personalized hitting time mechanism (PHT), which we show to be significantly more robust to sybil attacks than GHT. Specifically, if an agent has already cut all of its outlinks under PHT (which only leads to a negligible benefit), then adding sybils leads to no additional benefit. We provide an experimental analysis which demonstrates that, in the presence of strategic agents that create sybils, PHT dominates GHT (as well as PageRank and personalized PageRank) in terms of informativeness. We find the large dominance of PHT over GHT particularly surprising given the small difference between the two mechanisms. Finally, we provide a Monte Carlo algorithm to compute approximate PHT scores at scale, and we show that PHT retains its robustness to manipulation when used with approximate scores. Popular reputation systems for linked networks can be manipulated by spammers who strategically place links. The reputation of node v is interpreted as the world's opinion of v's importance. In PageRank [4], v's own opinion can be seen to have considerable influence on her reputation, where v expresses a high opinion of herself by participating in short directed cycles. In contrast, we show that expected hitting time -- the time to reach v in a random walk -- measures essentially the same quantity as PageRank, but excludes v's opinion. We make these notions precise, and show that a reputation system based on hitting time resists tampering by individuals or groups who strategically place outlinks. We also present an algorithm to efficiently compute hitting time for all nodes in a massive graph; conventional algorithms do not scale adequately.