KAKO IŠČE GOOGLE?
MARJETA KRAMAR FIJAVŽ
Fakulteta za gradbeništvo in geodezijo Univerza v Ljubljani
Math. Subj. Class. (2010): 15B48, 15A18, 47H10
Srce spletnega iskalnika Google je algoritem PageRank. V sestavku predstavimo osnovno idejo algoritma ter si ogledamo njegovo teoretično ozadje. Konvergenco algoritma bomo utemeljili na dva načina, s Perron-Frobeniusovo teorijo za pozitivne matrike ter s pomočjo Banachovega izreka o negibni točki.
HOW GOOGLE WORKS?
We present the main idea of the PageRank algorithm which is the core of the Google search engine. We concentrate on the theoretical background of the algorithm and prove its convergence in two different ways, by the Perron-Frobenius theory for positive matrices and using Banach fixed point theorem.
Uvod
Že od začetka leta 1989 (za ustanovitelja velja Tim Berners-Lee) se je svetovni splet zelo hitro siril in kmalu dobil glavno vlogo v prenosu informacij. Svetovni splet je ogromen1 in neprestano raste. Poleg tega se stalno spreminja: 40 % strani spremeni vsebino tedensko, nastajajo nove in izginjajo stare strani. Splet je samoorganiziran s pomočjo raznovrstnih medsebojnih povezav. Gre torej za ogromno knjiznico podatkov, ki nima ne kataloga ne knjizničarjev. Kako se tu znajti?
Vzporedno z nastajanjem spleta so se razvili spletni iskalniki, ki uporabniku z vnosom ključnih besed pomagajo najti ustrezno stran. Med različnimi iskalniki je zadnja leta najbolj znan Google. Spletni iskalnik Google2 sta leta 1998 zagnala Sergey Brin in Larry Page, takrat doktorska studenta na Stanfordski univerzi v Kaliforniji.
Vsak spletni iskalnik ima svojo bazo spletnih strani, ki se seveda neprestano spreminja. Gradi jo s pomočjo avtomatskega programa, ki po spletu stalno posilja virtualne robote, imenovane pajki. Pajki potujejo po spletnih povezavah ter vsako obiskano stran ostevilčijo in indeksirajo njeno vsebino (naslov, ključne besede, imena povezav, sidra ipd.). Tako nastane baza spletnih strani s stvarnim kazalom. Ko uporabnik v iskalnik vtipka poizvedbo,
x19. 1. 2014 obstaja vsaj 1.75 milijarde spletnih strani, http://www.worldwideweb size.com/.
2Ime Google naj bi izviralo iz angleske besede »googol« (sl. gugol), ki pomeni stevilo 10100.
121	Obzornik mat. fiz. 61 (2014) 4

