SRP om videnskaben bag Google | Matematik A og Dansk A

Uddrag

Indledning
Hvad er ideen bag Googles pageranking algoritme? Hvordan har Sergey Brin og Lawrence Page båret sig ad, med at skabe en så revolutionerende måde at sortere alle internettets websider?

Før Google blev lanceret, havde man ingen søgemaskine, der kunne behandle alle internettets mange websider. Søgemaskinen behandlede på daværende tidspunkt kun en brøkdel af alle de eksisterende websider, og sorteringen foregik efter emne, som var det et bibliotek. Det var langt fra optimalt. Derfor tog Sergey Brin og Lawrence Page opgaven om at skabe den optimale søgemaskine op. De skulle altså skabe en algoritme, som kunne behandle alle websider og samtidig sortere dem. De måtte altså først finde ud af, hvordan de skulle rangere disse milliarder af websider, finde ud af hvad man skulle rangere efter. De fandt frem til, at en websides pagerank afhænger af websidens vigtighed.

I første del af opgaven beskrives det, hvordan man matematisk kan bestemme en given sides pagerank. Opgaven forklarer, hvordan Sergey Brin og Lawrence Page kom frem til den endelige pagerank algoritme, som Google benytter den dag i dag. Derudover beskrives de komplikationer, de mødte på vejen til det endelige produkt.

I anden del af opgaven formidles den matematiske undersøgelse til et bredere publikum ved hjælp af en populærvidenskabelig artikel. Her beskrives ideen bag Googles pagerank algoritme og grundstenene for den. Ydermere reflekteres der over, hvilke retoriske og stilistiske overvejelser der ligger til grund for den populærvidenskabelige artikel.
____________

Matematikken bag Googles pageranking algoritme
Søgemaskinen Google blev hurtigt enormt populær og er stadig den mest anvendte søgemaskine på nettet . Det er den, fordi den revolutionerende pagerank algoritme var blandt grundstenene til den.

Formlen for pagerank
Før man kan udlede en matematisk formel for pagerank af en given webside, skal man bestemme, hvordan vigtigheden af den enkelte webside beskrives. Her anvendte man sine erfaringer fra naturvidenskab om, at hvis en artikel havde mange henvisninger og referencer i andre artikler, så var det en god artikel. Derudfra kunne man sige, at en webside er vigtig, hvis andre websider linker til den. På figur 1 ses et miniatureinternet, hvor A, B, C og D, indikerer hver sin webside, og pilene repræsenterer et link fra den ene webside til den anden. Så vil man altså beskrive vigtigheden, I, af siderne ved: I(A)=2,I(B)=1,I(C)=2 og I(D)=1.

Det ses at en websides pagerank er et tal. På denne måde tages der ikke højde for at en knap så vigtig side opnår troværdighed og dermed en højere vigtighedsscore, hvis en vigtig side linker til den. F.eks. burde websiden D have en højere score, da C linker til den.

Nu kan en formel udledes. Vigtigheden af en webside er defineret, samtidig med at der skal tages højde for en websides troværdighed. Samlet finder man en sides pagerank. Altså er en given side, Pi, pagerank givet ved I(P_i ). Hvis en anden webside, P_j, har l_j links og et af de l_j'te links, linker til Pi, så .....
____________

Googlematricen skabes
Førhen har vi bestemt en websides pagerank, ud fra hvor mange der linker til siden. Derefter tilføjede vi, at en websides pagerank vil stige, hvis en vigtig side linker til en mindre vigtig side, dermed fik en sides troværdighed også indflydelse på en websides pagerank. Til sidst vil vi give brugerne af internettet indflydelse på pageranken af en webside. Det gør man for at gøre pagerank algoritmen så objektiv og demokratisk som muligt. Man ønsker selvfølgelig også at kunne svare ja på spørgsmålene nævnt i slutningen af sidste afsnit.
Nu vil vi altså skabe Googlematricen, som er defineret som G=(g_ij ). Den tidligere information har ikke været forgæves, tværtimod, vi bygger nemlig videre på hyperlinkmatricen H. Nu vil vi altså bare konstruere en matrix, G, og løse ligningen:

