JavaScript is disabled for your browser. Some features of this site may not work without it.
Manipulation-resistant Reputations Using Hitting Time

Author
Hopcroft, John; Sheldon, Daniel
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.
Date Issued
2007-07-03Publisher
Cornell University
Subject
computer information science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2007-2085
Type
technical report