manipulation-resistant reputations system

《manipulation-resistant reputations system》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Manipulation-ResistantReputationsUsingHittingTimeJohnHopcroftDanielSheldonCornellUniversityCornellUniversityjeh@cs.cornell.edudsheldon@cs.cornell.eduAbstractPopularreputationsystemsforlinkednetworkscanbemanipulatedbyspammerswhostrategicallyplacelinks.Thereputationofnodevisinterpretedasthewo

2、rld’sopinionofv’simportance.InPageRank[4],v’sownopinioncanbeseentohaveconsiderableinfluenceonherreputation,wherevexpressesahighopinionofherselfbyparticipatinginshortdirectedcycles.Incontrast,weshowthatexpectedhittingtime—thetimetoreachvinarandomwalk—measuresessentiallythesamequantityasPageRan

3、k,butexcludesv’sopinion.Wemakethesenotionsprecise,andshowthatareputationsystembasedonhittingtimeresiststamperingbyindividualsorgroupswhostrategicallyplaceoutlinks.Wealsopresentanalgorithmtoefficientlycomputehittingtimeforallnodesinamassivegraph;conventionalalgorithmsdonotscaleadequately.1Intr

4、oductionReputationandrankingsystemsareanessentialpartofwebsearchande-commerce.Thegeneralideaisthatthereputationofoneparticipantisdeterminedbytheendorsementsofothers;forexam-ple,onewebpageendorsesanotherbylinkingtoit.However,notallparticipantsarehonorable—e.g.,spammerswilldotheirbesttomanipul

5、ateasearchengine’srankings.Anaturalrequirementforareputationsystemisthatindividualsshouldnotbeabletoimprovetheirownreputationus-ingsimpleself-endorsementstrategies,likeparticipatinginshortcyclestoboostPageRank.SincePageRankenjoysmanyniceproperties,itisinstructivetoseewherethingsgowrong.LetG=

6、(V;E)beadirectedgraph(e.g,theweb).PageRankassignsascore(v)toeachnodev,whereisdefinedtobethestationarydistributionofarandomwalkonG,givingthepleasinginterpretationthatthescoreofpagevisthefractionoftimeawebsurferspendsthereifsherandomlyfollowslinksforever.Fortechnicalreasons,therandomwalkismod

7、ifiedtorestartineachstepwithprobability,jumpingtoapagechosenuniformlyatrandom.Thisensuresthatexistsandisefficienttocompute.Thenawell-knownfactaboutMarkovchains[1]saysthat1=(v)isequaltotheexpectedreturntimeofv,thenumberofstepsittakesarandomwalkstart