資源描述：
《manipulation-resistant reputations system》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、Manipulation-ResistantReputationsUsingHittingTimeJohnHopcroftDanielSheldonCornellUniversityCornellUniversityjeh@cs.cornell.edudsheldon@cs.cornell.eduAbstractPopularreputationsystemsforlinkednetworkscanbemanipulatedbyspammerswhostrategicallyplacelinks.Thereputationofnodevisinterpretedasthewo
2、rld’sopinionofv’simportance.InPageRank[4],v’sownopinioncanbeseentohaveconsiderablein?uenceonherreputation,wherevexpressesahighopinionofherselfbyparticipatinginshortdirectedcycles.Incontrast,weshowthatexpectedhittingtime—thetimetoreachvinarandomwalk—measuresessentiallythesamequantityasPageRan
3、k,butexcludesv’sopinion.Wemakethesenotionsprecise,andshowthatareputationsystembasedonhittingtimeresiststamperingbyindividualsorgroupswhostrategicallyplaceoutlinks.Wealsopresentanalgorithmtoef?cientlycomputehittingtimeforallnodesinamassivegraph;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,whereisde?nedtobethestationarydistributionofarandomwalkonG,givingthepleasinginterpretationthatthescoreofpagevisthefractionoftimeawebsurferspendsthereifsherandomlyfollowslinksforever.Fortechnicalreasons,therandomwalkismod
7、i?edtorestartineachstepwithprobability,jumpingtoapagechosenuniformlyatrandom.Thisensuresthatexistsandisef?cienttocompute.Thenawell-knownfactaboutMarkovchains[1]saysthat1=(v)isequaltotheexpectedreturntimeofv,thenumberofstepsittakesarandomwalkstart
