Manipulation-Resistant Reputations Using Hitting Time
John E. Hopcroft, Daniel R. Sheldon · Internet Mathematics · 2008
Popular reputation systems for linked networks can be manipulated by spammers who strategically place links. In PageRank [Brin and Page 98], pages endorse others by placing links, and the global link structure is analyzed to determine the reputation of each page. Though this is meant to be a global measure, page _υ_ can boost its own PageRank considerably using a simple self-endorsement strategy: placing outlinks to form short directed cycles. In contrast, we show that expected hitting time—the time to reach _υ_ in a random walk—measures essentially the same quantity as PageRank, but does not depend on _υ_'s outlinks. We develop a reputation system based on hitting time and show that it 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.