Skip to main content


eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Manipulation-resistant Reputations Using Hitting Time
Authors: Hopcroft, John
Sheldon, Daniel
Keywords: computer information science
technical report
Issue Date: 3-Jul-2007
Publisher: Cornell University
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.
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
TR2007-2085.pdf201.7 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us