Dan Sheldon

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.

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.