链接分析Websearch中词项作弊E.g服装店网站

1Web ges-Weblinks– →Web2BroadSearchEngines:2WhotoWebsearch中词 E.g.服装 Whatisthe“best”answertoaspecific 网页,(e.g.,foraqueryNosingleright4RankingNodesontheWeb56THE“FLOW”7Linkas8Example:Pagerank基本想

’sIdeaof 网页内容的判 ’s要性取值(pagerank)，据此对网页排序SimpleRecursiveEachlink’svoteisproportionaltoimportanceofitssourceIfpagejwithimportancerjhasnout-links,eachlinkgetsrj/nvotesPagej’sownimportanceisthesumofthevotesonitsin-linksFlowModelSolvingtheFlow方程组无唯一解(无穷多解增加约束条件，唯一ry+ra+rm=ry=2/5,ra=2/5,rm= NewPagerank：MatrixMisacolumnstochasticmatrix,i.e.,columnssumtoLetpage𝑖has𝑑𝑖out-Ifij,thenMji=1/diElseRankvector𝑟𝑖istheimportancescoreofpage∑i𝑟𝑖=Theflowr=MExample:FlowEquation&Eigenvector1 例例 .. 用随 解设想用户随机浏览 任意时刻t,停留在页面 设页面停留概率分布矢量平稳分t+1时刻用户在哪里p(t+1)=如果随 的状态满p(t+1)=Mp(t)=p(t)为stationaryRankvectorrr Existenceand 关于PageRank的3个疑DoesthisDoesitconvergetowhatweAreresults收敛

来看两个例 收敛得有意义PageRank遭遇的2个问Problem:Spidermisaspider .. Iteration0,1,2,AllthePageRankscoregets“trapped”innode Solution: solutionforspiderAteachtimestep,therandomsurferhastwoWithprob.β,followalinkatWithprob.1-β,jumptosomerandomCommonvaluesforβareintherange0.8toSurferwill eportoutofspidertrapwithinafewtimesteps随机跳转 Y

yyyyyya 0A

1/21/201/31/3 0+1/31/3011/31/3yam随机跳转

1/31/21/2 0 + 0 yyamy1 a=1 .. m1 Problem:Dead路的网页（死胡同Solution1Web删除 Solution2: eports:Followrandom eportlinkswithprobability1.0fromdead-endsAdjustmatrix eportSolvetheSpider-trapsarenotaproblem,butPageRankscoresarenotwhatwewantSolution:NevergetstuckinaspidertrapbyeportingoutofitinafinitenumberofstepsDead-endsareaproblem.ThematrixisnotcolumnstochasticsoourinitialassumptionsarenotmetSolution:MakematrixcolumnstochasticbyalwayseportingatdeadendsSolution: Thisformulationassumesthat𝑴hasnodeadends.Wecaneitherpreprocessmatrix𝑴toremovealldeadendsorexplicitlyfollowrandom eportlinkswithprobability1.0fromdead-ends. Sample: ComputingPageMatrixRearrangingtheSparseMatrixSparseMatrix仅用非零项表示稀疏矩

destination031,5,1517,64,113,117,2213, (E.g.10N4*10*1billionBasicAlgorithm:UpdateBlock- 小PageRank的定PageRank的迭代计针对终止点 陷阱的措 稀疏矩阵表块更块条更新（分布式计算PageRank的一些问衡量页面的流行 单一的重要性测Topic-SpecificInsteadofgenericpopularity,canwemeasurepopularitywithinatopic?dependingonwhetheryouareinterestedinsports,historyandcomputersecurityGoal:EvaluateWgesnotjustaccordingtotheirpopularity,butbyhowclosetheyaretoaparticulartopic,e.g.“sports”or“history”AllowssearchqueriestobeansweredbasedoninterestsoftheuserTopic-SpecificeportcangoStandardPageRank:Anypagewithequalprobability.(Toavoiddead‐endandspider‐trapproblems)“relevant”pages eportIdea:BiastherandomWhen eports,shepicksapagefromasetScontainsonlypagesthatarerelevanttothetopic.(E.g.,OpenDirectorypagesforagiventopic/query)For eportsetS,wegetadifferentvectorMatrixA为不 建立不同的16个DMOZ顶 分e.g.,arts,business,WhichtopicrankingtoUsercanpickfromUsercontext,e.g.,user’susethecontextoftheE.g.,Historyofqueriese.g.,“basketball”followedbyFindingrelatedorsimilar Theproblemofmeasuring“similarity”ofobjectsarisesinmanyapplications.ExistingSim(a,b):similarityscoreof geaandI(a):in-linkneighborsof geO(a):out-linkneighborsof geCommonneighborSim(a,b)==|(c,d)|=CocitationSim(a,b)==|(c,d)|=ExistingSimRank(naive“twopagesaresimilariftheyarereferenced(cited,orlinkedto)bysimilarpages”(1)Sim(u,u)=1;(2)Sim(u,v)=0if|I(u)||I(v)|=,whereCisaconstantbetween0andTheiterationstartswithSim(u,u)=1,Sim(u,v)=0ifu≠v.SimRank(RandomworkPageRank:TRUSTRANK:WhatisWeb行为网页 WebFirstAspeoplebegantousesearchenginestofindthingsontheWeb,thosewithcommercialintereststriedtoexploitsearchenginestobringpeopletotheirownsite–whethertheywantedtobethereornotShirt‐sellermightpretendtobeaboutTechniquesforachievinghighrelevance/importanceforaw TermBelievewhatpeoplesayaboutyou,ratherthanwhatyousayaboutyourselfPageRankasatooltomeasure“importance” WhyitShirt‐sellersayheisaboutmoviesdoesn’thelp,becauseothersdon’tsayheisaboutmoviesHispageisn’tveryimportant,soitwon’tberankedhighforshirtsormoviesvs.Spammers:Round becamethedominantsearchengine,spammersbegantoworkoutwaystoSpamfarmsweredevelopedtoconcentratePageRankonasinglepageLinkspam:CreatinglinkstructuresthatboostPageRankofaparticularpageLink 者观点看，有3类网e.g LinkSpammer’s pageGetasmanylinksfromaccessiblepagesaspossibleto pagetConstruct“linkfarm”togetPageRankmultipliereffectLink最常见和有效 农场组织方式之采用统计方法分析文本e.gNaïveBayes类 邮件过滤的方检查几乎重复的页检测 农场的页Hidingvs.detectingspamfarms…(itisaTrustRank:topic-specificPageRankwitha eportsetof“trusted”pagesE.g. s, sfornon-USTrustRank:Basicprinciple:Approximate从web网上抽取一 网页“seed这个任务很艰巨，somustmakeseedsetassmallaspossibleTrustSimpleModel:TrustWhyisitagood信 选 集集合大小的权需要人工检查，所以保证所有好网页以最短路径抵达与集合；所以集合越大越好挑 集合的方 根据pagerank选择k个页面。原因 如.edu,.mil,.SpamIntheTrustRankmodel,westartwithgoodpagesandpropagatetrustComplementaryWhatfractionofapage’sPageRankcomesfromspampages?Inpractice,wedon’tknowallthespampages,soweneedtoestimateSpamMass HUBSANDHubsandHITS(Hypertext-InducedTopic目标:假设我们想要找到好报 Idea:Linkas In-link?Out-FindingHITS页Authorities:报纸主课程主汽车制造商的主 报纸列表页课程列表页每个汽车厂商 页Countingin-links:Countingin-links:ExpertQuality:联合迭代定Hubsand

[KleinbergHubsandHubsand存在性与唯一ExampleofPageRankandPageRank和HITS是一个问题的两种方ThedestiniesofPageRankandHITSpost-1998wereverydifferent本章小 HITS：导航页 Pagerank稀疏矩条块更面 的对 的ComputethePageRankofeachpage,assumingβ=0.8.eComputethetopic-sensitivPageRank,assumingtheeeportset(a)A(b)AandSupposetwospamfarmersagreetolinktheirspamfarms.How