UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
POU ˇ CEVANJE, PREDMETNO POU ˇ CEVANJE
GREGOR SPA ˇ CAL
MATEMATI ˇ CNO OZADJE ALGORITMA PAGERANK
MAGISTRSKO DELO
LJUBLJANA 2016
UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
POU ˇ CEVANJE, PREDMETNO POU ˇ CEVANJE
GREGOR SPA ˇ CAL
MATEMATI ˇ CNO OZADJE ALGORITMA PAGERANK
MAGISTRSKO DELO
MENTOR: red. prof. dr. ALEKSANDER MALNI ˇ C SOMENTOR: doc. dr. ROK POˇ ZAR
LJUBLJANA 2016
Mentorju red. prof. dr. Aleksandru Malniˇcu in somentorju doc. dr. Roku Poˇzarju
hvala za nasvete, vodenje, ˇcas in strokovno pomoˇc pri nastajanju magistrskega dela.
Zeni, druˇˇ zini in prijateljem
hvala za vso podporo, razumevanje in potrpeˇzljivost. Posebej bi se rad zahvalil svoji ˇzeni Nikiti za vso spodbudo in pomoˇc.
Povzetek
PageRank je Googlov algoritem za rangiranje spletnih strani po pomembnosti. Strani lahko glede na vrednost PageRanka hierarhiˇcno uredimo in tako omogoˇcimo boljˇse rezul- tate iskanja na spletu.
V magistrskem delu obravnavamo pomen, lastnosti in delovanje spletnega iskanja.
Predstavljamo slabosti spletnega iskanja, ki so se pojavljale pred nastankom Googla. Eno najpomembnejˇsih vpraˇsanj je zagotovo to, ali lahko delovanje PageRanka formalno ma- tematiˇcno utemeljimo ter katere matematiˇcne koncepte in teorije za to potrebujemo. Za konec predstavimo primer implementacije algoritma v obliki spletne aplikacije in s tem pokaˇzemo njegovo delovanje na preprostem primeru spleta.
V magistrskem delu torej predstavimo matematiˇcno ozadje delovanja algoritma Pa- geRank, za kar potrebujemo teoretiˇcno znanje s podroˇcja linearne algebre in teorije grafov.
Poleg formalnega matematiˇcnega opisa ilustriramo tudi njegovo delovanje na primerih.
Splet modeliramo z usmerjenim grafom, ki mu priredimo neko matriko. Rezultat algo- ritma PageRank pa je lastni vektor te matrike pri lastni vrednosti 1, ki ga izraˇcunamo s pomoˇcjo potenˇcne iterativne metode. Obravnavamo tudi teˇzave, ki lahko nastanejo pri raˇcunanju: ali je rezultat potenˇcne metode vedno smiseln, ali je lahko reˇsitev za dani primer veˇc in ali je rezultat odvisen od zaˇcetnih parametrov.
Glavni namen tega magistrskega dela je podati konkreten in ˇsirok vpogled v sple- tno iskanje s poukarkom na PageRanku, tako iz zgodovinskega, raˇcunalniˇskega kot ma- tematiˇcnega vidika, in poiskati ustrezne zglede za ilustracijo delovanja, teˇzav in reˇsitev potenˇcne iterativne metode. Algoritem PageRank je tako predstavljen celostno na nivoju, primernem za tiste, ki jim spletno iskanje, linearna algebra in teorija grafov niso tuji, vendar se z nekaterimi zahtevnejˇsimi pojmi in koncepti ˇse niso spoznali.
MSC (2010) klasifikacija: 05C20, 15A18, 15B48, 15B51
Kljuˇcne besede: algoritem PageRank, spletno iskanje, matematika algoritma PageRank, Google, rangiranje spletnih strani
Abstract
PageRank is Google’s algorithm for ranking web pages by relevance. Pages can then be hierarchically sorted in order to provide better search results.
The MSc thesis considers functioning, relevance, general properties of web se- arch and its weaknesses before the appearance of Google. One of the most important questions is, if we can formally explain the mathematics behind PageRank algorithm and what mathematical knowledge is necessary. Finally, we present an example of its implementation in a form of a web application, to demonstrate how PageRank works on a form of simplified web.
The MSc thesis presents the mathematics behind PageRank algorithm. To this end, we need linear algebra and graph theory. Beside formal mathematical description of the algorithm, we also provide examples to illustrate how it works.
Web is modeled as a directed graph, to which we assign a certain matrix. The result of PageRank, performed on this matrix, is the eigenvector, corresponding to matrix’s eigenvalue 1. The eigenvector is calculated with power iteration method.
We consider problems, that can occur during the calculation: does the result of the power iteration method always make sense, can there be more than one solution for a given example and does the result depend on the starting parameters.
The major objective of this thesis is to provide a wide and concrete insight into web search, emphasising PageRank, considering historical, mathematical and com- puter science viewpoint. We wish to provide relevant examples to demonstrate how the algorithm works. With these examples we also try to demonstrate problems as well as solutions that can occur during calculation with the power iteration method.
PageRank is presented comprehensively in a way suitable for those familiar with basic knowledge in web search, linear algebra and graph theory, yet still in need of an introduction to some advanced concepts.
MSC (2010) classification: 05C20, 15A18, 15B48, 15B51
Key words: PageRank algorithm, web search, the mathematics behind PageRank algorithm, web page ranking
Kazalo
1 Uvod 1
2 Spletni iskalnik 5
2.1 Zgodovina iskanja . . . 5
2.1.1 Pridobivanje informacij . . . 6
2.2 Spletni iskalnik . . . 7
2.2.1 Kaj je spletni iskalnik? . . . 7
2.2.2 Delovanje spletnega iskalnika . . . 8
3 Google 13 3.1 Spletno iskanje pred Googlom . . . 13
3.2 Razvoj algoritma PageRank . . . 14
3.2.1 O avtorjih algoritma . . . 14
3.2.2 Motivacija za razvoj . . . 14
3.3 Poizvedbeno neodvisno doloˇcanje pomembnosti . . . 15
3.4 Neformalni opis delovanja PageRanka . . . 15
4 Teoretiˇcne osnove 19 4.1 Teoretiˇcne osnove s podroˇcja linearne algebre . . . 19
4.2 Teoretiˇcne osnove s podroˇcja teorije grafov . . . 27
5 Matematiˇcna utemeljitev delovanja 31 5.1 Formalni opis . . . 31
5.2 Raˇcunanje rangov s potenˇcno iterativno metodo . . . 34
5.3 Teˇzave potenˇcne metode in njihove reˇsitve . . . 36
5.3.1 Ali zaporedje vektorjev vedno konvergira k smiselni vrednosti? 37 5.3.2 Ali je reˇsitev enoliˇcna? . . . 39
5.3.3 Ali je konvergenca odvisna od izbire zaˇcetnega pribliˇzka? . . . 40
6 Implementacija algoritma 45 6.1 HTML5 in Paper.js . . . 45
6.1.1 HTML5 . . . 45
6.1.2 JavaScript in Paper.js . . . 46
6.2 Razvoj aplikacije . . . 46
6.2.1 Opis programske kode in osnovne podatkovne strukture . . . . 47
6.2.2 Risanje vozliˇsˇc . . . 47
6.2.3 Risanje povezav . . . 48
6.2.4 Implementacija potenˇcne iterativne metode . . . 49
6.3 Navodila za uporabo . . . 51
6.4 Uporabe aplikacije in moˇznosti nadaljnjega razvoja . . . 52
7 Zakljuˇcek 55
Literatura 57
Slike
2.1 Shema elementov spletnega iskalnika. . . 11
3.1 Primer spleta, modeliranega z usmerjenim grafom. . . 15
4.1 Primer usmerjenega grafa na petih vozliˇsˇcih. . . 28
5.1 Primer omreˇzja ˇstirih spletnih strani, modeliranega z usmerjenim gra- fom. . . 33
5.2 Graf omreˇzja na treh vozliˇsˇcih. . . 36
5.3 Graf omreˇzja, za katerega je vektor x nesmiseln. . . 37
5.4 Graf omreˇzja z dodanimi povezavami (ˇcrtkane povezave). . . 38
5.5 Graf omreˇzja, katerega reˇsitev ni enoliˇcna. . . 39
5.6 Graf omreˇzja na treh toˇckah. . . 40
6.1 Izgled aplikacije ob zagonu. . . 47
6.2 Povezava med dvema vozliˇsˇcema na Canvasu. . . 48
Poglavje 1 Uvod
Tema, ki jo obravnava magistrsko delo, prepleta dve podroˇcji: matematiko in raˇcunalniˇstvo, bolj natanˇcno, algebro in spletno iskanje. Algebra je ena kljuˇcnih vej matematike in se ukvarja s ˇstudijem manipulacije abstraktnih simbolov in reˇsevanjem enaˇcb. ˇCeprav zaˇcetki algebre segajo celo do antike, je za nas pomemben razvoj al- gebre v 19. stoletju. Veliki matematiki, kot so Augustin-Louis Cauchy (1789-1857), Sir William Rowan Hamilton (1805-1865), Ferdinand Georg Frobenius (1849-1917) in drugi, so v svojih delih postavili temelje podveje algebre, imenovane linearna alge- bra. Tu se prviˇc pojavi pojem matrika, ki je ponovno sproˇzil nastanek nove podveje algebre – teorije matrik. Prav razvoj te teorije predstavi pojma lastna vrednost in lastni vektor, to pa je pravzaprav tudi osnova matematiˇcne plati tega magistrskega dela. Omenimo ˇse letnico 1929 in ime Richard von Mises (1883-1953). Von Mises je predstavil prvi numeriˇcni algoritem za raˇcunanje lastnih vrednosti in lastnih vek- torjev, imenovan potenˇcna metoda [12].
Raˇcunalniˇski del magistrskega dela je povezan pravzaprav z enim najbolj pr- vinskih pojavov v naravi, to je z iskanjem. Bolj konkretno je fokus raziskovanje spletnega iskanja. Spletno iskanje je relativno nov pojem, ki se je pojavil z na- stankom svetovnega spleta leta 1989. Spletno iskanje je ena najbolj dobiˇckonosnih industrij na svetu in ˇse vedno raste. Najveˇcji predstavnik te industrije je podjetje Google. ˇCeprav se podjetje danes ukvarja z mnogimi razliˇcnimi dejavnostmi, se je vse zaˇcelo ravno s spletnim iskanjem. Ustanovitelja Googla, Larry Page in Sergey Brin, sta leta 1998 predstavila svoj model spletnega iskalnika. Osrednji del iskalnika je algoritem za hierarhiˇcno urejanje spletnih strani po pomembnosti, imenovan Pa- geRank, ki temelji na iskanju doloˇcenega lastnega vektorja. Za iskanje tovrstnega vektorja pa se uporablja prav omenjena potenˇcna metoda. Tako sta Page in Brin s pomoˇcjo skoraj 70 let stare metode ustvarila nekaj, kar je pravzaprav spremenilo svet [1, 3].
1
2 POGLAVJE 1. UVOD
Zavedati se moramo, da je blagovna znamka Google v manj kot dvajsetih letih obstoja postala z 85,5 milijardami ameriˇskih dolarjev druga najbolj vredna znamka na svetu, celo pred Microsoftom [13]. Po drugi strani je beseda Google v obliki glagola guglati/googlati (iskati informacije na spletu s pomoˇcjo spletnega iskal- nika Google) postala ne le del pogovornega jezika, ampak celo Slovarja slovenskega knjiˇznega jezika. Ravno zaradi vpliva Googla, je le-ta postal zanimiv za raziskova- nje. Matematiki so se tako podali v raziskovanje delovanja algoritma PageRank, da bi pojasnili, zakaj pravzaprav deluje.
V okviru ˇstudija na dodiplomski stopnji nismo veliko ˇcasa posveˇcali spletnemu iskanju oziroma bolj natanˇcno PageRanku. Smo pa spoznali dovolj linearne algebre, da se lahko lotimo vpraˇsanja, kako le-ta deluje z vidika linearne algebre. Tako kot sta Page in Brin skozi raziskovanje odkrivala in odpravljala teˇzave, tudi mi v nadaljeva- nju ugotavljamo, da mora biti za ustreznost delovanja PageRanka izpolnjenih nekaj pogojev. PageRank se namreˇc izvaja na matriki, ki mora imeti doloˇcene lastnosti, da je njen lastni vektor za lastno vrednost 1 ravno vektor vrednosti PageRanka. Tu pa se sreˇcamo s koncepti iz linearne algebre, ki jih tekom ˇstudija ˇse nismo spoznali.
Opremo se na teorijo pozitivnih matrik in Perron-Frobeniusov izrek ter spoznamo lasnosti stohastiˇcnih matrik. Da bi splet ustrezno modelirali, se naveˇzemo ˇse na teorijo grafov. S pomoˇcjo usmerjenih grafov in lastnosti krepko povezanih usmerje- nih grafov tako uspemo modelirati splet v obliki, ki je omogoˇcila aplikacijo znanja linearne algebre, in pokazati ustreznost delovanja algoritma PageRank.
V magistrskem delu se najprej sprehodimo skozi zgodovino iskanja, od njegovih zaˇcetkov pa vse do danes. S tem spletno iskanje kronoloˇsko umestimo in ga loˇcimo od tako imenovanega klasiˇcnega iskanja. V nadaljevanju poglavja na sploˇsno predsta- vimo model spletnega iskalnika in delovanje vsakega od gradnikov, kar nas pripelje do trenutka, ko uporabnik vnese poizvedbo v spletnem brskalniku. V tretjem poglavju predstavimo Google. Da bi laˇzje razumeli, kaj je Pagea in Brina motiviralo za razvoj PageRanka, najprej opiˇsemo razvoj iskanja pred Googlom. Sledi predstavitev obeh avtorjev in opis razvoja PageRank algoritma. Za laˇzjo predstavo delovanja algoritma poglavje vsebuje ˇse njegov neformalni opis. V ˇcetrtem poglavju obravnavamo teo- retiˇcne osnove, ki so potrebne za formalni opis delovanja algoritma. Poglavje loˇcimo na dva dela glede na podroˇcje, ki ga razdelek obravnava. S podroˇcja linearne algebre vpeljemo pojme, kot so nenegativen vektor, nenegativna in pozitivna matrika, spek- ter, spektralni radij, norma in (ne)razcepnost matrike. Razdelek vsebuje dokaz zelo pomembnega Perronovega izreka, ki ga kasneje dopolnimo in dokaˇzemo pod imenom Perron-Frobeniusov izrek. S podroˇcja terorije grafov predstavimo osnovne lastnosti
3 usmerjenih grafov in pojem matrika sosednosti grafa. Preko lastnosti usmerjenih grafov, ki ji reˇcemo krepka povezanost, pokaˇzemo, da je razcepnost matrike sose- dnosti odvisna od tega, ali usmerjeni graf to lastnost ima ali ne. V petem poglavju uporabimo rezultate iz ˇcetrtega, da dokaˇzemo ustreznost delovanja algoritma Pa- geRank. Najprej algoritem formalno opiˇsemo in idejo ilustriramo na zgledih. V razdelku 5.1 prviˇc interpretiramo rezultat, ki ga vrne PageRank, kot lastni vek- tor neke matrike. Kot metodo za raˇcunanje tega lastnega vektorja pa predstavimo potenˇcno iterativno metodo. Poglavje obravnava tudi teˇzave, ki nastanejo pri izva- janju te metode, ter njihove reˇsitve. Na koncu dokaˇzemo, da je Googlova matrika ustrezno definirana in ima vse lastnosti, da je rezultat potenˇcne iterativne metode, torej lastni vektor pri lastni vrednosti 1, pravi. ˇSesto poglavje vsebuje opis razvoja aplikacije za raˇcunanje PageRanka za dano omreˇzje. Najprej predstavimo orodja, uporabljena za razvoj, nato pa ˇse kljuˇcne korake razvoja. Kot zadnje predstavimo ˇse moˇznosti nadaljnjega razvoja aplikacije in njene uporabe.
Za raziskovanje se opremo predvsem na tujo literaturo in zapiske predavanj, ki so nastali med ˇstudijem. Za razvoj aplikacije smo uporabili jezika HTML5 in JavaScript. Literatura, ki bi celostno obravnavala algoritem PageRank in njegovo matematiˇcno utemeljitev, ga predstavila na zgledih in podala primer implementacije, namreˇc v naˇsem prostoru praktiˇcno ˇse ne obstaja.
Tako je eden glavnih ciljev magistrskega dela celostno predstaviti PageRank na nivoju, primernem za bralca, ki mu linearna algebra in teorija grafov nista tuji, vendar se z nekaterimi zahtevnejˇsimi pojmi in koncepti ˇse ni sreˇcal. Primer imple- mentacije pa lahko bralcu sluˇzi za nadaljnji razvoj in raziskovanje. S tem ponujamo konkreten in ˇsirok vpogled v delovanje spletnih iskalnikov in matematiˇcno uteme- ljitev njihovega delovanja. Hkrati ˇzelimo dati bralcu vpogled v pomembnost in prisotnost matematike za razvoj raˇcunalniˇskih znanosti.
Poglavje 2
Spletni iskalnik
V tem poglavju se bomo na kratko sprehodili skozi zgodovino iskanja, definirali, kaj sploh je spletni iskalnik, opisali njegove lastnosti, predstavili njegovo delovanje.
Tekom celega poglavja izhajamo iz [1] in [3].
2.1 Zgodovina iskanja
V resnici ne bomo govorili o katerem koli iskanju oziroma iskanju ˇcesar koli, ampak o iskanju oziroma pridobivanju informacij. Pridobivanje informacij (angl.
information retrieval) je proces iskanja doloˇcene informacije v naboru dokumentov.
Zahtevi po pridobitvi informacije, ki jo poˇsljemo iskalniku, reˇcemo poizvedba (angl.
query). Preden smo pojem iskalnik povezovali skoraj izkljuˇcno z raˇcunalnikom, pa je to pomenilo osebo – knjiˇzniˇcarja, arhivarja . . .
Ceprav zaˇˇ cetke zapisovanja informacij pripisujemo ˇze jamskemu ˇcloveku, se je zbiranje informacij v pravem pomenu besede zaˇcelo ˇsele v antiki. Stari Grki in Rimljani so svoje informacije zapisovali na papirusove zvitke. Nekateri izmed njih so imeli nekakˇsne oznake, na katerih so bili zapisani kratki povzetki vsebine dokumentov. V tem ˇcasu se je v kontekstu iskanja informacij pojavil ˇse en element – kazalo. Iz tega ˇcasa nam je verjetno najbolj poznana knjiˇznica iz Aleksandrije, ki naj bi hranila celo do 700.000 takih zvitkov.
Ceprav je izum pergamenta pripeljal do knjig, se bomo bolj osredotoˇˇ cili na pa- pir in izum tiskalnega stroja, ki sta od 15. stoletja dalje zares omogoˇcila hitro rast zbirk dokumentov. Z rastjo knjiˇznic pa se je pokazala potreba po organizaciji doku- mentov, in sicer hierarhiˇcno po vsebini. Sprva je bilo vse odvisno od knjiˇzniˇcarja, ki si je moral vse to zapomniti. ˇSele v 20. stoletju so mu delo olajˇsali pripomoˇcki, kot sta na primer mikrofilm in MARC (MAchine Readable Cataloging). Konˇcno je izum raˇcunalnika omogoˇcil, da iskanje ni bilo veˇc v rokah ljudi, temveˇc raˇcunalniˇskih iskal-
5
6 POGLAVJE 2. SPLETNI ISKALNIK nih sistemov. Kljub temu iskanje ni bilo dovolj enostavno, da bi ga lahko opravljal vsak, ampak le posebej izˇsolane osebe.
Pravo revolucijo v svetu iskanja informacij pa je leta 1989 prinesel Tim Berners- Lee z izumom World Wide Weba. Ravno ta izum predstavlja dokonˇcen konec indu- strijske dobe in prevlado informacijske dobe. Vendar iskanje ni uspelo slediti rasti svetovnega spleta. Iskalnik je za vsako poizvedbo vrnil na tisoˇce strani, ki so bile povsem neurejene, uporabnik je moral nato sam presoditi, katera je zanj relevantna in katera ne.
To se je spremenilo leta 1998, ko se je za pridobivanje informacij zaˇcela uporaba analize povezav (angl. link analysis). Najuspeˇsnejˇsi iskalniki so izokriˇsˇcali strukturo spleta, ki je povezan s hiperpovezavami, in tako drastiˇcno izboljˇsali kvaliteto iskanja.
Med te iskalnike spada tudi Google, ki od leta 2004 zaseda vodilno mesto med spletnimi iskalniki. Preden se lotimo opisa delovanja spletnega iskalnika, opiˇsimo nekaj metod pridobivanja informacij.
2.1.1 Pridobivanje informacij
Pred spletnim iskanjem so se raˇcunalniki uporabljali tudi za tako imenovano klasiˇcno iskanje, zato je na tem mestu smiselno predstaviti razlike med obema.
Klasiˇcno iskanje navadno poteka v zbirki dokumentov, ki je manjˇsa, bolj obvladljiva in nepovezana. Primer takega iskanja je recimo iskanje knjige v knjiˇznici. Spletno iskanje pa poteka na najveˇcji povezani zbirki dokumentov na svetu. Kljuˇcni razliki sta torej velikost in (ne)povezanost. Na kratko predstavimo tri najpomembnejˇse metode klasiˇcnega iskanja, ki so bile osnova za spletno iskanje. Podroben opis bralec najde v [1].
Iskanje s pomoˇcjo Booleove algebre
Uporaba Booleove algebre za iskanje informacij predstavlja eno prvih in naj- enostavnejˇsih metod za pridobivanje informacij. Deluje tako, da iˇsˇce dokument, ki se popolnoma ujema z uporabnikovo poizvedbo. V ozadju se uporablja Booleova algebra, kar pomeni, da so besede v poizvedbi povezane z logiˇcnimi vezniki in, ali inne, moˇzni vrednosti pa sta zgolj 0 in 1. Z drugimi besedami, dokument se s poi- zvedbo ujema ali ne. Bralec lahko podrobnosti najde v [1]. Sam iskalnik deluje tako, da primerja uporabnikovo poizvedbo z naslovom, kljuˇcnimi besedami ali povzetkom posameznega dokumenta, in glede na ujemanje doloˇci ustreznost dokumenta. Ena izmed teˇzav je, da tako iskanje vraˇca le popolne rezultate, kar pomeni, da ˇce vne- semo poizvedborazvoj mobilne telefonije in je v bazi dokument z naslovom ”Razvoj prenosne telefonije”, iskalnik tega dokumenta ne bo naˇsel.
2.2. SPLETNI ISKALNIK 7 Iskanje s pomoˇcjo vektorskih prostorov
Ta naˇcin iskanja je izumil Gerard Salton v ˇsestdesetih letih prejˇsnjega stoletja kot odgovor na teˇzave, ki so nastajale pri iskanju z uporabo Booleove algebre. Gre za pretvorbo besedila v numeriˇcne vektorje in matrike, na katerih se potem izvaja analiza. Tak model iskanja nam omogoˇca, da najdemo tudi dokumente, ki se ne ujemajo popolnoma s poizvedbo, so pa podobni. Prednost takega iskanja je tudi ocena ustreznosti dokumenta in povratna informacija o ustreznosti. Glede na ustre- znost dokumentom doloˇcimo vrednost med 0 in 1 in jih na podlagi tega hierarhiˇcno uredimo. Slabost tega modela je ˇcasovna zahtevnost izvajanja, saj je potrebno izraˇcunati podobnosti med vsakim posameznim dokumentom in poizvedbo.
Iskanje s pomoˇcjo verjetnosti
Tak model iskanja deluje na oceni verjetnosti, da bo doloˇcen dokument za uporabnika ustrezen. Ocena verjetnosti se doloˇci kot koliˇcnik med verjetnostjo, da je dokument ustrezen, in verjetnostjo, da ni. Opozorimo, da tu govorimo le o oceni verjetnosti in ne o pravi verjetnosti, saj so lahko vrednosti tega koliˇcnika veˇcje od 1. Dokumenti so urejeni hierarhiˇcno glede na vrednost ocene verjetnosti. Slabost verjetnostnega modela je, da je izredno zahteven za implementacijo.
2.2 Spletni iskalnik
Razdelek opisuje, kaj je spletni iskalnik, njegove lastnosti, naloge in delova- nje. Podaja sploˇsni opis delovanja iskalnikov in lastnosti, ki jih pripisujemo vsem iskalnikom.
2.2.1 Kaj je spletni iskalnik?
Velikokrat naredimo napaˇcno povezavo in iskalnik zamenjamo z brskalnikom.
Spletni brskalnik (angl. web browser) je raˇcunalniˇski program, namenjen iskanju in prikazu HTML dokumentov in veˇcpredstavnih vsebin iz svetovnega spleta s pomoˇcjo URL-ja1. Spletni iskalnik(angl. web search engine) pa je programski sistem, zasno- van za iskanje informacij na svetovnem spletu. Spletni iskalnik torej deluje v ozadju spletnega brskalnika, ki sluˇzi kot vmesnik med uporabnikom in iskalnikom.
Spletno iskanje je veja iskanja oziroma pridobivanja informacij. Spletno iskanje si s klasiˇcnim iskanjem deli marsikatero lastnost, vendar ima tudi nekaj edinstvenih lastnosti in sicer:
1Uniform Resource Locator (enotni doloˇcevalec vira)
8 POGLAVJE 2. SPLETNI ISKALNIK
velikost,
dinamiˇcnost,
samoorganizacijo,
hiperpovezanost.
Utemeljimo zgornje lastnosti. Splet je leta 2004 obsegal 10 milijard (109) spletnih strani. Ocenjujejo, da splet vsebuje pribliˇzno 20-krat veˇc informacij kot Kongre- sna knjiˇznica (angl. Library of Congress), ki velja za najveˇcjo knjiˇznico na svetu in vsebuje preko 34,5 milijonov knjig. ˇCeprav v zadnjem ˇcasu splet ne raste veˇc tako hitro kot v preteklosti, ˇse vedno velja za najveˇcjo zbirko dokumentov na svetu.
Dinamiˇcnost se od klasiˇcnih dokumentov razlikuje v dveh stvareh. Prviˇc, za razliko od klasiˇcnih dokumentov, ki se po tisku ne spreminjajo veˇc, se spletne strani spre- minjajo zelo pogosto. In drugiˇc, rast spleta je v primerjavi s klasiˇcnimi dokumenti precej hitrejˇsa – v enem letu nastane nekaj tisoˇc klasiˇcnih dokumentov, medtem ko splet v istem obdobju zraste za nekaj milijard spletnih strani. Raziskave kaˇzejo, da se kar 40% spletnih strani spremeni v prvem tednu, 23% pa vsakodnevno. Splet se samoorganizira, saj se podatki neprestano posodabljajo, povezave se trgajo, doku- menti izginjajo. Znan je podatek iz leta 2002, da je kar polovica dokumentov, ki so bili citirani v neki reviji, postala nedostopna v roku ˇstirih let. Podatki so heterogeni, saj obstajajo v razliˇcnih formatih, jezikih in pisavah. Sem spada ˇse ena edinstvena lastnost spleta, in sicer spleta nihˇce ne ureja oziroma pregleduje. Samoorganizacija spleta pomeni tudi, da so spletne strani ustvarjene za celo vrsto namenov – neka- tere za nakupovanje, druge za nakljuˇcne obiskovalce, ki zgolj iˇsˇcejo neko informacijo . . . To predstavlja ˇse eno zahtevno nalogo za spletni iskalnik, ki mora pri iskanju velikokrat kombinirati razliˇcne tipe poizvedb glede na potrebe uporabnika. Seveda je tudi hiperpovezan, saj je to osnovna lastnost spleta in tudi tista kljuˇcna, ki jo izkoriˇsˇcajo spletni iskalniki. Poleg vseh teh izzivov pa se iskalnik sooˇca ˇse z enim – natanˇcnostjo. Uporabniki navadno pregledajo prvih nekaj rezultatov, ki jih vrne iskalnik, preostalo se smatra za neustrezno. Iskalniki morajo znati odgovoriti na tak naˇcin iskanja in vraˇcati rezultate, ki so natanˇcni. Opiˇsimo sedaj delovanje spletnega iskalnika.
2.2.2 Delovanje spletnega iskalnika
V sploˇsnem lahko delovanje brskalnika opiˇsemo s tremi koraki: plazenje (angl.
crawling), indeksiranje (angl. indexing) in procesiranje poizvedbe (angl. query processing). Namenimo nekaj besed vsakemu izmed njih.
2.2. SPLETNI ISKALNIK 9 Plazenje
Naloga modula za plazenje je, da ustvari virtualne robote imenovanepajki, ki se neprestano plazijo po spletu in pridobivajo nove informacije o spletnih straneh.
To poˇcnejo tako, da stranem poˇsiljajo ogromne koliˇcine zahtev. Tako pajek pridobi informacije o spletnih straneh, ki jih preda v nadaljnjo obdelavo, in poiˇsˇce vse po- vezave od te strani naprej, ki jih uvrsti na seznam zahtev. Nato poˇslje nove zahteve in najde nove strani in povezave, kar se ponavlja v neskonˇcnost. Kljub temu, da so pajki uporabniku skriti, opravljajo eno najpomembnejˇsih nalog – ˇce pajek obiˇsˇce veˇc strani, je verjetnost za uspeˇsno iskanje veˇcja. Pri plazenju lahko naletimo tudi na nekaj teˇzav, na primer, kako pogosto naj pajki obiˇsˇcejo strani. Zaradi dinamiˇcnosti spleta so lahko podatki, pridobljeni pred nekaj tedni, ˇze zastareli. Zato se plazenje nikoli ne konˇca. Vendar pa se nekatere strani osveˇzujejo pogosteje kot druge, zato jih mora tudi pajek obiskati pogosteje. V tem primeru se iskalniki sami odloˇcajo, kako bodo obiskovali spletne strani, nekateri na primer to poˇcnejo glede na njihovo pogostost osveˇzevanja in pomembnost. Drugi primer teˇzave je, kako se etiˇcno plaziti po straneh. V ta namen je bil razvit protokol imenovan The Robots Exclusion Pro- tocol, ki skrbi za ustrezno plazenje pajkov. Med drugim je tu pomembno, da pajki ne vplivajo na delovanje spletne strani. Administratorji spletnih strani pa imajo moˇznost pajke tudi povsem blokirati, in sicer z nastavitvijo doloˇcenih parametrov na spletni strani. Preostale teˇzave, s katerimi se sreˇcuje modul za plazenje so ˇse:
kako se izogniti prekrivanju (dva pajka obiskujeta iste strani), katere strani sploh obiskati . . . Kot zanimivost omenimo, da se lahko zgodi, da naˇse strani pajek nikoli ne bo naˇsel. V tem primeru lahko iskalnikom poˇsljemo URL naˇse spletne strani in jo s tem dodamo na njihov seznam strani, ki jih je potrebno obiskati. Pri nekaterih iskalnikih imamo celo moˇznost vpogleda v to, ali je njihov pajek naˇsel naˇso spletno stran ali ne. Bralec si lahko ogleda primer programske kode za pajka v [1].
Indeksiranje
Vse informacije, ki jih pajek pridobi, gredo v modul za indeksiranje. Pajek sem prinese veˇcji del vsebine spletnih strani, zato je prvi korak pri indeksiranju re- dukcija celotne vsebine na bistvene komponente. Sem spadajo: naslov, opis, sidrno besedilo, odebeljene besede, besede zapisane z veˇcjim fontom in hiperpovezave. To se shrani v tako imenovano inverzno datoteko (angl. inverted file), in sicer tako, da so ob vsakem pojmu zapisane ˇstevilke spletnih strani, na katerih se ta pojem pojavi, podobno kot pri stvarnem kazalu v knjigi.
Inverzna datoteka bi lahko izgledala na primer takole:
10 POGLAVJE 2. SPLETNI ISKALNIK
atom - 5, 45, 131
⋮
fakulteta - 3, 11, 24, 42, 55, 154, 1423, 114623
⋮
pedagoˇska - 3, 5, 25, 40, 55, 111, 1423
⋮
zeliˇsˇca - 65, 448, 2298, 5107923
To pomeni, da je pojem atom vsebovan na straneh 5, 45 in 131.
Hitro vidimo, da bo taka datoteka ogromna, hkrati pa se bodo sploˇsni pojmi, kot na primer vreme pojavili na veliko straneh. Zato se uporabljajo dodatni para- metri za vsak pojem in za vsako stran, na kateri se pojavi. To so na primer, kje na strani se ta pojem pojavi (naslov, opis) in v kakˇsni obliki (odebeljeno besedilo, sidrno besedilo). Zopet je teˇzava tudi dinamiˇcnost spleta, saj se mora datoteka posodabljati skupaj s stranjo, pa tudi naˇcin, kako bo datoteka shranjena (zaradi ve- likosti jo je potrebno deliti na veˇc manjˇsih). Zgolj za zanimivost omenimo podatek, da je Googlov indeks leta 2004 obsegal dobrih osem milijard spletnih strani, za kar je Google potreboval veˇc deset tisoˇc raˇcunalnikov.
Procesiranje poizvedbe
To je edini korak iskanja, ki je odvisen od uporabnika. Ta modul mora upo- rabnikovo poizvedbo obdelati v realnem ˇcasu in ˇcim hitreje vrniti rezultat (govorimo o milisekundah). Kako torej to storiti? Vzemimo za primer inverzno datoteko, ki smo jo uporabili pri opisu indeksiranja in denimo, da uporabnik vnese poizvedbo pedagoˇska fakulteta. Iskalnik avtomatsko predpostavi, da iˇsˇcemo oba pojma sku- paj. V tem primeru bi torej vrnil mnoˇzico spletnih strani, kjer se pojavita oba, to je {3,55,1423}. Namenoma smo oblikovali tak primer, da se pojma pojavita zgolj na dveh straneh, vendar ni teˇzko opaziti, da je lahko ta mnoˇzica ogromna. En naˇcin, kako narediti mnoˇzico bolj obvladljivo je, da upoˇstevamo dodatne parametre (glej razrelek Indeksiranje). Recimo, da bomo beleˇzili tri dodatne informacije za vsak pojem: ali se pojem pojavi v naslovu, ali se pojavi v opisu in kolikrat se pojavi v besedilu. To lahko storimo tako, da vsaki strani pripnemo vektor s temi podatki.
Za pojem pedagoˇska in stran 3 bi lahko izgledalo takole:
pedagoˇska - 3 [1, 1, 11], 5, 25, 40, 111, 1423
To pomeni, da je pojem pedagoˇska vsebovan v naslovu in opisu strani ter da se v besedilu pojavi 11-krat. Oglejmo si, kako bi to vplivalo na naˇs iskalni vnos. Recimo, da je rezultat:
2.2. SPLETNI ISKALNIK 11 pedagoˇska - 3 [1, 1, 11], 55 [0, 1, 3], 1423 [1, 0, 3]
fakulteta - 3 [1, 0, 17], 55 [1, 1, 2], 1423 [0, 0, 7]
Iskalnik sedaj uporabi hevristike, da doloˇci, katera stran je bolj ustrezna. Primer hevristike je, da seˇsteje vrednosti vektorja po koordinatah za prvi pojem za stran 3 in to mnoˇzi z vsoto koordinat za drugi pojem za stran 3. Tako dobimo oceno vsebine (angl. content score):
stran 3:(1+1+11)⋅(1+0+17)=234 stran 55: (0+1+3)⋅(1+1+2)=16 stran 1423:(1+0+3)⋅(0+0+7)=28
Vidimo, da ima najviˇsjo vrednost stran 3 (234), zato bo tudi najviˇsje na lestvici. To je ena metoda ureditve mnoˇzice rezultatov, vendar je odvisna od poizvedbe uporab- nika, kar pomeni, da mora iskalnik te vrednosti vsakiˇc znova izraˇcunati, to pa zahteva svoj ˇcas. Zato se uporablja tudi poizvedbeno neodvisne (angl. query-independant) hevristike (glej 3.3). Primer je ocena popularnosti spletne strani oziroma kar popu- larnost. Sem spada tudi algoritem PageRank, ki je osrednja tema magistrske naloge in se mu bomo od tu dalje posebej posvetili.
Slika 2.1: Shema elementov spletnega iskalnika.
Poglavje 3 Google
V tem poglavju bomo najprej predstavili spletno iskanje pred Googlom, usta- novitelja podjetja Google in izumitelja algoritma PageRank – Larrya Pagea in Ser- geya Brina, slabosti spletnega iskanja, ki so ju vodile pri razvoju algoritma, in podali neformalni opis PageRanka. Povedali bomo tudi, kaj je PageRank razlikovalo od ta- kratne konkurence ter zakaj je prevladal. Pri tem bomo uporabljali [1], [2], [3] in [15].
3.1 Spletno iskanje pred Googlom
Spletno iskanje se je pojavilo hkrati z izumom World Wide Weba. Znani iskalniki iz tega obdobja so Archie (1990), Veronica and Jughead (1991), Excite (1993), Yahoo! (1994), WorldWideWebWorm (1994), WebCrawler (1994), in drugi.
V osnovi so vsi delovali v skladu z opisom iz prejˇsnjega poglavja, vkljuˇcno s pro- cesiranjem poizvedbe uporabnika, kjer so strani rangirali glede na oceno vsebine.
Splet je rasel in zaradi njegove velikosti je tak naˇcin iskanja postajal vedno manj primeren. Za ilustracijo navedimo nekaj podatkov. Iskalnik WorldWideWebWorm je imel leta 1994 v svojem indeksu 110.000 spletnih strani in dokumentov, leta 1997 pa je iskalnik WebCrawler indeksiral pribliˇzno 100 milijonov strani. Predvidevali so, da bo splet do leta 2000 obsegal vsaj milijardo spletnih strani in dokumentov.
Podobno je rasla tudi koliˇcina iskanja. Iz pribliˇzno 1500 poizvedb na dan v letu 1994 na 20 milijonov poizvedb na dan v letu 1997. Od leta 1998 se poleg ocene za vsebino kot dodatni kriterij za rangiranje spletnih strani uporablja tako imenovana ocena za popularnost (tudi ocena za pomembnost, angl. popularity score, impor- tance score). Popularnost kot kriterij za rangiranje je drastiˇcno izboljˇsala rezultate iskanja. Izkoriˇsˇca namreˇc strukturo spleta, ki je povezan s hiperpovezavami, zato se tak naˇcin iskanja imenuje model analize povezav (angl. link analysis model). Prav ta model uporablja tudi PageRank.
13
14 POGLAVJE 3. GOOGLE
3.2 Razvoj algoritma PageRank
3.2.1 O avtorjih algoritma
Algoritem PageRank sta razvila Larry Page in Sergey Brin. Leta 1996 sta se pridruˇzila raziskovalnemu projektu
”Internetni iskalniki nove generacije“ na Univerzi Stanford v Kaliforniji, kjer sta sicer opravljala doktorski ˇstudij iz raˇcunalniˇstva. Leta 1998 sta pri 25 letih objavila svoje delo v ˇclanku
”Anatomija obseˇznega hiperteks- tnega spletnega iskalnika“ (angl. The Anatomy of a Large-Scale Hypertetual Web Search Engine), ki je predstavljal tudi rojstvo podjetja Google. S svojim delom sta spremenila ne le svet spletnega iskanja, ampak tudi poslovni svet. Vrednost Googla je namreˇc danes ocenjena na pribliˇzno 80 milijard ameriˇskih dolarjev. Google se da- nes ne ukvarja veˇc izkljuˇcno s spletnim iskanjem. Veˇc o Googlu in njegovem vplivu na ekonomijo in gospodarstvo si lahko bralec prebere v [3].
3.2.2 Motivacija za razvoj
Osnovni problem, ki sta ga s svojim raziskovalnim delom ˇzelela nasloviti Page in Brin, je bila slaba kvaliteta iskanja kot posledica rasti spleta. Ob tem sta ˇzelela tudi znanstveno raziskati spletno iskanje.
Med raziskovanjem sta ugotovila, da je fokus takratnih razvijalcev spletnih iskalnikov usmerjen v napaˇcno stvar. Bili so namreˇc mnenja, da je kljuˇc do dobrega iskalnika popoln indeks, kar pa je le deloma res. Vendar se je zaradi rasti spleta kazala vedno veˇcja potreba po ureditvi rezultatov iskanja, in sicer hierarhiˇcno, po pomembnosti. Rezultat iskanja je bil namreˇc ponavadi ogromen seznam veˇcinoma povsem irelevantnih spletnih strani. Za ilustracijo najdemo podatek iz leta 1997, da so le ˇstirje vodilni iskalniki naˇsli samega sebe (svojo domaˇco spletno stran) med prvimi desetimi zadetki. ˇSe ena slabost takratnih iskalnikov je bil naˇcin doloˇcanja pomembnosti posamezne spletne strani. Veˇcjo pomembnost so namreˇc doloˇcili glede na gostoto kljuˇcnih besed ali zgolj koliˇcino povezav, ki kaˇzejo na to spletno stran.
Zakljuˇcila sta, da iskalniki niso rasli skladno s spletom, ampak so ostali krepko zadaj, in da je hierarhiˇcna ureditev spletnih strani prihodnost spletnega iskanja. Drugi cilj je bil sestaviti tak iskalni sistem, ki bo podpiral znanstveno raziskovanje. Ugotovila sta namreˇc, da se je spletno iskanje v preteklosti razvijalo bolj kot ne izkljuˇcno v komercialne namene in ne znanstvene.
3.3. POIZVEDBENO NEODVISNO DOLO ˇCANJE POMEMBNOSTI 15
3.3 Poizvedbeno neodvisno doloˇ canje pomembno- sti
Seveda Page in Brin nista bila edina, ki sta ˇzelela analizo povezav uporabiti v svojem algoritmu za doloˇcanje pomembnosti spletnih strani. Omenimo, da je v istem ˇcasu IBM pod vodstvom Jona Kleinberga pripravljal ˇse en tak iskalnik ime- novan HITS (Hypertext Induced Topic Search), ki je Googlu takrat predstavljal resno konkurenco. Kljuˇcno, da je PageRank prevladal, je bilo doloˇcanje pomemb- nosti neodvisno od poizvedbe. Rangiranje strani je poizvedbeno neodvisno, ˇce na popularnost strani ne vpliva uporabnikova poizvedba, ampak se jo doloˇci neodvisno in ostane konstantna do naslednje osveˇzitve. V praksi to pomeni, da med procesi- ranjem poizvedbe, kjer je ˇcas izrednega pomena, ne zapravljamo ˇcasa z raˇcunanjem pomembnosti, ampak zgolj poiˇsˇcemo vnaprej izraˇcunane vrednosti. Tu se vidi po- membna razlika med poizvedbeno odvisnim iskanjem, opisanem v razdelku 2.2.2 (Procesiranje poizvedbe). ˇCe torej iskalnike razdelimo na poizvedbeno odvisne in neodvisne, hitro vidimo prednosti enih in drugih. PageRank spada med poizvedbeno neodvisne, kar pomeni, da raˇcuna in hrani popularnosti vseh strani v Googlovem indeksu. Na drugi strani je bil iskalnik HITS v osnovi poizvedbeno odvisen, zato ni mogel konkurirati PageRanku.
3.4 Neformalni opis delovanja PageRanka
Kot smo ˇze zapisali, PageRank spretno izkoriˇsˇca hiperpovezanost spleta. V resnici gre za to, da si splet predstavljamo kot ogromen usmerjen graf (glej 4.2), v katerem so spletne strani vozliˇsˇca, hiperpovezave pa usmerjene povezave grafa.
Povezave dalje delimo ˇse na vhodne in izhodne, odvisno od tega, ali gre povezava v vozliˇsˇce ali iz njega.
Slika 3.1: Primer spleta, modeliranega z usmerjenim grafom.
16 POGLAVJE 3. GOOGLE PageRank deluje na ideji, da je stran pomembna, ˇce ima veliko pomembnih
”povezav nazaj“ (angl. backlinks), po domaˇce, ˇce veliko pomembnih strani kaˇze nanjo. Vendar te povezave niso enakovredne, ampak se jih uteˇzi glede na ˇstevilo izhodnih povezav posamezne strani, ki kaˇzejo na stran. Pojasnimo s primerom.
Denimo, da gremo na volitve, kjer je glas vsakega volivca vreden enako, recimo 1. Hkrati pa lahko, v primeru da se ne moremo odloˇciti le za enega kandidata, glasujemo za veˇc. ˇCe glasov ne uteˇzimo, to pomeni, da je volivec, ki je glasoval za tri kandidate, v resnici glasoval trikrat, kar je nepraviˇcno do volivca, ki je glasoval le za enega. Zato uteˇzimo glasove tako, da se glas enakomerno razdeli med vse kandidate, za katere je volivec glasoval. Torej volivec, ki glasuje za tri kandidate, da v resnici vsakemu tretjino svojega glasu. Ravno zaradi analogije z volitvami najdemo v literaturi, da so povezave uteˇzene po naˇcelu demokratiˇcnosti. Zapiˇsimo sedaj delovanje algoritma bolj strukturirano.
Denimo, da imamo neki nabor spletnih strani, ki so preko hiperpovezav pove- zane med seboj. Pomembnost strani A iz tega nabora se doloˇci glede na to, koliko od preostalih strani iz tega nabora kaˇze nanjo in kako pomembne so. Pri tem se upoˇsteva naˇcelo demokratiˇcnosti, to je, da so povezave strani uravnoteˇzene glede na to, na koliko strani kaˇze ta stran. ˇCe torej stran B kaˇze le na stran A, stran C pa ˇse na dve drugi, je povezava B →A veˇc vredna kot povezava C → A. Na kratko, spletna stran je pomembna, ˇce nanjo kaˇzejo druge pomembne spletne strani.
Ce sˇ P R(T) oznaˇcimo PageRank spletne strani T, potem P R(A) spletne strani A zadoˇsˇca enaˇcbi
P R(A)=(P R(T1)
C(T1) +P R(T2)
C(T2) +. . .+P R(Tn) C(Tn) ),
kjer so Ti spletne strani, ki kaˇzejo na stran A, C(Ti) pa ˇstevilo izhodnih povezav strani Ti, i=1,2, . . . n.
Page in Brin sta nato popravila svojo prvotno formulacijo tako, da sta simu- lirala obnaˇsanje nakljuˇcnega uporabnika. Predpostavila sta, da se uporabnik po spletnih straneh premika preko povezav, v nekem trenutku pa se odloˇci, da bo v vnosno vrstico brksalnika vnesel URL naslov neke spletne strani. Tako sta v enaˇcbo vnesla tako imenovani faktor duˇsenjad(angl. damping factor). Popravljena enaˇcba je sedaj oblike
P R(A)=(1−d)+d⋅(P R(T1)
C(T1) +P R(T2)
C(T2) +. . .+P R(Tn) C(Tn) ).
Faktor duˇsenja d pove, da se uporabnik z verjetnostjo d prestavi na novo sple- tno stran preko hiperpovezave, z verjetnostjo (1−d) pa preko vnosa URL naslova.
3.4. NEFORMALNI OPIS DELOVANJA PAGERANKA 17 PageRank strani A torej doloˇcimo tako, da najprej seˇstejemo uteˇzene vrednosti Pa- geRanka vseh strani, ki kaˇzejo na A, in vrednost mnoˇzimo z d. Nazadnje dobljeni vrednosti priˇstejemo ˇse verjetnost vnosa nakljuˇcnega URLja, torej (1−d). Kasneje sta Brin in Page ugotovila, da je tudi ta formulacija pomanjkljiva in jo zopet po- pravila (glej poglavje 5).
Preden spoznamo konˇcno formulacijo in jo tudi matematiˇcno utemeljimo, po- trebujemo naslednje poglavje, v katerem predstavimo teoretiˇcne osnove.
Poglavje 4
Teoretiˇ cne osnove
Namen tega poglavja je na enem mestu zbrati vse potrebne definicije, izreke, trditve in dokaze, ki jih bomo kasneje potrebovali za razlago PageRank algoritma.
Prvi del pokriva podroˇcje linearne algebre, drugi pa teorije grafov. Od bralca se priˇcakuje, da ˇze pozna doloˇcene pojme in rezultate s podroˇcja linearne algebre in teorije grafov. Skozi celotno poglavje izhajamo iz [4], [5], [6] in [7], kjer je izjemoma uporabljen drugi vir, pa je le-ta naveden.
4.1 Teoretiˇ cne osnove s podroˇ cja linearne algebre
V mnoˇzico vektorjev Rn vpeljemo relacijo delne urejenosti
”manj ali enako“
(≤) s predpisom
x≤y ⇐⇒ xi≤yi za vse i=1, . . . , n, kjer se po koordinatah vzame standardno relacijo
”manj ali enako“. Dualno relacijo
”veˇc ali enako“ oznaˇcimo z ≥. Podobno vpeljemo relaciji ≤ oziroma ≥ na mnoˇzici kvadratnih matrik Rn×n
A≤B ⇐⇒ aij ≤bij za vse i, j=1, . . . , n.
Vektorju x≥0, ki ima vse koordinate nenegativne, reˇcemo nenegativni vektor, ma- triki A≥0 pa nenegativna matrika.
Absolutna vrednost vektorja x = (x1, . . . , xn)T ∈ Rn je vektor absolutnih vre- dnosti koordinat
∣x∣=(∣x1∣, . . . ,∣xn∣)T, 19
20 POGLAVJE 4. TEORETI ˇCNE OSNOVE absolutna vrednost matrike A=(aij)n×n, aij ∈R pa je matrika absolutnih vrednosti elementov
∣A∣=(∣aij∣)n×n.
Lema 4.1. Za poljubno matriko A=(aij)n×n veljajo naslednje lastnosti:
i) Matrika A je nenegativna natanko tedaj, ko je Ax≥0 za vse x≥0.
ii) Za poljuben vektor x velja neenakost ∣Ax∣≤∣A∣∣x∣. V posebnem primeru A ≥0 je ∣Ax∣≤A∣x∣.
Dokaz. Dokaˇzimo vsako toˇcko leme posebej.
i) A≥0 ⇐⇒ ∀x≥0∶Ax≥0.
Pokaˇzimo, da velja implikacija v desno smer. Za poljuben nenegativen vektor x≥0 si oglejmo produktAx.
⎛⎜⎜
⎜⎜⎜⎜
⎝
a11 a12 . . . a1n a21 a22 . . . a2n
⋮ ⋮ ⋱ ⋮
an1 an2 . . . ann
⎞⎟⎟
⎟⎟⎟⎟
⎠
⎛⎜⎜
⎜⎜⎜⎜
⎝ x1 x2
⋮ xn
⎞⎟⎟
⎟⎟⎟⎟
⎠
=
⎛⎜⎜
⎜⎜⎜⎜
⎝
a11x1+a12x2+. . .+a1nxn a21x1+a22x2+. . .+a2nxn
⋮
an1x1+an2x2+. . .+annxn
⎞⎟⎟
⎟⎟⎟⎟
⎠
Oˇcitno je, da bo vsaka koordinata produkta Axnenegativna, saj je vsaka kom- ponenta vsota produktov nenegativnih ˇstevil.
Da pokaˇzemo implikacijo v obratni smeri, si oglejmo produkt Aei, kjer je ei standardni bazni vektor. Potem je Aei natanko i-ti stolpec matrike A. Ker je ei ≥0, bo produkt Aei ≥0 le, ˇce bo tudi i-ti stolpec matrike A nenegativen.
To pa lahko storimo za vse 1≤i≤n.
ii) ∣Ax∣≤∣A∣∣x∣.
V ∣Ax∣ je i-ti element enak ∣∑nj=1aijxj∣, v produktu ∣A∣∣x∣ pa je i-ti element enak ∑nj=1∣aij∣∣xj∣. Dokaz sledi z upoˇstevanjem znane neenakosti za absolutno vrednost
∣∑n
j=1
aijxj∣≤∑n
j=1
∣aij∣∣xj∣.
Zadnja trditev je neposredna posledica dejstva, da za nenegativne matrike velja
∣A∣=A.
Mnoˇzico vseh lastnih vrednosti matrikeA imenujemo spekter matrike, σ(A)={λ∈R∣ ∃x≠0∶Ax=λx},
4.1. TEORETI ˇCNE OSNOVE S PODRO ˇCJA LINEARNE ALGEBRE 21 po absolutni vrednosti najveˇcji lastni vrednosti pa reˇcemo spektralni radij in ga oznaˇcimo z r(A):
r(A)=max{∣λ∣ ∣ λ∈σ(A)}.
Naj bo X realen vektorski prostor. Funkciji ∣∣ ∣∣ ∶ X → R reˇcemo norma, ˇce ustreza naslednjim pogojem:
1. ∣∣x∣∣≥0 za vsak x∈X, 2. ∣∣x∣∣=0 ⇐⇒ x=0,
3. ∣∣λx∣∣=∣λ∣ ∣∣x∣∣ za vsakx∈X in λ∈R, 4. ∣∣x+y∣∣≤∣∣x∣∣+∣∣y∣∣.
Brez dokaza navedimo ˇse koristno neenakost, ki jo bomo vˇcasih potrebovali, dokaz sledi neposredno iz definicije.
Lema 4.2. Naj bostaxinypoljubna vektorja v realnem vektorskem prostoru. Potem velja
∣ ∣∣x∣∣−∣∣y∣∣ ∣≤∣∣x−y∣∣.
Pomemben zgled norme je tako imenovanap-ta norma, definirana s predpisom
∣∣x∣∣p=(∑n
i=1
∣xi∣p)
1 p,
kjer je p≥1 naravno ˇstevilo. Dokaz, da predpis res doloˇca normo, opuˇsˇcamo. Bralec ga lahko najde v [4]. Prav tako opuˇsˇcamo dokaz naslednje leme, katere dokaz pa je preprost in ga prepruˇsˇcamo bralcu.
Lema 4.3. Naj bo A∈Rn×n kvadratna matrika. Potem je mnoˇzica {Ax ∣ ∣∣x∣∣p=1} v normi ∣∣ ∣∣p navzgor omejena.
Lema 4.3 omogoˇca, da lahko norme definiramo tudi za matrike:
∣∣A∣∣p=sup
x≠0
∣∣Ax∣∣p
∣∣x∣∣p = max
∣∣x∣∣p=1∣∣Ax∣∣p.
22 POGLAVJE 4. TEORETI ˇCNE OSNOVE Mi bomo potrebovali normi zap=1 in p=∞. Z nekaj raˇcunanja se da pokazati, da lahko v tem primeru ti dve normi izrazimo tudi drugaˇce:
∣∣A∣∣1=max
1≤j≤n m
∑
i=1
∣aij∣,
∣∣A∣∣∞=max
1≤i≤m n
∑
j=1
∣aij∣.
Norma za p= 1 nam da najveˇcjo vsoto absolutnih vrednosti elementov v stolpcih matrike, norma za p= ∞ pa najveˇcjo vsoto absoutnih vrednosti elementov po vr- sticah matrike. Za nas bodo norme pomembne zaradi konvergence zaporedij. Brez dokaza povejmo, da so v tem pogledu vse norme ekvivalentne, namreˇc zaporedje, ki konvergira v eni normi, konvergira tudi v vsaki drugi. V nadaljevanju bomo pri zapisu norm indeks obiˇcajno kar izpuˇsˇcali.
Zapiˇsimo ˇse nekaj lem, ki jih bomo potrebovali v nadaljevanju.
Lema 4.4. Naj bo A∈Rn×n kvadratna matrika. ˇCe xk→x konvergira po normi, to je ∣∣xk−x∣∣→0, potem Axk→Ax konvergira po normi, se pravi ∣∣Axk−Ax∣∣=0.
Lema 4.5. Limita nenegativnega realnega konvergentnega zaporedja je nenegativna.
Lema 4.6. Ce zaporedje vektorjevˇ xn→x0 konvergira po normi in zaporedje skalar- jev λn→r konvergira, potem zaporedje vektorjev λnxn→rx0 konvergira po normi.
Lema 4.7. Za vsako navzgor omejeno mnoˇzico v R obstaja supremum. Supremum je limita kakega konvergentnega zaporedja iz te mnoˇzice.
Lema 4.8. Vsako omejeno zaporedje v evklidskem prostoru ima konvergentno pod- zaporedje.
Izrek 4.9 (Perron). Naj bo A∈Rn×n nenegativna kvadratna matrika s spektralnim radijem r = r(A). Potem je r lastna vrednost matrike A, lastni vektor pa lahko izberemo tako, da je nenegativen.
4.1. TEORETI ˇCNE OSNOVE S PODRO ˇCJA LINEARNE ALGEBRE 23 Dokaz. Pokazali bomo, da lahko spektralni radij r ≥ 0 zapiˇsemo kot limito r = limn→∞λn, kjer so λn nenegativni skalarji, za katere obstajajo nenegativni vektorji xn z lastnostjo Axn≥λnxn.
V ta namen si oglejmo mnoˇzico
Λ={λ≥0 ∣∃x≥0,∣∣x∣∣=1, Ax≥λx}.
Ta mnoˇzica je neprazna, saj je 0∈Λ, in navzgor omejena, to je, obstaja tak M ≥0, da je ∣λ∣ ≤ M za vse λ ∈ Λ. To sledi iz dejstva, da je mnoˇzica {Ax ∣ ∣∣x∣∣ = 1} po lemi 4.3 navzgor omejena. Iz λx ≤ Ax namreˇc sledi ∣∣λx∣∣ ≤ ∣∣Ax∣∣ in tedaj je
∣λ∣=λ∣∣x∣∣=∣∣λx∣∣≤∣∣Ax∣∣≤M.
Po lemi 4.7 obstaja supremum r =sup Λ. To bo natanko spektralni radij. Po lemi 4.7 ga lahko zapiˇsemo kot limito
r= lim
n→∞λn,
kjer so λn ∈ Λ. Po definiciji mnoˇzice Λ za vsak λn ∈ Λ obstaja tak vektor xn, da Axn≥λnxn in∣∣xn∣∣=1. Ker je mnoˇzica{xn ∣ ∣∣xn∣∣=1}v normi omejena, obstaja po lemi 4.8 konvergentno podzaporedje vektorjev, ki konvergira proti nekemu vektorju x0. Smemo vzeti, da je ustrezno (pod)zaporedje kar (xn)→x0.
Imamo torej konvergentno zaporedje enotskih nenegativnih vektorjev xn ≥ 0, xn → x0,∣∣xn∣∣ = 1 in zaporedje λn → r, pri ˇcemer je Axn ≥λnxn. V naslednjem koraku bomo pokazali, da je r∈Λ, torej da velja
x0≥0, ∣∣x0∣∣=1 in Ax0≥rx0.
Relacija x0 ≥ 0 velja po lemi 4.5. Pokaˇzimo ˇse drugi dve. Enakost ∣∣x0∣∣ =1 sledi z uporabo leme 4.2:
0≤∣1−∣∣x0∣∣ ∣=∣ ∣∣xn∣∣−∣∣x0∣∣ ∣≤∣∣xn−x0∣∣→0.
Za dokaz tretje neenakosti se moramo sklicati na osnovne lastnosti konvergentnih zaporedij v evklidskem prostoru:
Ax0 =A(lim
n→∞xn)= lim
n→∞Axn≥ lim
n→∞λnxn=rx0.
Po lemi 4.4 je Ax0 limita zaporedja Axn; matrika A je kot preslikava v evklidskem prostoru zvezna, kar pomeni, da matrika A preslika konvergentno zaporedje v kon- vergentno zaporedje slik. Oˇcitno je tudi, da se po lemi 4.5 v limiti ohranja neenakost Axn≥λnxn. Poleg tega po lemi 4.6 zaporedje λnxn konvergira proti zaporedju rx0.
24 POGLAVJE 4. TEORETI ˇCNE OSNOVE Velja torej Ax0 ≥ rx0. S tem smo pokazali, da je supremum r = sup Λ element mnoˇzice Λ.
Sedaj lahko pokaˇzemo, da je x0 lastni vektor za lastno vrednost r. Tega se lotimo s protislovjem. Predpostavimo, da jeAx0>rx0. Potem zaradi nenegativnosti matrikeAveljaA(Ax0)>A(rx0)=rAx0. Zagotovo jeAx0 ≠0, saj bi v nasprotnem primeru imeli protislovno neenakost 0=Ax0 >rx0 ≥0. Vzemimo normiran vektor y0 v smeri vektorja Ax0. Velja y0 ≥0, ∣∣y0∣∣ =1 in Ay0 >ry0. Iz zadnje neenakosti razberemo, da obstaja takλ>r, da veljaAy0≥λy0. Zaradi tega jeλ∈Λ, kar pa je v protislovju s predpostavko, dar=sup Λ. Iz tega sledi, da je predpostavkaAx0>rx0 napaˇcna, zato veljaAx0=rx0.
Pokazati moramo ˇse, da nobena druga lastna vrednost matrike Apo absolutni vrednosti ne presegar, z drugimi besedami, da je r spektralni radij matrike A. Naj bo λ neka lastna vrednost matrike A in z pripadajoˇci lastni vektor, torej Az =λz.
Ce uporabimo neenakost iz leme 4.1 dobimoˇ
A∣z∣=∣A∣∣z∣≥∣Az∣=∣λz∣=∣λ∣∣z∣.
Vektor ∣z∣ je nenegativen, zato je nenegativen tudi enotski vektor u = ∣∣z∣∣∣z∣, ki tako zadoˇsˇca neenakostiAu≥∣λ∣u.Sledi ∣λ∣∈Λ. Ker pa jer=sup Λ, velja∣λ∣≤r.
V zvezi s spektralnim radijem kot zanimivost dodajmo ˇse, da ga lahko vedno doloˇcimo s pomoˇcjo Gelfandove enaˇcbe na naslednji naˇcin [Proposition 3.1.3, 9]:
Lema 4.10 (Gelfand). Naj ∣∣ ∣∣ oznaˇcuje poljubno matriˇcno normo. Potem velja r(A)= lim
k→∞∣∣Ak∣∣1k.
Definirajmo ˇse nekaj pojmov oziroma lastnosti, ki jih lahko ima nenegativna matrika. Nenegativna matrika A se imenuje vrstiˇcno stohastiˇcna, ˇce je vsota ele- mentov v vsaki vrstici enaka 1, ∑nj=1aij = 1 za vse i = 1, . . . , n, oziroma stolpˇcno stohastiˇcna, ˇce je vsota elementov v vsakem stolpcu enaka 1, ∑ni=1aij =1 za vse j = 1, . . . , n.
Trditev 4.11. Za vrstiˇcno ali stolpˇcno stohastiˇcno matriko A je spektralni radij enak r(A)=1 in λ=1 je lastna vrednost matrike.
Dokaz. Po definiciji norme matrike je ∣∣Ax∣∣≤∣∣A∣∣ ∣∣x∣∣. ˇCe je x lastni vektor, potem velja∣λ∣ ∣∣x∣∣≤∣∣A∣∣ ∣∣x∣∣. Iz tega pa sledi ∣λ∣≤∣∣A∣∣.
4.1. TEORETI ˇCNE OSNOVE S PODRO ˇCJA LINEARNE ALGEBRE 25 Za vrstiˇcno stohastiˇcno matriko velja
∣∣A∣∣∞=max
1≤i≤n n
∑
j=1
∣aij∣=1,
za stolpˇcno pa
∣∣A∣∣1 =max
1≤j≤n n
∑
i=1
∣aij∣=1.
Za lastne vrednosti vrstiˇcno ali stolpˇcno stohastiˇcne matrike zato velja ∣λ∣≤1.
Pokaˇzimo, da je 1 res lastna vrednost. Naj bo najprejAvrstiˇcno stohastiˇcna. Potem zae=(1, . . . ,1)T veljaAe=e, kar pa ˇze pomeni, da je spektralni radijr(A)=1. ˇCe pa je A stolpˇcno stohastiˇcna, je AT vrstiˇcno stohastiˇcna. Po pravkar dokazanem je 1∈σ(AT). Ker veljaσ(AT)=σ(A)ima tudi stolpˇcno stohastiˇcna matrika spektralni radij enak 1.
Omenimo, da dokaz zgornje trditve sledi tudi neposredno iz Gelfandove enaˇcbe, saj iz r(A)=lim∣∣Ak∣∣k1 in∣∣A∣∣=1 takoj sledi r(A)=1.
V tem dokazu lahko opazimo, da je za vrstiˇcno stohastiˇcno matriko normi- rani lastni vektor za lastno vrednost 1 enak n1(1, . . . ,1)T in je strogo pozitiven. Za stolpˇcno stohastiˇcno matriko pa po Perronovemu izreku vemo le, da obstaja lastni vektor pri lastni vrednosti 1, ki je nenegativen.
Vpeljimo sedaj ˇse eno lastnost, ki jo ima lahko matrika, in bo bolj primerna temi, ki smo se jo namenili preuˇciti.
Matrika A=(aij)n×n je razcepna, ˇce obstaja taka neprazna indeksna mnoˇzica M ⊂{1, . . . , n}, da je linearen podprostor
JM ={(x1, . . . , xn)T ∈Rn ∣xi =0 za i∈M}
invarianten za A. Matriko, ki te lastnosti ne premore, imenujemo nerazcepna.
Na tem mestu je potrebno opomniti, da je (ne)razcepnost matrike odvisna od izbire baze. Vzemimo obrnljivo matriko P. Za to matriko je lahko matrika P−1AP razcepna, ˇceprav je A nerazcepna, in obratno. Vendar opazimo, da permutacija standardnih baznih vektorjev ohranja razcepnost oziroma nerazcepnost. To pa po- meni, da je matrika A razcepna natanko tedaj, ko lahko standardne bazne vektorje Rn preuredimo tako, da je za neki indeks 1≤k<n pripadajoˇci podprostor
Jk={(x1, . . . , xn)T ∈Rn ∣ xk+1=. . .=xn=0}
invarianten za A. Z drugimi besedami, pokazali smo naslednjo trditev.
26 POGLAVJE 4. TEORETI ˇCNE OSNOVE
Trditev 4.12. Matrika A∈Rn×n je razcepna natanko tedaj, ko obstaja taka permu- tacijska matrika P, da je matrika P−1AP bloˇcno trikotna
PTAP =P−1AP =⎛
⎝ X Y
0 Z
⎞
⎠, pri ˇcemer sta matriki X in Z kvadratni.
V zvezi s Perronovim izrekom povejmo, da je Perron ob predpostavki, da so vsi elementi matrike strogo pozitivni, dokazal tudi moˇcnejˇso razliˇcico izreka 4.9, ki reˇce, da je nenegativni lastni vektor pri lastni vrednostirstrogo pozitiven (vse koordinate so>0) in je doloˇcen do skalarja natanˇcno.
Podobno velja za nenegativne matrike, ki so nerazcepne. To bo temeljni izrek, ki ga bomo potrebovali.
Izrek 4.13 (Perron-Frobenius1). Naj boA nenegativna nerazcepna matrika. Potem je spektralni radij r=r(A) lastna vrednost matrike A, pripadajoˇc lastni podprostor je enorazseˇzen in napet na strogo pozitiven lastni vektor z=(z1, . . . , zn)T.
Dokaz. Uporabimo najprej Perronov izrek 4.9. Ta nam zagotovi obstoj nenegativ- nega lastnega vektorja z = (z1, . . . , zn)T ∣ z ≠ 0. Pokaˇzimo najprej, da je z strogo pozitiven.
Pa denimo, da vektorz ni strogo pozitiven. Bazne vektorje preuredimo tako, da za prvih k koordinat vektorja z velja zi>0, za preostalihn−k pazi =0. Od tod sledi, da za poljubeny∈Jk obstajacy >0, za katerega je∣y∣≤cy⋅z.Ce uporabimo ˇse lemoˇ 4.1 dobimo
∣Ay∣≤A∣y∣≤cyAz =cyr⋅z.
Ker ima vektorz zadnjih n−k koordinat enakih 0, ima to lastnost tudi vektorAy, se pravi Ay ∈Jk, tako je Jk invarianten podprostor za A, kar pa je v protislovju s predpostavko, da je A nerazcepna. To pomeni, da je vektor z strogo pozitiven.
Sedaj je potrebno dokazati ˇse, da lastni vrednostir pripada enorazseˇzen lastni podprostor. Tudi tega se lotimo s protislovjem. Denimo, da ima matrika A poleg strogo pozitivnega lastnega vektorja z > 0 ˇse en lastni vektor y ∈ Rn pri lastni vrednosti r. ˇCe je tako, lahko najdemo tak skalar c ∈ R, da je vektor x = z−cy pozitiven, ne pa tudi strogo pozitiven. Ponovimo sedaj razmislek iz prejˇsnjega dela dokaza.
1Ferdinand Georg Frobenius (1849-1917)
4.2. TEORETI ˇCNE OSNOVE S PODRO ˇCJA TEORIJE GRAFOV 27 Bazne vektorje vektorjaxlahko preuredimo tako, da veljaxi >0, zai=1, . . . , m in xi =0 za i=m+1, . . . , n. To pomeni, da za poljuben w ∈Jm obstaja dw >0, za katerega je ∣w∣≤dw⋅x. Zopet uporabimo lemo 4.1 in dobimo
∣Aw∣≤A∣w∣≤dwAx=dwr⋅x,
od koder sledi Aw ∈Jm. To pomeni, da je podprostor Jm invarianten za matriko A, kar je zopet v protislovju z nerazcepnostjo A. Sledi m = 0 in tedaj x = 0. Z drugimi besedami, z =cy, in pripadajoˇci lastni podprostor za lastno vrednost r je tako enorazseˇzen.
Ce sedaj zdruˇˇ zimo trditev 4.11 in izrek 4.13, lahko zapiˇsemo naslednjo posle- dico, ki velja za stohastiˇcne matrike.
Posledica 4.14. Ce je matrikaˇ A nenegativna, nerazcepna in vrstiˇcno ali stolpˇcno stohastiˇcna, je spektralni radij r(A) = 1 ∈ σ(A), pripadajoˇci lastni podprostor je enorazseˇzen in napet na strogo pozitiven lastni vektor.
4.2 Teoretiˇ cne osnove s podroˇ cja teorije grafov
Navedimo par definicij in trditev s podroˇcja teorije grafov, ki jih bomo potre- bovali za utemeljitev delovanja PageRanka.
Usmerjen graf Dje urejena trojkaD=(V(D), E(D), φ), kjer jeV(D)mnoˇzica vozliˇsˇc, E(D) mnoˇzica usmerjenih povezav, funkcija φ ∶ E(D) → V(D)×V(D) pa preslika vsako povezavo v urejen par vozliˇsˇc: φ ∶ a → (v1, v2). Vozliˇsˇcu v1 reˇcemo zaˇcetek povezave, vozliˇsˇcuv2 pa konec povezavea.
Dve povezavi a in b, ki povezujeta isti par vozliˇsˇc, natanˇcneje, ˇce velja φ(a)= φ(b), sta vzporedni povezavi. Usmerjena povezava z zaˇcetkom in koncem v istem vozliˇsˇcu se imenuje zanka. Usmerjen graf brez vzporednih povezav in zank je eno- staven.
Zaporedju vozliˇsˇc in povezav(v0a0, v1a1, . . . , vnan−1)usmerjenega grafaDreˇcemo krepki sprehod v D, ˇce za poljuben indeks 1 ≤ i ≤ n velja φ(ai) = (vi, vi+1) za i = 0, . . . , n−1. V primeru, ko so vse povezave sprehoda paroma razliˇcne, govorimo o enostavnem sprehodu. ˇCe so paroma razliˇcna tudi vsa vozliˇsˇca, pravimo, da gre za (usmerjeno) pot. Usmerjen graf D je krepko povezan natanko tedaj, ko v njem obstaja krepek sprehod (in tedaj tudi neka pot) med poljubnim urejenim parom vozliˇsˇc.
Usmerjeni graf lahko priroˇcno predstavimo s tako imenovano matriko sosedno- sti, zato jo definirajmo. Naj bodo v1, v2, . . . , vn vozliˇsˇca usmerjenega grafaD. Tedaj
28 POGLAVJE 4. TEORETI ˇCNE OSNOVE je matrika sosednosti usmerjenega grafa D matrika A(D)∈Zn×n, katere element v i−ti vrstici in j−tem stolpcu je enak ˇstevilu vzporednih povezav vi →vj. Oˇcitno je, da bodo v primeru, ko je usmerjeni graf enostaven, elementi te matrike le 0 in 1.
Zgled 1: Zapiˇsimo matriko sosednosti danega usmerjenega grafa.
Slika 4.1: Primer usmerjenega grafa na petih vozliˇsˇcih.
Matrika sosednosti A(D)je
A(D)=
⎛⎜⎜
⎜⎜⎜⎜
⎜⎜⎝
0 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0
⎞⎟⎟
⎟⎟⎟⎟
⎟⎟⎠ .
S preprostim premislekom lahko ugotovimo, da se pri preoˇstevilˇcenju vozliˇsˇc usmer- jenega grafa matrika sosednosti spremeni do permutacijske podobnosti natanko, to je, obstaja taka permutacijska matrikaP, da je matrika sosednosti preoˇstevilˇcenega digrafa enaka A′=P−1AP.
Trditev 4.15. Matrika sosednosti usmerjenega grafa je nerazcepna natanko tedaj, ko je pripadajoˇci usmerjeni graf krepko povezan.
Dokaz. Naj bo D krepko povezan graf in denimo, da je matrika sosednosti A raz- cepna. Iz definicije razcepnosti vemo, da lahko razdelimo mnoˇzico vozliˇsˇc V na disjunktni mnoˇzici V1 in V2 (V1 ∪V2 = V) tako, da je glede na novo oˇstevilˇcenje vozliˇsˇc pripadajoˇca matrika sosednosti bloˇcno trikotna:
A=⎛
⎝
A11 A12 0 A22
⎞
⎠,
4.2. TEORETI ˇCNE OSNOVE S PODRO ˇCJA TEORIJE GRAFOV 29 kjer blokAkl za vsakk, l∈{1,2}pripada povezavam iz mnoˇzice vozliˇsˇcVk v mnoˇzico Vl. Opozorimo, da A21 = 0 pomeni, da ne obstaja nobena povezava iz vozliˇsˇca iz mnoˇzice V2 do vozliˇsˇca iz mnoˇzice V1. Poljubno izberimo vozliˇsˇci vi ∈V2 in vj ∈V1. Ker je usmerjeni graf D krepko povezan, obstaja usmerjena pot v D od vi do vj, kar pomeni, da bo produkt ustreznih elementov matrike razliˇcen od 0, saj so na teh mestih same enice, to je
aii1ai1i2. . . aisj ≠0
za nekatere i1, . . . , is ∈ {1, . . . , n}. Opazimo, da mora v tem produktu obstajati neniˇcelni faktor z
”meˇsanimi“ indeksi, to je aikil ≠ 0 z vik ∈ V2 in vil ∈ V1, to v resnici pomeni, da smo med potjo skoˇcili iz enega v drug blok. To pa je v proti- slovju z matriko A, kot smo jo zapisali v bloˇcno trikotni obliki nekaj vrstic viˇsje. Iz tega sledi, da je matrika A nerazcepna.
Podobno se dokaˇze implikacijo tudi v drugo smer, zato jo bomo na tem mestu izpustili in jo prepustili bralcu [9].
Sedaj imamo vso potrebno teoretiˇcno znanje, da se lotimo matematiˇcne ute- meljitve delovanja algoritma PageRank.
30 POGLAVJE 4. TEORETI ˇCNE OSNOVE
Poglavje 5
Matematiˇ cna utemeljitev delovanja
V tem poglavju bomo matematiˇcno opisali in utemeljili delovanje algoritma PageRank. Skozi celotno poglavje izhajamo iz [1] in [7], v prvih treh razdelkih do- datno ˇse iz [2], v ˇcetrtem pa iz [8].
Preden se lotimo utemeljitve, ponovimo neformalni opis. Ce imamo naborˇ spletnih strani, ki so preko hiperpovezav povezane med seboj, se pomembnost strani A iz tega nabora doloˇci glede na to, koliko od preostalih strani iz tega nabora je povezanih z njo in kako pomembne so. Upoˇstevamo naˇcelo demokratiˇcnosti, to je, da so povezave strani uravnoteˇzene glede na to, na koliko strani kaˇze ta stran.
5.1 Formalni opis
Ce ˇˇ zelimo algoritem matematiˇcno zapisati in utemeljiti, potrebujemo najprej nekaj oznak. Denimo, da imamo mnoˇzico, ki vsebuje n spletnih strani:
W ={Wk ∣ k=1, . . . , n}.
Za posamezno spletno stran Wk oznaˇcimo z Ik = {i ∣ Wi →Wk} mnoˇzico indeksov vseh vstopnih povezav, z Ok={j ∣ Wk→Wj} pa mnoˇzico vseh izstopnih povezav ter z xWk >0rang strani Wk. Vpraˇsanje je sedaj, kako najbolje definiratixWk?
Naivno bi lahko rekli, da je rang spletne strani Wk odvisen od ˇstevila strani, ki nanjo kaˇzejo, to je vstopnih povezav Ik. Torej, veˇc strani kot kaˇze na neko stran, bolj pomembna je. Rang spletne strani bi bil lahko definiran kot ˇstevilo vstopnih povezav. Tako definicijo ranga so uporabljali nekateri zgodnji iskalniki, vendar se je
31