GI=I

Her er vektor I den endelige pagerank vektor. For at give brugeren en stemme i bestemmelsen om, hvilke websider der er vigtige, surfer vi tilfældigt rundt på nettet, som en bruger ville gøre det. Lad os sige, at brugeren starter på siden P_j, som har l_j links. Et af disse links linker til siden P_i. Brugeren vil klikke sig ind på et af de l_j'te links, hvor sandsynligheden for at brugeren rammer P_i, vil være 1/l_j . Med denne tanke kan man beskrive pagerank I(P_j ) som sandsynligheden for, at brugeren tilfældigt kommer forbi siden P_j, når der surfes rundt på må og få. F.eks. hvis man skal skrive en større opgave og søger dybdegående information om et specifikt emne, så ender man med garanti på nogle af de samme sider flere gange. Dermed giver brugerne af internettet disse sider en højere pagerank. Problemet er bare, hvis denne tilfældige surfetur ender på en webside uden nogen links. For at komme videre med tanken før, betragter man siden uden nogen links som en side, der linker til alle nettes sider, altså n. Hvis vi så med det ovenstående skal modificere H, vil det sige, at den søjle der repræsenterer websiden uden links, nu har 1/n i hver indgang i stedet for 0. Den modificerede hyperlinkmatrice kaldes nu S:

S=H+A

H er stadig hyperlinkmatricen. A er en matrix af samme dimension som H, og den har 0 i alle de søjler, hvor H repræsenterer en webside med links til andre sider, men 1/n i hver indgang i en søjle hvor H repræsenterer en websider uden links.
Man bliver også nødt til at tage højde for, hvis brugen på den tilfældige surfetur ikke vælger at klikke videre på et af de l_j'te links. For at beskrive dette matematisk indføres α. Alfa er et tal mellem 0 og 1, som skildrer sandsynligheden for, om brugeren er vejledt af S og vælger et af de l_j'te links eller ender
____________

Videnskaben bag Google beviser:
Derfor er søgemaskinen Google uovervindelig
Skaberne bag Google er de første, der skaber en søgemaskine, der kan behandle alle internettets websider. Samtidig er Google først til at sortere siderne efter vigtigheden af den enkelte side i stedet for at fortage en kategorisering af siderne. Dette skyldes Googles pagerank algoritme.

Hele verden kender til Google. Mange computere bruger den velkendte søgemaskine og dens tilhørende søgefelt som startside. Hvorfor gør man det? Det gør man, fordi den er smart, ikke mindst i dens minimalistiske design, men også i dens egentlige funktion. Den kan søge blandt alle websider i det ellers uendelige univers af websider på en brøkdel af et sekund, og vigtigst af alt kan den vise de mest relevante resultater først. Med dens sublime egenskaber var Google enormt revolutionerende, da det blev lanceret i 1997. Ingen havde før set noget lignede. Man kan nu undre sig over, hvad der ligger bag dette mesterværk, og hvordan det overhovedet er muligt at sortere siderne, så de mest relevante resultater kommer først. Dette muliggjorde Sergey Brin og Lawrence Page med deres pagerank algoritme. En algoritme der rangerer de mest relevante sider, når man søger i Google.

De allerede eksisterende søgemaskiner
Der fandtes allerede søgemaskiner, inden Google blev opfundet. De byggede bare på et andet princip. Samme princip som et bibliotek gør, da personer kategoriserede nogle websider og var i stand til at placere den enkelte webside inden for en bestemt kategori.
På den ene side var denne kategorisering af websiderne praktisk, men på den anden side var den yderst uhensigtsmæssig. Uhensigtsmæssig fordi det var menneskers subjektive vurdering, om en webside skulle høre til en bestemt kategori eller ikke. Derudover var det kun en brøkdel af de mange milliarder websider, som blev kategoriseret. Det var simpelthen ikke ...... Køb adgang for at læse mere Allerede medlem? Log ind