Manipulation-resistant Reputations Using Hitting Time
No Access Until
Permanent Link(s)
Other Titles
Author(s)
Abstract
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, 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. Our algorithm, which applies to any random walk with restart, exploits a relationship between PageRank and hitting time in random walks with restart. This relationship also provides novel insights into spam detection and PageRank computation.