personpagerank

Topic-SensitivePageRankPresentedby:BratislavV.
Stojanoviunimatrix0@live.
comUniversityofBelgradeSchoolofElectricalEngineeringPage1/29IntroductionTheWorldWideWebisgrowingrapidlyTherearemorethan100millionwebsitesandmorethan10billionpagesoverthere!
Wedidn'tmentionthecontentthatcannotbeindexedbystandardsearchengines(Deepweb)!
Forexample,ifwetypetheword"golf"insideGoogle,wewillendupwitharound456millionresults!
Othersearchengineswillyieldmoreorlessdifferentresults.
Why"Whatmakesthefoundationofthesearchengine""Whydowepreferonesearchengineoveranother"BratislavStojanovi(unimatrix0@live.
com)|Page2/29ProblemDefinition"HowcanwefindexactlywhatwewantontheWWWinafastandefficientmatter"Everysearchengineneedstorankpages,buthowBiggerthevaluemeansthepagehasmorecontentBiggerthevaluemeansquerywordsaremorefrequentBiggerthevaluemeansthepageismoreimportantEverypagehasitsownrankofimportance,butwhatisimportanceTrafficanalysisFinancialstatementanalysisLinkstructureanalysis$$$BratislavStojanovi(unimatrix0@live.
com)|Page3/29ProblemImportanceNearly90%oftraffictomostwebsitesisfoundbyusingasearchengineordirectoryBratislavStojanovi(unimatrix0@live.
com)|Page4/29WheredousersclickmoreoftenWhatwillbetheresultofthequery"golf"ProblemTrendOureverydaylifeisclutteredwithatonsofdifferentinformationsFindingarealinformationhasbecomeevenmoredifficultTherehasbeenacoupleofmillionnewwebsitesadded,onlyinthelastyear!
Googleisthemostpopularwebsite,andthesecondmostvisitedwebsiteontheplanet!
BratislavStojanovi(unimatrix0@live.
com)|Page5/29ExistingSolutionsHITS(Hyperlink-InducedTopicSearch)HyperSearchPageRankHilltopSALSA(StochasticApproachforLinkStructureAnalysis)TrustRankAndmanyothervariants…BratislavStojanovi(unimatrix0@live.
com)|Page6/29Solution#1:HITSHubsandAuthoritiesJohnM.
Kleinberg,CornellUniversity,NY,'98ReflectsthetimewhentheinternetwasoriginallyformingTwotypesofpages:HubsAuthoritiesHubpageprovideslinkstogoodauthoritiesonthesubjectAuthoritypageprovidesagoodinformationaboutthesubjectBratislavStojanovi(unimatrix0@live.
com)|Page7/29Solution#1:HITSCriticism:ExpensiveatruntimeScoresarecalculatedusingsubgraphoftheentireWebgraphSimpleanditerativeQuery-specificrankscoreBratislavStojanovi(unimatrix0@live.
com)|Page8/29Solution#2:PageRankLawrence"Larry"Page,SergeyBrin,Stanford,1998UsedbytheGooglesearchengineUsesarandomsurfermodelRepresentsthelikelihoodthatapersonrandomlyclickingonlinkswillarriveatanyparticularpageProbabilitydistributionisevenlydividedamongallpagesintheWebgraphPageRankvalueiscomputedforeachpageofflineInterpretsahyperlinkfrompageitopagejasavote,bypagei,forpagejAnalyzesthepagethatcaststhevoteaswellBratislavStojanovi(unimatrix0@live.
com)|Page9/29Solution#2:PageRank"Pageisimportantifmanyimportantpagespointtoit"SimplifiedPageRankformula:r=PR(G)Input:WebgraphG=(V,E)Output:RankvectorrLetGhavennodes(pages)In-linksofpagei:HyperlinksthatpointtopageifromotherpagesOut-linksofpagei:HyperlinksthatpointouttootherpagesfrompageiBratislavStojanovi(unimatrix0@live.
com)|Page10/29Solution#2:PageRankOriginalPageRankformula:Dampingfactord=0.
85Moregeneralformula:Recursivedefinition!
Equationoftheeigensystem,wherethesolutiontoPisaneigenvectorwiththecorrespondingeigenvalueof1ComputationcanbedoneusingpoweriterationmethodBratislavStojanovi(unimatrix0@live.
com)|Page11/29Solution#2:PageRankBratislavStojanovi(unimatrix0@live.
com)|Page12/29P1P2P3P4I11111I2I3I4I5111110.
330.
330.
330.
50.
51P1P2P3P4I11111I211.
830.
330.
83I3I4I511.
830.
330.
830.
330.
330.
330.
1650.
1650.
831.
83P1P2P3P4I11111I211.
830.
330.
83I31.
831.
3250.
330.
495I4I51.
3251.
830.
330.
4950.
610.
610.
610.
1650.
1651.
3250.
495P1P2P3P4I11111I211.
830.
330.
83I31.
831.
3250.
330.
495I41.
3251.
270.
610.
775I51.
271.
3250.
610.
7750.
4420.
4420.
4421.
270.
3050.
3050.
775P1P2P3P4I11111I211.
830.
330.
83I31.
831.
3250.
330.
495I41.
3251.
270.
610.
775I51.
271.
5220.
4420.
7471.
5221.
270.
4420.
747ConvergesDEPENDS!
Solution#2:PageRankCriticism:QueryindependentrankscoreRandomsurfermodelnotappropriateinsomesituationsPronetomanipulations(Googlebombs,linkfarms…)InexpensiveatruntimeScoresarecalculatedusingtheentireWebgraphAlgorithmhashooksfor"personalization"BratislavStojanovi(unimatrix0@live.
com)|Page13/29Solution#3:TrustRankGyngyi,Garcia-Molina,Pedersen,Stanford&Yahoo!
,2004LinkanalysisalgorithmFindsmotivationinPageRankmanipulationUsedtosemi-automaticallyseparateusefulwebpagesfromspamWebspampagesarecreatedonlywiththeintentionofmisleadingsearchenginesHumanexpertscaneasilyidentifyspampages,butit'stooexpensivetomanuallyevaluateeverythingBratislavStojanovi(unimatrix0@live.
com)|Page14/29Solution#3:TrustRankSelectasmallsetofseedpagestobeevaluatedbyanexpertNow,extendoutwardfromtheseedsetandseeksimilarpagesbyusinglinksAlternatively,wecanpickasmallsetofspampagesTRcanbeusedtocalculatespammassSpammassisthemeasureoftheimpactoflinkspammingonapagerankingInsteadofPR,wecalculateInversePR"Pagesarebadiftheylinktobadpages"BratislavStojanovi(unimatrix0@live.
com)|Page15/29Solution#3:TrustRankCriticism:Semi-automatedseparationofreputable,goodpagesfromspampagesIncontrasttoPR,TRdifferentiatesgoodandbadpagesBasedonagoodseedsetoflessthan200pages,resultshaveshownthatTRcaneffectivelyfilteroutspamBratislavStojanovi(unimatrix0@live.
com)|Page16/29ProposedSolutionTSPR(Topic-SensitivePageRank)TaherH.
Haveliwala,StanfordUniversity,2003"Personalized"versionofPageRankInsteadofcomputingasinglerankvector,whydon'twecomputeasetofrankvectors,oneforeach(basis)topicUsestheOpenDirectoryProjectasasourceofrepresentativebasistopics(http://www.
dmoz.
org)orYahoo!
Calculateintwosteps,fullyautomatically:Pre-processingQuery-processingPreprocessingstepiscalculatedoffline,justaswithordinaryPageRankBratislavStojanovi(unimatrix0@live.
com)|Page17/29IsitbetterQuery-specificrankscoreFullyautomatedMakeuseofcontextStillinexpensiveatruntimeBratislavStojanovi(unimatrix0@live.
com)|Page18/29IsitoriginalThefirsttopic-sensitivepersonalizationofPageRankSourceofideasformanyotherpossiblepersonalizationsTahergotajobatGoogleInc.
in2003asamemberofSearchQualityGroupCited994timesonGoogleScholarBratislavStojanovi(unimatrix0@live.
com)|Page19/29TrendSearchincontextandsemanticwebareverypopulartopicsnowadaysTheywillcertainlyplayasignificantroleinthenextstepoftheWorldWideWebevolutionTheSemanticWebasaglobalvisionhasremainedlargelyunrealizedThereisabeliefthatWeb3.
0willdramaticallyimprovethefunctionalityandusabilityofsearchenginesBratislavStojanovi(unimatrix0@live.
com)|Page20/29Topic-SensitivePageRank1/7PageRankformula:r=PR(G)Topic-SensitivePageRankformula:r=IPR(G,v)IPRstandsfor"Influenced"PageRankInput:WebgraphG=(V,E)InfluencevectorisavectorofbasistopicstOutput:ListofrankvectorsrItmapspageito:pageiimportance,WRTtopictiBratislavStojanovi(unimatrix0@live.
com)|Page21/29Topic-SensitivePageRank2/7Forthesakeofsimplicity,let'sconsidersomepageiandonly16topics(categories):WecanpickthemfromthefirstlevelofODPStep1isperformedonce,offline,duringWebcrawlItusesthefollowingiterativeapproach:BratislavStojanovi(unimatrix0@live.
com)|Page22/29Foreachtopiccjεv{//Part1:Calcvjvj[i]=0;if(iεpages(cj)){vj[i]=1/num(pages(cj))}//Part2:Calcrjrj[i]=IPR(W,vj[i]);}Topic-SensitivePageRank3/7BratislavStojanovi(unimatrix0@live.
com)|Page23/29Step2assumesthatwecalculatesomedistributionofweightsoverthe16topicsinourbasisOnlythelinkstructureofpagesrelevanttothequerytopicwillbeusedtorankpageiExample:Queryis"golf"Withnoadditionalcontext,thedistributionoftopicweightswewoulduseis:Topic-SensitivePageRank4/7BratislavStojanovi(unimatrix0@live.
com)|Page24/29Ifuserissuesqueriesaboutinvestmentopportunities,afollow-upqueryon"golf"shouldberankeddifferently,withthebusiness-specificrankvectorExample:Queryis"golf",butthepreviousquerywas"financialservicesinvestments"Distributionoftopicweightswewoulduseis:Topic-SensitivePageRank5/7BratislavStojanovi(unimatrix0@live.
com)|Page25/29Attheend,calculatethecompositePageRankscoreusingthefollowingformula:Interpretationofthecompositescore:WeightedsumofrankvectorsitselfformsavalidrankvectorThefinalscorecanbeusedinconjuctionwithotherscoringschemesTopic-SensitivePageRank6/7BratislavStojanovi(unimatrix0@live.
com)|Page26/29Topic:SportsTopic:SportsAfterawhile:P1(sports)=0.
895P1(business)=1.
2731111111P1P2P3P4P5P6P7I11111111I2Topic:BusinessTopic:Business11andsoon…Finally:P1(sports,business)==0.
55*0.
895+0.
85*1.
273=0.
533110.
330.
330.
330.
330.
330.
3310.
330.
330.
33P1P2P3P4P5P6P7I11111111I2110.
330.
660.
331.
331.
33P1P2P3P4P5P6I1I2P1P2P3P4P5P6I1111111I2110.
330.
660.
331.
331.
331111P1P2P3P4P5P6I1111111I2………………Topic-SensitivePageRank7/7BratislavStojanovi(unimatrix0@live.
com)|Page27/29ConclusionImplicitlymakesuseofIR(InformationRetrieval)indeterminingthetopicofthequeryHowever,thisuseofIRisNOTvulnerabletomanipulation,becauseODPiscompiledbythousandsofvolunteereditorsUsingasmallbasissetisimportantforkeepingthequery-timecostslowFuturework:UsefinergrainedbasissetWeightingschemebasedonpagesimilaritytoODPcategory,ratherthanpagemembershiptoODPcategoryBratislavStojanovi(unimatrix0@live.
com)|Page28/29QuestionsandDiscussionBratislavStojanovi(unimatrix0@live.
com)|Page29/29Yes