Marjeta Kramar Fijavž
želi na vrnjenem seznamu videti najbolj relevantne strani na vrhu. In kako spletni iskalnik določi relevantnost strani? To je ena najzahtevnejših nalog iskalnika, in prav zaradi pametnega razvrsčanja je Google, takoj ko se je pojavil, pometel s konkurenco.
Spletni iskalniki rangirajo spletne strani na podlagi dveh osnovnih kriterijev. Prvi kriterij je vsebinski. Tu upostevajo, kolikokrat se iskani izraz pojavi na posamezni spletni strani, ali se pojavi v naslovu, podnaslovu, poudarjeno ipd. Drugi kriterij pa je pomembnost strani, in tega si bomo podrobneje ogledali. Algoritem razvrsčanja strani po pomembnosti PageRank sta Brin in Page prvič opisala v članku [3] in je se vedno srce iskalnika Google. Podrobnejsi opis čelotnega postopka delovanja spletnih iskalnikov najde radovedni braleč v izvrstni knjigi [7].
V naslednjem razdelku si bomo ogledali osnovno idejo, na kateri temelji algoritem PageRank. Definirali bomo Googlovo matriko in videli, da zelimo poiskati lastni vektor te matrike k lastni vrednosti 1. Zato bomo obravnavali spektralne lastnosti pozitivnih matrik in utemeljili konvergenčo algoritma. Na konču bomo pokazali obstoj iskanega lastnega vektorja tudi s pomočjo Banačhovega izreka o negibni točki.
Pri tem poudarimo, da nas predvsem zanima teoretično ozadje problema in uporaba metod linearne algebre oziroma funkčionalne analize. Konkretnega izračuna ne bomo obravnavali.
Rangiranje spletnih strani
Posvetimo se vprasanju, kako določiti pomembnost spletne strani. Povezave med spletnimi stranmi si lahko predstavljamo kot demokratične volitve. Avtor spletne strani naredi povezave na druge strani, ki se mu zdijo pomembne (kot glasovi na volitvah). Skupek teh subjektivnih glasov da globalni pomen strani (zmagovalča volitev).
Uvedimo najprej nekaj oznak. Denimo, da imamo n spletnih strani:
W = {Wk | k = 1,...,n}.
Za posamezno stran Wk označimo z Ik := {i | Wi ^ Wk} mnozičo indeksov vseh vstopnih povezav, z Ok := {j | Wk ^ Wj} mnozičo indeksov vseh izstopnih povezav ter z xk > 0 rang strani Wk. Kako čim bolje definirati
Xk ?
Stran je gotovo pomembnejsa, če nanjo kaze več povezav, torej bi lahko za rang strani vzeli stevilo vstopnih povezav. Tako so delali prvi iskalniki, a dobljeni seznami strani niso bili najboljsi, poleg tega je tudi hitro prislo do zlorab (ustvarjalči strani so npr. umetno ustvarili povezave na določeno stran). Brin in Page sta tu odgovorila:
Stran je pomembna, ce nanjo kaze druga pomembna stran!
122
Obzornik mat. fiz. 61 (2014) 4
Kako išce Google?
Njuna definicija ranga strani je zato rekurzivna:
:=E |||' k =
ie/fc
(1)
Pri tem sta spet uporabila nacelo demokratičnosti in uteZila glasove volivcev glede na stevilo oddanih glasov |Oj|. Torej, če ima stran Wi veliko izhodnih povezav, je njen kazalec na določeno stran Wk proporcionalno manj vreden. Ob tem predpostavimo, da nobena stran ne pokaze nazaj nase. Enacba je na prvi pogled videti krozno odvisna. Poglejmo, ali je res tako.
Svetovni splet si lahko predstavljamo kot ogromen usmerjen graf na n tockah (tj. spletnih straneh), povezanih s spletnimi povezavami. Priredimo mu utezeno matriko sosednosti H velikosti n x n, kjer je
H
TTITT , ce Wj ^ Wi
v
0,
(2)
sicer.
Elemente Hij lahko razumemo kot verjetnosti dostopanja do strani Wi s
strani Wj.
Zberimo range strani v vektor rangov x := (x\,x2,..., xn)T. Rekurzivno
enacbo (1) lahko zapisemo v matricni obliki
x = Hx.
(3)
Iscemo torej lastni vektor matrike H, ki pripada lastni vrednosti 1. Takemu vektorju recemo tudi fiksen ali negiben vektor matrike H. Od tu naprej bomo privzeli, daje vektor rangov normiran, tj. ||x||i = Y^a= i Xi = 1. Zanima nas, ali normiran vektor rangov, ki ustreza enacbi (3), vedno obstaja in ali je enolicno dolocen.
Primer 1. Vzemimo za primer usmerjen graf na sliki 1. Njegova utezena matrika sosednosti je
H
njeni fiksni vektorji pa so oblike a(12, 4, 9, 6)T, a € R. Normiran vektor rangov je v tem primeru en sam, njegove koordinate na 2 decimalni mesti natancno so: x = (0.39, 0.13, 0.29, 0.19)T. Po pomembnosti razvrscene strani so tako: 1, 3, 4,2. Ce bi upostevali le stevilo vstopnih povezav, bi bil vrstni red drugacen: 3,1&4,2. Ce pa pri definiciji ranga ne bi upostevali utezi -joiTj glede na stevilo izhodnih povezav (oziroma postavili v matriki H vse nenicelne vrednosti na 1), rekurzivna enacba (1) sploh ne bi imela nenicelne resitve!
0	0	1	1/2\
1/3	0	0	0
1/3	1/2	0	1/2
U/3	1/2	0	0
121-131
123
Marjeta Kramar Fijavž
Slika 1. Primer usmerjenega grafa na 4 točkah.
Pozitivne matrike
Oglejmo si nekaj rezultatov iz teorije pozitivnih matrik, ki jih bomo pri nasi obravnavi potrebovali.
Definicija 1. Vektor x = (xi,..., xn)T imenujemo pozitiven vektor, če so vse njegove koordinate pozitivna realna Števila: xi > 0. Matriko A = (a imenujemo pozitivna matrika3, ce enako velja za vse njene elemente:
Za vektorja x = (x1,..., xn)T in y = (y1,..., yn)T € Rn označimo
Naslednje lastnosti je enostavno preveriti, dokaz prepusčamo bralcu. Lema 1. Za poljubno matriko A = (aij)nxn veljajo trditve:
(i)	A je pozitivna, natanko tedaj, ko je Ax > 0 za vse x > 0.
(ii)	|Ax| < |A| |x| za poljuben vektor x.
3Nekateri avtorji tako matriko imenujejo nenegativna ter za pozitivne matrike zahtevajo, da so vsi cleni strogo pozitivni: a^ > 0.
x < y ^^ x, < yi za vse i = 1,..., n. Absolutna vrednost vektorja x = (x1,..., xn)T € Cn je vektor
124
Obzornik mat. fiz. 61 (2014) 4
Kako išce Google?
(iii) Če je A pozitivna matrika, je \Ax\ < A \x\ za poljuben vektor x.
Ponovimo se nekaj izrazov. Spekter matrike A je množica vseh lastnih vrednosti matrike,
a(A) := (A € C \ 3x = 0 : Ax = Ax}.
Spektralni radij matrike A je enak
r(A) := max(\A\ \ A € ct(A)}.
Teorija pozitivnih matrik je doživela razcvet v začetku 20. stoletja. Eden od pionirjev te teorije je nemski matematik Perron4, ki je v članku [9] dokazal naslednji izrek:
Izrek 2 (Perron, 1907). Naj bo A pozitivna matrika s spektralnim radijem r = r(A). Potem je r lastna vrednost matrike A in pripadajoči lastni vektor je pozitiven.
Dokaza izreka na tem mestu ne bomo navedli, radovedni bralec ga najde npr. v [8, 2]. V članku [8] je prikazanih tudi veliko primerov uporabe Per-ronovega izreka na razlicnih podrocjih, od numericne matematike in teorije verjetnosti do biologije in ekonomije.
Definirajmo se nekaj pojmov. Pozitivno matriko A imenujemo:
(i)	vrstično stohastična, če je ^jj=1 aij = 1 za vse i = 1,..., n;
(ii)	stolpčno stohastična, če je ^j=1 aij = 1 za vse j = 1,..., n;
(iii)	stohastična, če je vrstično in stolpčno stohastična.
Utezena matrika sosednosti H v primeru 1 je stolpčno stohastična, ni pa vrstično stohastična.
Trditev 3. Za vrstično ali stolpčno stohastično matriko A je spektralni radij r(A) = 1 in je lastna vrednost matrike A.
Dokaz. Najprej se spomnimo znane Gelfandove enačbe za spektralni radij matrike:1
r(A) = lim ||Ak||k,	(4)
ki velja za katerokoli matrično normo (dokaz najdemo npr. v [10, izrek 8], [2, Prop. 3.1.3] ali [7, Example 7.10.1]). Za vrstično stohastično matriko A je
j
^ := max \aj\ = 1, ~ ~ j=1
4Oskar Perron (1880-1975)
121-131
125
Marjeta Kramar Fijavž
za stolpcno stohasticno pa
n
i =L
i= 1
Zaradi enačbe (4) je tako v vsakem primeru r(A) = 1.
Naj bo e := (1,..., 1)T in A vrstično stohastična matrika. Potem je Ae = e, torej je r(A) = 1 lastna vrednost matrike A. Ce je A stolpcno stohastična, je AT vrstično stohastična in po gornjem velja 1 € a (AT) =
V dokazu zadnje trditve opazimo, da je za vrstično stohastično matriko normiran lastni vektor k lastni vrednosti 1 enak n(1, • • •, 1)T in je strogo pozitiven. Pri stolpčno stohastični matriki pa zaradi Perronovega izreka vemo le, da je lastni vektor k lastni vrednosti 1 pozitiven. Nikakor pa ne moremo se ničesar reči o dimenziji ustreznega lastnega podprostora (to je o enoličnosti normiranega lastnega vektorja).
Perron je v [9] ob predpostavki, da so vsi členi matrike strogo pozitivni (aij > 0), pokazal tudi močnejso različičo izreka 2. Tu velja, da je lastni vektor k lastni vrednosti r strogo pozitiven in do skalarja natančno določen. Nadomestimo pogoj o strogi pozitivnosti z neko splosnejso lastnostjo matrike, za katero bomo videli, da je lepo povezana s strukturo grafa, ki ji pripada (glej trditev 8).
Definicija 2. Matrika A = (aij)nxn je razcepna, če obstaja taka neprazna indeksna mnoziča M ^ {1,..., n}, da je linearen podprostor
invarianten za A. Matrika, za katero to ne velja, je nerazcepna.
Opozorimo, da je ta lastnost matrike odvisna od izbire baze: za obrn-ljivo matriko P je matrika P-1AP lahko razčepna, čeprav je A nerazčepna, in obratno! Vendar pa hitro opazimo, da permutačija standardnih baznih vektorjev (ne)razčepnost ohranja. Torej je A razčepna natanko tedaj, ko lahko standardne bazne vektorje Rn preuredimo tako, da je za neki indeks 1 < k < n podprostor
invarianten za A. Matrika v preurejeni bazi je torej blocno trikotna. Preureditev baze pomeni, da v matriki na enak nacin permutiramo vrstice in stolpce. Dobili smo novo karakterizacijo nerazcepnosti, ki jo je enostavneje preveriti.
a(A).
Jm := {(xi,..., Xn)T i Xi = 0 za i € M}
Jk := {(xi, . . . ,Xn)T i Xfc+1 = ■ ■ ■ = Xn = 0}
(5)
126
Obzornik mat. fiz. 61 (2014) 4
Kako išce Google?
Trditev 4. Matrika A je razcepna, ce obstaja taka permutacijska matrika P, da je matrika PTAP blocno trikotna:
pri čemer sta X in Z kvadratni matriki.
Primer 2. Navedimo dva primera nerazcepnih matrik:
(i)	matrika A = (aij)nxn s strogo pozitivnimi nediagonalnimi elementi: aij > 0 za i = j, ter
(ii)	permutacijska matrika
Pojem (ne)razcepnosti je uvedel nemSki matematik F. G. Frobenius5. V delu [6] je pokazal, da Perronov izrek za strogo pozitivne matrike velja tudi za nerazcepne pozitivne matrike.
Izrek 5 (Perron-Frobenius, 1912). Naj bo A pozitivna nerazcepna matrika. Potem je spektralni radij r = r(A) lastna vrednost matrike A, pri-padajoc lastni podprostor je enorazsezen in napet na strogo pozitiven lastni vektor z = (zi,..., zn)T.
Dokaz. Najprej uporabimo Perronov izrek 2, ki nam zagotavlja obstoj pozitivnega vektorja z = (zi,..., zn)T, zi > 0, za katerega velja Az = rz.
Denimo, da z ni strogo pozitiven. Bazne vektorje preuredimo tako, da velja: zi > 0 za i = 1,..., k in zi = 0 za i = k + 1,..., n. To pomeni, da za poljuben y € Jk (glej (5)) obstaja c > 0, za katerega je |y| < c ■ z. Uporabimo lemo 1 in dobimo
od koder sledi € Jk. Torej je Jk invarianten podprostor za A, kar je v nasprotju z nerazcepnostjo A. Vektor z je zato strogo pozitiven.
5Ferdinand Georg Frobenius (1849-1917)
/0 1 0 0\ . ... ... 0 0 ... 1
V1 0 ••• 0
|Ay| < A|y| < c Az = cr ■ z,
121-131
127
Marjeta Kramar Fijavž
Pokazati moramo se, da je lastni podprostor, ki pripada lastni vrednosti r, enorazseZen. Denimo, da ima A poleg zgoraj omenjenega strogo pozitivnega lastnega vektorja z se en neniceln lastni vektor y € Rn k lastni vrednosti r (realnost vektorja y lahko predpostavimo zato, ker sta tako matrika A kot lastna vrednost r realni; sicer obravnavamo realni in imaginarni del posebej). Potem lahko najdemo tako stevilo c € R, da je vektor x := z — cy pozitiven, a ne strogo pozitiven. Zdaj ponovimo razmislek iz prejsnjega odstavka in nenicelnim koordinatam vektorja x priredimo podprostor J m , ki je invarianten za A. To je ponovno v nasprotju z nerazcepnostjo A, zato je z = cy.	■
V resnici sta Perron in Frobenius ob istih predpostavkah dokazala se malce vec: za spektralni radij velja: r > 0 in r je pol prvega reda resolvente R(-, A) := ( ■ —A)-1, dokaz tega najdemo npr. v [2]. Strogo pozitiven vektor z v izreku imenujemo Perronov vektor za A in je določen do mnozenja s skalarji natancno (tj. je enolicen, ce privzamemo ||z||i = 1).
Ce zdruzimo trditev 3 in izrek 5, dobimo naslednjo posledico za stoha-sticne matrike:
Posledica 6. Ce je pozitivna nerazcepna matrika A vrstično ali stolpčno stohastična, je spektralni radij r(A) = 1 € ^(A), pripadajoč lastni podprostor je enorazsečen in napet na strogo pozitiven lastni vektor.
Omenimo se eno lastnost pozitivnih matrik, ki ima pomembno vlogo v limitnih procesih. Pozitivno nerazcepno matriko imenujemo primitivna, ce je r(A) njena edina lastna vrednost na spektralni kroznici (A € C | |A| = r(A)}. Naslednjo karakterizacijo primitivnosti je podal ze Frobenius (najdemo jo npr. v [7]).
Lema 7. Pozitivna matrika A je primitivna natanko tedaj, ko je pri nekem m > 0 matrika Am strogo pozitivna.
Googlova matrika
Vrnimo se zdaj k resevanju enacbe x = Hx v (3), katere resitev je iskani vektor rangov. Zanima nas torej, ali obstaja enolicno dolocen normiran strogo pozitiven vektor, ki jo resi. V luci posledice 6 bi ze imeli pozitiven odgovor, ce bi bila matrika H pozitivna, nerazcepna ter vrsticno ali stolpcno stohasticna.
Kaj od tega velja za utezeno matriko sosednosti H, podano z (2)? Gotovo je pozitivna, a ni nujno stohasticna, saj strani brez izstopnih povezav pripada v H nicelni stolpec. Kakor hitro pa neka stran Wj ima vsaj eno izhodno povezavo, je
n 1 £ Hj = £ ¿1 = L
i= i	¿eo^ jl
128	Obzornik mat. fiz. 61 (2014) 4
Kako išce Google?
Ce torej vse ničelne stoplce v H nadomestimo s stolpcem (n, n, • • •, n)T ,
dobimo stolpčno stohastično matriko. Označimo jo s H.
Brin in Page sta ta korak utemeljila s t. i. naključnim obiskovalcem. Uporabnik z verjetnostjo Hij zapusti stran Wj po povezavi na stran Wi. Ce pa pristane na strani brez izhodnih povezav, se od tam resi tako, da v naslovno vrstico brskalnika naključno vtipka neki nov naslov in pri tem skoči na novo stran z verjetnostjo n.
Kako pa je z nerazčepnostjo matrike H (oziroma H)? Odgovor nam da naslednja trditev (dokazana je npr. v [2, Prop. 6.1.1]).
Trditev 8. Matrika sosednosti nekega grafa je nerazcepna natanko tedaj, ko je pripadajoč graf krepko povezan (tj. za vsak i = j obstaja v grafu pot od Wi do Wj in nazaj).
Očitno pri spletu to ne velja! Brin in Page sta v odgovor na to tezavo definirala Googlovo matriko kot
G := aH + (1 - a)S,	(6)
kjer za matriko S velja Sij = n za vse 1 < i, j < n, a € [0,1] pa je neki parameter. Interpretačija je podobna kot zgoraj: naključni obiskovaleč spletne strani se kdaj pa kdaj odloči ročno vtipkati neki nov naslov, tudi če na strani obstajajo izhodne povezave.
Googlova matrika G je strogo pozitivna in ji očitno pripada krepko povezan graf. Po trditvi 8 je torej G nerazčepna. Ker je tudi stolpčno sto-hastična, nam poslediča 6 zagotavlja obstoj enoličnega strogo pozitivnega enotskega fiksnega vektorja matrike G.
Posledica 9. Normiran strogo pozitiven vektor rangov je rečitev enačbe
x = Gx, ||x||i = 1,	(7)
vedno obstaja in je enoličcno določcen.
Iskani vektor lahko izračunamo z uporabo enostavne numerične metode, imenovane potenčna metoda,, pri kateri na začetnem priblizku uporabljamo vedno večje potenče matrike G. Definirajmo zaporedje priblizkov x(k) z
x(0) > 0, ||x(0)||i = 1 (začetni vektor), x(k) = Gx(k-1) = Gk x(0), k = 1,2,...
Opazimo, daje matrika G tudi primitivna (lema 7), torej je A1 = 1 njena edina lastna vrednost na enotski krozniči. S spektralno teorijo pozitivnih matrik lahko pokazemo, da x(k) vedno konvergira k lastnemu vektorju, ki
121-131
129
Marjeta Kramar Fijavž
pripada dominantni lastni vrednosti 1 matrike G (dokaz je npr. vsebovan v [2]).
V resnici pravi izračun seveda ni tako enostaven. Googlova matrika je ogromna, velikost gre v milijarde. Za (čim hitrejse) potenciranje tako velikih matrik je treba uporabiti ustrezne algoritme, ki jih na tem mestu ne bomo obravnavali.
Namenimo le se nekaj besed parametru a. Povezan je z drugo največjo lastno vrednostjo A2 matrike G, velja |A2| < a, zato vpliva na hitrost konvergence potenčne metode. To pomeni, da bo za manjse a metoda hitreje konvergirala. Hkrati zelimo imeti čim večji a, da bodo rangi dovolj različni med seboj (pri a = 0 dobimo G = S in vektor rangov x = (1,..., 1)T). Parameter a utezi preferenčo obiskovalča do potovanja po povezavah v grafu. Google uporablja a = 0.85.
Banachov izrek o negibni tocki
Za koneč si poglejmo se elegantnejsi dokaz obstoja vektorja rangov s pomočjo funkčionalne analize. Pri tem si pomagamo z znanim in zelo uporabnim izrekom, ki velja v poljubnem polnem metričnem prostoru (M, d).
Preslikavo T : M ^ M imenujemo skrčitev, če obstaja tako pozitivno stevilo q < 1, da za vse x, y € M velja
d (T(x), T(y)) < q ■ d(x,y).
Število q v zgornji enačbi imenujemo skrčitvena oz. Lipschitzeva konstanta.
Izrek 10 (Banach, 1922). Naj bo (M, d) poln metričen prostor in naj bo preslikava T : M ^ M skrčitev. Potem obstaja natanko ena negibna (ali fiksna) točka preslikave T, tj. x* € M, za katero velja T(x*) = x*. Se več, če za poljuben x(0) € M definiramo
x(k) := T(x(fc-1)) , k = 1, 2,..., potem zaporedje (T (x(fc))) fceN konvergira k x*, ko gre k ^ ro.
Izrek se imenuje Banačhov6 izrek o negibni točki (ali tudi Banačhovo skrŠčitveno naŠčelo) in njegov dokaz braleč najde npr. v uŠčbeniku [11, izrek 14.14].
Pokazimo, kako lahko ta izrek uporabimo v nasem primeru. Vzemimo M := {x € Rn | x > 0, ||xy1 = 1} in d(x,y):= ||x - y||1.
6Stefan Banach (1892-1945)
130
Obzornik mat. fiz. 61 (2014) 4
Kako išce Google?
Ni težko videti, da je (M, d) poln metricni prostor. Opazimo tudi, da za Googlovo matriko G velja: G(M) C M (uporabimo lemo 1(i) in dejstvo, da stolpcno stohasticna matrika ohranja || ■ ||i-normo pozitivnega vektorja). Za konstantno matriko S = i1) je Sx = 1 (1,..., 1)T za vse x € M
\n)nxnJ	nv ' ' '
in zato
S(x - y) = (0,..., 0)T za poljubna x, y € M.	(8)
Po zgornjem in zaradi ||ii ||i = 1 tako dobimo
||Gx - Gy|i = ||aHH(x - y) + (1 - a)S(x - y)11
< a||iH||i|x - y|i = a||x - y||i
za vse x,y € M. Torej je G skrcitev na M s skrcitveno konstanto a. Po Banachovem izreku o negibni točki je zato enačba (7) vedno enolično resljiva in potencna metoda konvergira.
Priznati moramo, da je nas kratki dokaz o obstoju enolicnega vektorja rangov mocno odvisen od lastnosti (8) matrike S. Ce le-to malo spremenimo tako, da njeni elementi niso vec konstantni, a se vedno ostane strogo pozitivna in stolpcno stohasticna, nas dokaz ne bo vec dober, medtem ko dokaz s pomocjo Perron-Frobeniusove teorije se vedno deluje. Taka sprememba je seveda smiselna, saj lahko vrednosti Sij interpretiramo kot verjetnosti skoka s strani Wj na stran Wi, ki niso nujno vse med seboj enake (strani z bolj podobno vsebino bolj asociirajo druga na drugo, ceprav ne vsebujejo direktne povezave).
LITERATURA
[1]	David Austin, How Google Finds Your Needle in the Web's Haystack, Feature Column from the AMS, december 2006.
[2]	A. Batkai, M. Kramar FijavZ in A. Rhandi, Positive Operator Semigroups and Applications, 17th Internet Seminar on Evolution Equations 2013/14, skripta, http: //isem17.unisa.it, dostopano: 3. 11. 2014.
[3]	Sergey Brin in Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 33 (1998), 107-117.
[4]	Kurt Bryan in Tanya Leise, The $25,000,000,000 Eigenvector. The Linear Algebra behind Google, SIAM Review 48 (2006), 569-581.
[5]	Matthias Frick, Mathematik hinter Google, Zulassungsarbeit, Eberhard-Karls Universität Tubingen, 2007.
[6]	G. Frobenius, Über Matrizen aus nicht negativen Elementen, S.-B. Pre-uss, Akad. Wiss. (Berlin), 456-477.
[7]	Amy Langville in Carl Meyer, Google 's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, 2006.
[8]	C. R. MacCluer, The Many Proofs and Applications of Perron's Theorem,, SIAM Review 42 (2000), 487-498.
[9]	Oskar Perron, Zur Theorie der Matrizen, Math. Ann. 64 (1907), 248-263.
[10]	Ivan Vidav, Linearni operatorji v Banachovih prostorih, DMFA - zaloznistvo, Ljubljana, 1982.
[11]	JoZe Vrabec, Metricni prostori, DMFA - zaloZnistvo, Ljubljana, 1990.
121-131
131