Monday, October 1, 2007
4:00 PM
5130 Upson Hall
  Theory Seminar
Fall 2007
CS 789

Dan Sheldon
Cornell University


Manipulation-resistant Reputations Using Hitting Time


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, expected hitting time --- the time to reach v in a random walk --- measures essentially the same quantity as PageRank, but excludes v's opinion.

In this talk I will introduce hitting time as a reputation system and show that it resists tampering by individuals or groups who strategically place outlinks. For example, the outlinks of v have no effect on the reputation of v, and the damage v can cause to others is limited by the reputation of v. Also, the effect of placing additional nodes operating under your control (often called sybils) is limited.

This talk is based on joint work with John Hopcroft, and will be presented at the 5th Workshop On Algorithms And Models For The Web-Graph (WAW2007) in December.