College 9-10 Crawlers en Page Rank PDF

College 9 25-11-2024 Page rank:  hoge autoriteit als er veel links naar jou zijn idee achter HITS: hubs and Authorities:  list pages (hub) bevatten goede information  hubs verwijzen naar pagina’s met hoge autoriteit, ze bevatten zelf niet autoritaire informatie  twee w...

College 9 25-11-2024 Page rank:  hoge autoriteit als er veel links naar jou zijn idee achter HITS: hubs and Authorities:  list pages (hub) bevatten goede information  hubs verwijzen naar pagina’s met hoge autoriteit, ze bevatten zelf niet autoritaire informatie  twee waarden die een pagina heeft: o autority: aantal links die wijzen naar de pagina o hub value: aantal links die vertrekken van de pagina (verwijzen naar een andere pagina)  bij pagerank wordt hub value gestraft  wordt vaak maar op een deel van de documenten toegepast, niet op alle hoe werkt het:  gegeven een tekst query, krijg je een index naar alle pagina’s die deze query bevatten -> dit geeft de Root set  voeg alle pagina’s toe die: o verwijzen naar een pagina in de root set o of pagina’s waar naar wordt verwezen vanuit de root set  de pagina’s die uit de rootset met deze aanvullende pagina’s komen zijn de base set Grap G = (S,E) waar S is de base set  hub score is gebaseerd op autority score van pagina’s die naar jou verwijzen  Autority score is gebaseerd op hub score van pagina’s die naar jou verwijzen  Normalisatie is nodig omdat er anders oneindige iteraties ontstaan Wikipedia is een voorbeeld van een site met een hoge hub en autoriteits score, door veel inkomende en uitgaande links Je kan HITS toepassen maar dan moeten alle pagina’s in de baseset staan Waarom gebruikt Google page rank en niet HITS?  Zo gebruiksvriendelijk mogelijk. Page rank geeft een makkelijk overzicht met beste keuze boven aan  HITS voor iedere query is erg kostelijk Hoeveel inkomende links verwacht je bij pagina’s?  Distributie: Snelle afname en steeds minder  Wegen meer een poisson distributie  Vliegvelden een andere distributie  Distribution volgens een power law  Netwerken worden ook wel scale-free networks genoemd Small-world network:  Het aantal mensen wat bijvoorbeeld nodig is om iedereen te bereiken  Zoals kevin bacon: wanneer iemand samen met hem in een film heeft gespeeld bacon number one, als iemand samen speelt met iemand anders die met hem heeft gespeeld beacon number 2 etc.  Clustering coefficient: voor small world networks: clustering coefficient + pad afstand  Kleinere graaf  Hoge clustering  Korte gemiddelde afstand College 10 28-11-2024 Crawler: tool om webpagina’s uit te lezen Web engines moeten hun documenten crawlen Stappenplan crawlen:  URL’s initializeren  Herhalen: o URL ophalen uit pool  o Fetch and parse pagina o Forward page content to the indexer o Extract URLs van pagina o Add URLS aan pool Problemen simpele crawler:  Je moet heel veel pagina’s door  Onmogelijk zonder parallellisatie (meerdere crawlers)  Niet iedere crawl van een pagina is succesvol Politeness:  Vermijden van denial of service attack: Sommige kleinere sites kunnen niet zo veel vraag aan  volg robots.txt van de site op, dit zijn een soort huishoud regels voor de crawler hoe te gedragen op de site -> deze catchen van iedere site die je crawlt o site/robot.txt freshness:  sommige websites (zoals nieuws sites) moeten vaker gecrawld worden  andere pagina’s hoeven niet zo vaak opnieuw gecrawld te worden Robustness:  We willen geen duplicatie in de content  Bijvoorbeeld max 3 kopieën accepteren in de index Kwaliteiten van goede crawler:  Scalable: crawl vergroten door meer machines (parallalisation)  Polite: niet te vaak een site bezoeken en robots.txt  Fresh: refresh belangrijke pagina’s  Robust: niet de index overblowen met de veel kopieën URL Frontier: managed welke data is gezien en welke nog niet  Sommige pagina’s hebben hogere prioriteit om als eerste bezocht te worden  Indexen gebeurt op basis van hoogste pagerank Hoe controleer je of contex al in index zit?  Document vingerpring -> je maakt een soort samenvatting, als deze overeen komen dan zie je het als dezelfde content  Documenten overslaan die al in de index staan  Je kan ook een timestamp toevoegen, alleen toevoegen als timesamp is ouder dan … bijvoorbeeld Distributie van crawlers:  Wereldwijd verspreiding van crawlers  url opslaan het dichts bij locatie, vb.nl indexen in een crawler in NL taak waar url frontier op moet letten:  politness  freshness URL frontier:  Front queues managet prioritering o Prioritering tussen 1 en F o Voegt URL toe aan de juiste queue o Heuristieken om prioriteit te bepalen: refresh rate, pagerank etc o Wordt aangevraagt door back queue  Back queue dwingt politeness af o Nooit helemaal leeg o URLS van dezelfde host in elke queue o Houd te tijd bij wanneer een host weer opgeroepen kan worden