Show simple item record

dc.contributor.authorHopcroft, Johnen_US
dc.contributor.authorSheldon, Danielen_US
dc.description.abstractPopular 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.en_US
dc.format.extent206545 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer information scienceen_US
dc.subjecttechnical reporten_US
dc.titleManipulation-resistant Reputations Using Hitting Timeen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record