鏈接分析Websearch中詞項作弊E.g服裝店網(wǎng)站

1Web ges-Weblinks– →Web2BroadSearchEngines:2WhotoWebsearch中詞 E.g.服裝 Whatisthe“best”answertoaspecific 網(wǎng)頁,(e.g.,foraqueryNosingleright4RankingNodesontheWeb56THE“FLOW”7Linkas8Example:Pagerank基本想

’sIdeaof 網(wǎng)頁內(nèi)容的判 ’s要性取值(pagerank)，據(jù)此對網(wǎng)頁排序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 例例 .. 用隨 解設(shè)想用戶隨機瀏覽 任意時刻t,停留在頁面 設(shè)頁面停留概率分布矢量平穩(wěn)分t+1時刻用戶在哪里p(t+1)=如果隨 的狀態(tài)滿p(t+1)=Mp(t)=p(t)為stationaryRankvectorrr Existenceand 關(guān)于PageRank的3個疑DoesthisDoesitconvergetowhatweAreresults收斂

來看兩個例 收斂得有意義PageRank遭遇的2個問Problem:Spidermisaspider .. Iteration0,1,2,AllthePageRankscoregets“trapped”innode Solution: solutionforspiderAteachtimestep,therandomsurferhastwoWithprob.β,followalinkatWithprob.1-β,jumptosomerandomCommonvaluesforβareintherange0.8toSurferwill eportoutofspidertrapwithinafewtimesteps隨機跳轉(zhuǎn) Y

yyyyyya 0A

1/21/201/31/3 0+1/31/3011/31/3yam隨機跳轉(zhuǎn)

1/31/21/2 0 + 0 yyamy1 a=1 .. m1 Problem:Dead路的網(wǎng)頁（死胡同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行為網(wǎng)頁 WebFirstAspeoplebegantousesearchenginestofindthingsontheWeb,thosewithcommercialintereststriedtoexploitsearchenginestobringpeopletotheirownsite–whethertheywantedtobethereornotShirt‐sellermightpretendtobeaboutTechniquesforachievinghighrelevance/importanceforaw TermBelievewhatpeoplesayaboutyou,ratherthanwhatyousayaboutyourselfPageRankasatooltomeasure“importance” WhyitShirt‐sellersayheisaboutmoviesdoesn’thelp,becauseothersdon’tsayheisaboutmoviesHispageisn’tveryimportant,soitwon’tberankedhighforshirtsormoviesvs.Spammers:Round becamethedominantsearchengine,spammersbegantoworkoutwaystoSpamfarmsweredevelopedtoconcentratePageRankonasinglepageLinkspam:CreatinglinkstructuresthatboostPageRankofaparticularpageLink 者觀點看，有3類網(wǎng)e.g LinkSpammer’s pageGetasmanylinksfromaccessiblepagesaspossibleto pagetConstruct“l(fā)inkfarm”togetPageRankmultipliereffectLink最常見和有效 農(nóng)場組織方式之采用統(tǒng)計方法分析文本e.gNa?veBayes類 郵件過濾的方檢查幾乎重復(fù)的頁檢測 農(nóng)場的頁Hidingvs.detectingspamfarms…(itisaTrustRank:topic-specificPageRankwitha eportsetof“trusted”pagesE.g. s, sfornon-USTrustRank:Basicprinciple:Approximate從web網(wǎng)上抽取一 網(wǎng)頁“seed這個任務(wù)很艱巨，somustmakeseedsetassmallaspossibleTrustSimpleModel:TrustWhyisitagood信 選 集集合大小的權(quán)需要人工檢查，所以保證所有好網(wǎng)頁以最短路徑抵達(dá)與集合；所以集合越大越好挑 集合的方 根據(jù)pagerank選擇k個頁面。原因 如.edu,.mil,.SpamIntheTrustRankmodel,westartwithgoodpagesandpropagatetrustComplementaryWhatfractionofapage’sPageRankcomesfromspampages?Inpractice,wedon’tknowallthespampages,soweneedtoestimateSpamMass HUBSANDHubsandHITS(Hypertext-InducedTopic目標(biāo):假設(shè)我們想要找到好報 Idea:Linkas In-link?Out-FindingHITS頁Authorities:報紙主課程主汽車制造商的主 報紙列表頁課程列表頁每個汽車廠商 頁Countingin-links:Countingin-links:ExpertQuality:聯(lián)合迭代定Hubsand

[KleinbergHubsandHubsand存在性與唯一ExampleofPageRankandPageRank和HITS是一個問題的兩種方ThedestiniesofPageRankandHITSpost-1998wereverydifferent本章小 HITS：導(dǎo)航頁 Pagerank稀疏矩條塊更面 的對 的ComputethePageRankofeachpage,assumingβ=0.8.eComputethetopic-sensitivPageRank,assumingtheeeportset(a)A(b)AandSupposetwospamfarmersagreetolinktheirspamfarms.How