Google PageRank: Relevance webových

Google PageRank: Relevance webov´ ych str´ anek a probl´ em vlastn´ıch ˇ c´ısel

Bakal´ aˇrsk´ a pr´ ace

Studijn´ı program: Studijn´ı obory:

B1101 – Matematika 7504R015 – Matematika se zamˇeˇren´ım na vzdˇeláván´ı 7507R036 – Anglický jazyk se zamˇeˇren´ım na vzdˇeláván´ı

Autor práce: Vedouc´ı práce:

Mark´ eta Hejlov´ a Martin Pleˇsinger

Liberec 2015

Google’s PageRank: Ranking of web pages and the eigenvalue problem

Bachelor thesis

Study programme: Study branches:

B1101 – Mathematics 7504R015 – Mathematics for Education 7507R036 – English for Education

Author: Supervisor:

Mark´ eta Hejlov´ a Martin Pleˇsinger

Liberec 2015

Tento list nahrad’te originálem zadán´ı.

Prohl´ aˇsen´ı Byla jsem seznámena s t´ım, ˇze na mou bakaláˇrskou práci se plnˇe vztahuje zákon ˇc. 121/2000 Sb., o právu autorském, zejména § 60 – ˇskoln´ı d´ılo. Beru na vˇedom´ı, ˇze Technická univerzita v Liberci (TUL) nezasahuje do m´ ych autorsk´ ych práv uˇzit´ım mé bakaláˇrské práce pro vnitˇrn´ı potˇrebu TUL. Uˇziji-li bakaláˇrskou práci nebo poskytnu-li licenci k jej´ımu vyuˇzit´ı, jsem si vˇedoma povinnosti informovat o této skuteˇcnosti TUL; v tomto pˇr´ıpadˇe má TUL právo ode mne poˇzadovat u ´hradu náklad˚ u, které vynaloˇzila na vytvoˇren´ı d´ıla, aˇz do jejich skuteˇcné v´ yˇse. Bakaláˇrskou práci jsem vypracovala samostatnˇe s pouˇzit´ım uvedené literatury a na základˇe konzultac´ı s vedouc´ım mé bakaláˇrské práce a konzultantem. Souˇcasnˇe ˇcestnˇe prohlaˇsuji, ˇze tiˇstˇená verze práce se shoduje s elektronickou verz´ı, vloˇzenou do IS STAG.

Datum:

Podpis:

Anotace Bakaláˇrská práce se zamˇeˇruje na spektráln´ı vlastnosti nˇekter´ ych speciáln´ıch matic a jejich souvislosti s Markovov´ ymi ˇretˇezci a teori´ı orientovan´ ych graf˚ u. Jedná se zejména o nezáporné, kladné, (sub)stochastické, (ne)rozloˇzitelné a (im)primitivn´ı matice. V´ yklad je v pr˚ ubˇehu celého textu doprovázen praktick´ ym pˇr´ıkladem, ˇc´ımˇz je práce motivována. Tento pˇr´ıklad se t´ yká nalezen´ı tzv. PageRank˚ u jednotliv´ ych webov´ ych stránek na internetu. PageRank lze reprezentovat jako m´ıru d˚ uleˇzitosti webové stránky. Koncept PageRanku vyuˇz´ıvá napˇr´ıklad internetov´ y vyhledávaˇc Google. Práce se zab´ yvá zp˚ usobem, jak lze PageRank definovat a odhaluje nˇekteré obt´ıˇznosti, které se objevuj´ı v samotné definici a pˇri v´ ypoˇctu PageRank˚ u. Tyto obt´ıˇze lze ovˇsem snadno obej´ıt s vyuˇzit´ım vlastnost´ı pˇr´ısluˇsn´ ych matic.

Kl´ıˇ cov´ a slova: nezáporné matice; kladné matice; (sub)stochastické matice; (ne)rozloˇzitelné matice; (im)primitivn´ı matice; PageRank vektor; googlovská matice; Markovovy ˇretˇezce; orientované grafy; mocninná metoda; Perronovo vlastn´ı ˇc´ıslo; Perron˚ uv vlastn´ı vektor

5

Abstract The bachelor thesis is focused on the spectral properties of some particular matrices and their connections to Markov chains and the theory of digraphs. In particular we concentrate on nonnegative, positive, (sub)stochastic, (ir)reducible, and (im)primitive matrices. The theory is continuously demonstrated on a practical example, which works also as a motivation. This example is to determine so-called PageRanks of individual internet webpages. This PageRank can be interpreted as a measure of imparotance of the given webpage. The PageRank concept is employed for example by Google web search engine. This thesis analyzes the PageRank definition and reveals some difficulties that appear in the definition as well as in the computation of the PageRank. Hovewer, these difficulties can be easily avoided by using properties of the abovementioned matrices.

Key words: nonnegative matrices; positive matrices; (sub)stochastic matrices; (ir)reducible matrices; (im)primitive matrices; PageRank vector; Google matrix; Markov chain; digraphs; power method; Perron eigenvalue; Perron eigenvector

6

Podˇ ekov´ an´ı Ráda bych podˇekovala svému vedouc´ımu bakaláˇrské práce Martinu Pleˇsingerovi za jeho trpˇelivou pomoc, odborné veden´ı a ochotu pˇri zpracován´ı této práce.

7

Obsah

Anotace

5

Abstract

6

Seznam obr´ azk˚ u

10

Seznam tabulek

11

Pouˇ zit´ e znaˇ cen´ı

12

´ Uvod

14

1 Z´ akladn´ı pojmy 1.1 Vlastn´ı ˇc´ısla a vlastn´ı vektory 1.2 Normy vektor˚ u a matic . . . . 1.3 Základn´ı pojmy teorie graf˚ u . 1.4 Co je to PageRank? . . . . . .

16 16 18 20 21

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

I Existence PageRank vektoru

24

2 Nez´ aporn´ e a stochastick´ e matice 2.1 Aritmetika nezáporn´ ych a kladn´ ych matic . . . . . . . . . . . . . . . 2.2 Stochastické matice: spektráln´ı polomˇer . . . . . . . . . . . . . . . . . 2.3 Stochastické matice: (lev´ y) Perron˚ uv vlastn´ı vektor . . . . . . . . . . 2.4 Kladné matice: spektráln´ı polomˇer a (prav´ y) Perron˚ uv vlastn´ı vektor

25 25 29 30 31

3 Nerozloˇ zitelnost matic 3.1 Stochastické matice: jednoznaˇcnost (levého) Perronova vlastn´ıho vektoru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 (Ne)rozloˇzitelné matice . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Kladné matice: jednoznaˇcnost (pravého) Perronova vlastn´ıho vektoru 3.4 Nezáporné nerozloˇzitelné matice . . . . . . . . . . . . . . . . . . . . .

34 34 35 39 39

4 Matice hyperlink˚ u obecnˇ e nen´ı stochastick´ a ani nerozloˇ ziteln´ a. Co s t´ım? 42 4.1 Matice hyperlink˚ u je obecnˇe substochastická. . . . . . . . . . . . . . . 42

8

4.2

Stochastická matice hyperlink˚ u je obecnˇe rozloˇzitelná. . . . . . . . . . 43

II V´ ypoˇ cet PageRank vektoru

46

5 Mocninn´ a metoda 5.1 Diagonalizovatelné matice . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Mocninná metoda pro diagonalizovatelné matice . . . . . . . . . . . . 5.3 Mocninná metoda pro obecné ˇctvercové matice . . . . . . . . . . . . .

47 47 48 50

6 V´ ypoˇ cet Perronova vlastn´ıho vektoru 6.1 (Im)primitivn´ı matice . . . . . . . . . . . . . 6.2 Spektráln´ı vlastnosti (im)primitivn´ıch matic 6.3 Testován´ı (im)primitivity matice . . . . . . 6.4 Mocninná metoda pro googlovskou matici .

52 52 54 57 60

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Z´ avˇ er

64

A PageRank vektor modelov´ eho internetu z obr´ azku 1.1

65

Reference

69

9

Seznam obr´ azk˚ u

1.1

Schéma jednoduchého internetu se ˇsesti stránkami . . . . . . . . . . . 21

3.1 3.2

Schéma jednoduchého internetu se dvˇema nezávisl´ ymi komponentami 36 Schéma jednoduchého internetu s rozloˇzitelnou matic´ı hyperlink˚ u . . 37

4.1

Schéma jednoduchého internetu se substochastickou matic´ı hyperlink˚ u 42

6.1

Schéma jednoduchého internetu se stochastickou nerozloˇzitelnou matic´ı, která je periodická . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Schéma jednoduchého internetu se stochastickou nerozloˇzitelnou matic´ı, která je periodická, po permutaci vrchol˚ u (pˇreˇc´ıslován´ı stránek). 54 Pˇrehled vztah˚ u mezi jednotliv´ ymi druhy ˇctvercov´ ych matic . . . . . . 62

6.2 6.3

A.1 Konvergence PageRank vektoru, vliv startovac´ıho vektoru . . . . . . 67 A.2 Konvergence PageRank vektoru, vliv parametru α . . . . . . . . . . . 68

10

Seznam tabulek

6.1

V grafu (internetu) na obrázku 1.1 existuje cesta délky pˇet mezi libovoln´ ymi dvˇema vrcholy (stránkami). . . . . . . . . . . . . . . . . . 61

11

Pouˇ zit´ e znaˇ cen´ı Matice a vektory Znaˇ cen´ı

V´ yznam

A ∈ Rm×n A ∈ Cm×n i A AT AH A−1 A−T A−H sp(A)

reálná matice s rozmˇery m krát n a s prvky aj,k komplexn´ı matice s rozmˇery m krát n a s prvky aj,k imaginárn´ı jednotka, i2 = −1 matice komplexnˇe sdruˇzená s prvky aj,k transponovaná matice matice transponovaná, komplexnˇe sdruˇzená AH = AT inverzn´ı matice ke ˇctvercové regulárn´ı matici A matice (A−1 )T = (AT )−1 , kde A je ˇctvercové regulárn´ı matice (A−1 )H = (AH )−1 , kde A je ˇctvercové regulárn´ı spektrum ˇctvercové matice A (mnoˇzina vˇsech vlastn´ıch ˇc´ısel) %(A) spektráln´ı polomˇer ˇctvercové matice A K (A) spektráln´ı kruˇzice matice A K (A) = {%(A)(cos(ϕ) + i sin(ϕ)) : 0 ≤ ϕ ≤ 2π} ⊂ C det(A) determinant ˇctvercové matice A A > 0, A ≥ 0 reálná matice A, jej´ıˇz prvky splˇ nuj´ı aj,k > 0, aj,k ≥ 0 tj. kladná, resp. nezáporná matice A < 0, A ≤ 0 reálná matice A, jej´ıˇz prvky splˇ nuj´ı aj,k < 0, aj,k ≤ 0 n×n I∈R jednotková matice ej j-t´ y sloupec jednotkové matice I e vektor e = [1, . . . , 1]T n |x| ∈ R vektor absolutn´ıch hodnot x = [|ξ1 |, . . . , |ξn |]T |A| ∈ Rm×n matice absolutn´ıchP hodnot s prvky |aj,k | kxkp p-norma vektoru ( j |ξj |p )1/p , p = 1, 2, . . . kxk∞ maximová norma vektoru maxj |ξj | kAkp p-norma matice maxkxkpP =1 kAxkp kAk∞ ∞-norma matice maxj ( k |aj,k |)

12

Speci´ aln´ı nez´ aporn´ e matice a nez´ aporn´ e vektory Znaˇ cen´ı

V´ yznam

π ∈ Rn

lev´ y Perron˚ uv vlastn´ı vektor stochastické matice zvan´ y také PageRank vektor, jedná-li se o (opravenou) matici hyperlink˚ u, resp. googlovskou matici dangling node vektor stochastická matice (substochastická) matice hyperlink˚ u (substochastická) oprava matice hyperlink˚ u (stochastická) opravená matice hyperlink˚ u (stochastická) teleportaˇcn´ı matice (stochastická) googlovská matice, α ∈ (0, 1)

d ∈ {0, 1}n S ∈ Rn×n H ∈ Rn×n D = n1 deT ∈ Rn×n e =H +D H E = n1 eeT ∈ Rn×n e + (1 − α)E G = αH

Grafy a mnoˇ ziny Znaˇ cen´ı

V´ yznam

~ = (V , E ) orientovan´ G y graf s vrcholy vj ∈ V a hranami ej,k ∈ E ~ G(A) orientovan´ y graf matice A M ×W kartézsk´ y souˇcin mnoˇzin M a W |M | poˇcet prvk˚ u koneˇcné mnoˇziny M

Ostatn´ı Znaˇ cen´ı V´ yznam Pj |Pj | BPj r(Pj ) D

j-tá webová stránka poˇcet odkaz˚ u na stránce Pj mnoˇzina vˇsech stránek odkazuj´ıc´ıch na Pj PageRank stránky Pj mnoˇzina vˇsech stránek, které neobsahuj´ı ˇzádn´ y odkaz (dangling nodes)

13

´ Uvod Tato práce pojednává o pojmu PageRank, kter´ y byl v roce 1996 navrˇzen´ y Larry Pagem a Sergeyem Brinem na universitˇe ve Stanfordu jako souˇcást v´ yzkumného projektu. Pˇred t´ımto datem se touto problematikou zab´ yvalo v´ıce vˇedc˚ u, z nichˇz bychom zm´ınili Gabriela Pinskiho a Francise Narina, kteˇr´ı v roce 1976 poprvé definovali problém propojen´ı jako problém vlastn´ıch ˇc´ısel. PageRank je hlavn´ım nástrojem, kter´ y dostává Google na tak dobrou pozici mezi internetov´ ymi vyhledávaˇci a sama spoleˇcnost Google tvrd´ı, ˇze je jej´ım srdcem. M˚ uˇzeme nyn´ı ˇr´ıci, ˇze se jedná o algoritmus, kter´ y pomáhá v ˇrazen´ı vyhledávan´ ych stránek podle d˚ uleˇzitosti a kter´ y urˇcuje to, v jakém poˇrad´ı se budou uˇzivatel˚ um zobrazovat pˇri zadán´ı urˇcitého pojmu do vyhledávaˇce. Pˇresnˇejˇs´ı definic´ı se budeme zab´ yvat pozdˇeji. Cel´ y text ˇcerpá zejména z knihy [17], která objasˇ nuje problematiku PageRanku. Dalˇs´ı informace k tomuto tématu je moˇzné nalézt v [2] nebo v [24]. V matemick´ ych ˇca´stech práce je ˇcerpáno pˇredevˇs´ım z [12] a [14]. Text je rozdˇelen do dvou hlavn´ıch ˇca´st´ı, Existence PageRank vektoru a V´ ypoˇcet PageRank vektoru. Ovˇsem pˇred tˇemito ˇca´stmi se v kapitole 1 zab´ yváme nˇekter´ ymi základn´ımi pojmy z teorie vlastn´ıch ˇc´ısel matic a z teorie graf˚ u, se kter´ ymi dále pracujeme, a proto se s nimi ˇctenáˇr mus´ı seznámit hned na zaˇca´tku. Také je zde uvedena definice PageRanku, ke které se pak vrac´ıme v závˇeru práce. Po prvn´ı kapitole následuje prvn´ı ˇca´st, která obsahuje 3 kapitoly a která se zab´ yvá existenc´ı PageRank vektoru. Kapitola 2 definuje nezáporné a stochastické matice a jejich specifika. V kapitole 3 hovoˇr´ıme o nerozloˇzitelnosti matic a v kapitole 4 ˇreˇs´ıme problém, ˇze matice hyperlink˚ u, se kterou pracujeme v pr˚ ubˇehu celé práce, obecnˇe nen´ı ani stochastická ani nerozloˇzitelná. Tyto dvˇe vlastnosti, jak zjist´ıme, jsou pro existenci PageRanku nepostradatelné a jsou spojené s problematikou uˇzivatele internetu, kter´ y neprocház´ı internetem tak, jak by nám vyhovovalo. Na konci prvn´ı ˇca´sti se ale dozv´ıdáme, ˇze problémy se stochasticitou a (ne)rozloˇzitelnost´ı, lze vyˇreˇsit, a tud´ıˇz v´ıme, ˇze PageRank existuje. V druhé ˇca´sti v´ ykladu se vˇenujeme jiˇz samotnému v´ ypoˇctu PageRank vektoru. Nejprve v kapitole 5 pˇredstavujeme mocninnou metodu, která je nástrojem tohoto v´ ypoˇctu, a pak se v kapitole 6 vrac´ıme k definici PageRanku a nacház´ıme zp˚ usob, jak PageRank vektor neboli také Perron˚ uv vlastn´ı vektor spoˇc´ıtat. V této posledn´ı kapitole také uvád´ıme (im)primitivn´ı matice, které jsou pro pouˇzit´ı mocninné metody k v´ ypoˇctu hledaného vektoru nepostradatelné. Zjist´ıme, ˇze pro imprimitivn´ı matice tato metoda nefunguje, a proto budeme muset ovˇeˇrit, ˇze googlovská matice, pro kterou PageRank poˇc´ıtáme, je primitivn´ı. V závˇeru budeme schopni ovˇeˇrit (im)primitivitu, upravit definici PageRank vektoru a nalezneme tak zp˚ usob, jak ho

14

spoˇc´ıtat. Konkrétn´ı pˇr´ıklad v´ ypoˇctu PageRanku je moˇzné nalézt v pˇr´ıloze A. Cel´ y text má za u ´kol seznámit se s partiemi lineárn´ı algebry, teorie graf˚ u a Markovov´ ych ˇretˇezc˚ u a jejich vzájemn´ ym propojen´ım v rozsahu, kter´ y pˇrekraˇcuje bˇeˇznˇe vykládanou látku základn´ıch kurz˚ u na pˇr´ıkladu praktické u ´lohy a t´ım odhalit zp˚ usob, kter´ ym nejen Google pracuje. PageRank je také vyuˇz´ıván v bibliometrii, v sociáln´ıch a informaˇcn´ıch s´ıt´ıch, v systémech silniˇcn´ıch sit´ı, biologii, chemii ˇci fyzice. Znalost PageRanku mimo jiné m˚ uˇze pomoci majitel˚ um r˚ uzn´ ych webov´ ych stránek vylepˇsovat svou pozici na internetu tak, aby se jejich stránky ukazovaly co nejv´ yˇse.

15

1

Z´ akladn´ı pojmy

Hodnocen´ı d˚ uleˇzitosti nebo v´ yznamnosti webov´ ych stránek je znaˇcnˇe obt´ıˇzné. Ukazuje se, ˇze vhodn´ ym pˇr´ıstupem pˇri takovém hodnocen´ı je pod´ıvat se, které (jiné) stránky na hodnocenou stránku odkazuj´ı, viz [17], [2, kapitola 7.2]. Odkazuj´ı-li na ni stránky d˚ uleˇzité, m˚ uˇzeme i stránku hodnocenou povaˇzovat za jist´ ym z˚ usobem d˚ uleˇzitou. Tedy, struˇcnˇe ˇreˇceno, kaˇzdá webová stránka je d˚ uleˇzitá, pokud je na ni odkázáno jinou d˚ uleˇzitou webovou stránkou. To vˇsak vede k zacyklené“ definici, ” abychom byli schopni hodnotit jednu stránku, mus´ıme b´ yt nejprve schopni zhodnotit stránky jiné. Takto definovaná m´ıra d˚ uleˇzitosti stránky se naz´ yvá PageRank1 . Pˇresná definice je sepsána v sekci 1.4. My nejprve zaˇcneme základn´ımi pojmy z teorie vlastn´ıch ˇc´ısel matic, které se nám budou hodit.

1.1

Vlastn´ı ˇ c´ısla a vlastn´ı vektory

Kl´ıˇcov´ ym nástrojem v této práci budou tzv. vlastn´ı ˇc´ısla a vlastn´ı vektory, coˇz známe ze základn´ıho kurzu lineárn´ı algebry. Pro u ´plnost pˇripomeneme defnici. Definice 1 (Vlastn´ı ˇc´ıslo, vlastn´ı vektor, spektrum, spektráln´ı polomˇer). Necht’ je obecná komplexn´ı ˇctvercová matice A ∈ Cn×n , λ ∈ C je skalár a x, y ∈ Cn , x 6= 0, y 6= 0, nenulové vektory tak, ˇze plat´ı Ax = xλ,

y H A = λy H ,

(1.1)

kde y H = y T . Pak skalár λ nazýváme vlastn´ım (nebo také charakteristickým) ˇc´ıslem matice A, vektor x vlastn´ım, resp. pravým vlastn´ım (nebo také charakteristickým) a vektor y levým vlastn´ım vektorem matice A. Uspoˇrádané dvojici (λ, x) se ˇr´ıká vlastn´ı pár matice A, obdobnˇe (λ, y) je vlastn´ı pár matice AH . Mnoˇzina vˇsech vlastn´ıch ˇc´ısel matice A se nazývá spektrum matice A a znaˇc´ı se sp(A) = {λ ∈ C : ∃x ∈ Cn , x 6= 0, Ax = xλ}. Absolutn´ı hodnota vlastn´ıho ˇc´ısla nejv´ıce vzdáleného od nuly se nazývá spektráln´ı polomˇer matice A a znaˇc´ı se %(A) = max |λ|.

(1.2)

λ∈sp(A) 1

Poznamenejme, ˇze slovo PageRank je sloˇzeninou slov Page a rank, kde druhé ze slov m˚ uˇzeme pˇreloˇzit pr´ avˇe napˇr. jako hodnost nebo hodnocen´ı, ve smyslu pozice v ˇzebˇr´ıˇcku. Slovo Page vˇsak neodkazuje ke slovu (webov´ a) str´ anka, z angl. (web) page, jak bychom se mohli mylnˇe domn´ıvat, ale k Larry Pageovi, autorovi této koncepce hodnocen´ı stránek, viz [17, str. 32, poznámka 1].

16

Je to tedy polomˇer nejmenˇs´ıho kruhu v komplexn´ı rovinˇe, který má stˇred v poˇcátku a obsahuje celé spektrum matice A. Hranici tohoto kruhu K (A) ≡ {%(A) exp(i ϕ) = %(A)(cos(ϕ) + i sin(ϕ)) : 0 ≤ ϕ < 2π} ⊂ C budeme nazývat spektráln´ı kruˇznice matice A. Pˇripomeˇ nme, ˇze vlastn´ı ˇc´ısla jsou koˇreny tzv. charakteristického polynomu χ(λ) = 0, kde χ(λ) ≡ det(Iλ − A) a det(·) znaˇc´ı determinant matice, viz [11, kapitola 1]. Jedn´ım z u ´kol˚ u v této práci bude zjistit, zda je urˇcité vlastn´ı ˇc´ıslo jednoduché nebo v´ıcenásobné. K tomu nám poslouˇz´ı následuj´ı tzv. Shurova pomocná vˇeta (viz [12, vˇeta 1.49]; nezamˇen ˇovat s tzv. Schurovou vˇetou, viz [11, kapitola 2]), na kterou se budeme pozdˇeji odkazovat. Vˇ eta 1 (Schurova pomocná vˇeta). Necht’ A ∈ Cn×n je ˇctvercová matice a λ je jej´ı vlastn´ı ˇc´ıslo. Pak λ je jednoduché vlastn´ı ˇc´ıslo tehdy a jen tehdy, kdyˇz existuje jediný lineárnˇe nezávislý pravý vlastn´ı x, (tedy také) jediný lineárnˇe nezávislý levý vlastn´ı vektor y a zároveˇ n plat´ı y H x 6= 0. D˚ ukaz. Uvaˇzujme matici A s vlastn´ım ˇc´ıslem λ. Uvaˇzujme dále matici B, která je matici A podobná, tj. existuje regulárn´ı matice W tak, ˇze plat´ı B = W AW −1 (poznamenejme, ˇze podobnost je ekvivalence na mnoˇzinˇe ˇctvercov´ ych matic daného rozmˇeru; viz [11, kapitola 1.8]). Pokud existuje jedin´ y lineárnˇe nezávisl´ y prav´ y vlastn´ı vektor x tak, ˇze Ax = xλ, a (tedy také) jedin´ y lineárnˇe nezávisl´ y lev´ y vlastn´ı vektor y tak, ˇze y H A = λy H , potom vektor W x je jedin´ y lineárnˇe nezávisl´ y prav´ y vlastn´ı vektor matice B, tj. B(W x) = (W AW −1 )(W x) = W Ax = (W x)λ, a vektor W −H y ≡ (W −1 )H y je jedin´ y lineárnˇe nezávisl´ y lev´ y vlastn´ı vektor matice B, tj. (W −H y)H B = (y H W −1 )(W AW −1 ) = y H AW −1 = λy H W −1 = λ(W −H y)H . Nav´ıc je pro vektory W x a W −H y splnˇeno (W −H y)H (W x) 6= 0 tehdy a jen tehdy, kdyˇz y H x 6= 0, pˇresnˇeji ˇreˇceno (W −H y)H (W x) = (y H W −1 )(W x) = y H (W −1 W )x = y H x. M´ısto s matic´ı A tedy m˚ uˇzeme v d˚ ukazu pracovat s matic´ı B, resp. s libovoln´ ym reprezentantem tˇr´ıdy matic podobn´ ych matici A. Nejv´ yhodnˇejˇs´ı bude pracovat s tzv. Jordanovým kanonickým tvarem matice A, viz [11, kapitola 1.8]. Nyn´ı pˇrejdeme k vlastn´ımu d˚ ukazu. Nejprve dokáˇzeme implikaci: kdyˇz x, y je jedin´ y lineárnˇe nezávisl´ y prav´ y, resp. lev´ y vlastn´ı vektor a y H x 6= 0, pak λ je jednoduché vlastn´ı ˇc´ıslo.

17

K libovolnému Jordanovu bloku Jm (λ) ∈ Cm×m existuje jedin´ y lineárnˇe nezávisl´ y T m lev´ y vlastn´ı vektor, napˇr. [1, 0, . . . , 0, 0] ∈ C , a jedin´ y lineárnˇe nezávisl´ y prav´ y T m vlastn´ı vektor, napˇr. [0, 0, . . . , 0, 1] ∈ C , a jejich skalárn´ı souˇcin je nenulov´ y, kdyˇz m = 1, resp. je nulov´ y, kdyˇz m > 1. Nav´ıc pravé (resp. levé) vlastn´ı vektory matice v Jordanovˇe kanonickém tvaru odpov´ıdaj´ıc´ı r˚ uzn´ ym Jordanov´ ym blok˚ um (tj. vlastn´ı vektory Jordanov´ ych blok˚ u doplnˇené nulami) jsou vˇzdy lineárnˇe nezávislé. Pokud x (resp. y) je jedin´ y lineárnˇe nezávisl´ y vlastn´ı vektor matice A odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ, pak v Joradnovˇe kanonickém tvaru matice A existuje právˇe jeden Jordan˚ uv blok Jm (λ) odpov´ıdaj´ıc´ı ˇc´ıslu λ. Pokud nav´ıc y H x 6= 0, pak mus´ı b´ yt m = 1, a tedy vlastn´ı ˇc´ıslo λ má násobnost rovnou jedné. Nyn´ı dokáˇzeme opaˇcnou implikaci. Necht’ λ je jednoduché vlastn´ı ˇc´ıslo matice A. Pak v Jordanovˇe kanonickém tvaru matice A odpov´ıdá vlastn´ımu ˇc´ıslu λ jedin´ y Jordan˚ uv blok, kter´ y je nav´ıc velikosti jedna. Pak také existuje jedin´ y lineárnˇe nezávisl´ y prav´ y (resp. lev´ y) vlastn´ı vektor odpov´ıdaj´ıc´ı tomuto vlastn´ımu ˇc´ıslu. Z Jordanova kanonického tvaru je vidˇet, ˇze jejich skalárn´ı souˇcin je nenulov´ y.

1.2

Normy vektor˚ u a matic

Pro v´ yklad bude potˇreba zavést pojmy normy vektoru a normy matice. Zejména proto, abychom mohli dát do vzájemného vztahu spektráln´ı polomˇer a normu ˇctvercové matice. ˇ ıslo Definice 2 (p-norma vektoru). Necht’ x = [ξ1 , ξ2 , . . . , ξn ]T ∈ Cn . C´ !1/p n X kxkp ≡ |ξi |p i=1

nazýváme vektorová p-norma nebo p-norma vektoru, p = 1, 2, . . . Zejména d˚ uleˇzit´ y bude jej´ı limitn´ı pˇr´ıpad. ˇ ıslo Definice 3 (maximová norma vektoru). Necht’ x = [ξ1 , ξ2 , . . . , ξn ]T ∈ Cn . C´ kxk∞ ≡ lim kxkp = max |ξj | p −→ ∞

j

nazýváme maximovou normou vektoru. Kromˇe vektorov´ ych norem budeme potˇrebovat zavést i normy matic. Normu matice lze zavést mnoha zp˚ usoby. My budeme pracovat s maticovou normou generovanou normou vektorovou. Konkrétnˇe p-normou vektoru. ˇ ıslo Definice 4 (p-norma matice (generovaná norma)). Necht’ A ∈ Cm×n . C´

x kAxkp

= max kAxkp = max A kAkp ≡ max x6=0 x6=0 kxkp kxkp p kxkp =1

(1.3)

nazýváme maticová p-norma, pˇr´ıpadnˇe norma generovaná vektorovou normou k · kp , p = 1, 2, . . .

18

Opˇet pro nás bude zaj´ımav´ y jej´ı limitn´ı pˇr´ıpad. ˇ ıslo Definice 5 (∞-norma matice (generovaná norma)). Necht’ A ∈ Cm×n . C´ kAk∞ ≡ lim kAkp = max kAxk∞ p −→ ∞

kxk∞ =1

(1.4)

nazýváme maticová ∞-norma, pˇr´ıpadnˇe norma generovaná vektorovou normou k · k∞ . Takto zadefinované maticové normy nelze obecnˇe snadno vypoˇc´ıtat, aˇz na nˇekteré pˇr´ıpady. Jedná se o normy k · k1 , k · k2 a limitn´ı pˇr´ıpad k · k∞ . Následuj´ıc´ı lemma, nám dá návod, jak vypoˇc´ıtat ∞-normu matice, kterou budeme pozdˇeji potˇrebovat. Lemma 1. Necht’ A ∈ Cm×n . Pak plat´ı kAk∞ = max kAxk∞ = max kxk∞ =1

j

n X

|aj,k |.

(1.5)

k=1

D˚ ukaz je elementárn´ı, viz napˇr. [12, str. 167]. Dále bude potˇrebné následuj´ıc´ı lemma (viz [11, str. 21]). Lemma 2. Je-li A ˇctvercová matice a k · k libovolná maticová norma generovan´ a vektorovou normou k · k, pak plat´ı kAk ≥ %(A)

(1.6)

a také kIk = 1. D˚ ukaz. Pro kaˇzdé vlastn´ı ˇc´ıslo λ matice A existuje alespoˇ n jeden vlastn´ı vektor x takov´ y, ˇze Ax = xλ. Pro tento vlastn´ı pár plat´ı kAkkxk ≥ kAxk = kλxk = |λ|kxk. Nerovnost na zaˇcátku vypl´ yvá pˇr´ımo z definice generované normy (1.3). Protoˇze x 6= 0, tj. kxk = 6 0, dostáváme ihned kAk ≥ |λ| pro libovolné vlastn´ı ˇc´ıslo λ. Z toho plyne kAk ≥ %(A). Poznamenejme, ˇze posledn´ı rovnost vypl´ yvá z tzv. homogenity norem (tj. pro libovoln´ y skalár α a vektor v plat´ı kαvk = |α|kvk), která je jednou z vlastnost´ı definuj´ıc´ıh pojem norma, viz [11, sekce 1.2, definice 1.10].

19

1.3

Z´ akladn´ı pojmy teorie graf˚ u

Pˇri v´ ykladu budeme potˇrebovat i nˇekteré pojmy z teorie graf˚ u. Nˇekteré základn´ı zm´ın´ıme v následuj´ıc´ı definici. Definice 6 (Orientovan´ y graf, vrchol, hrana, cesta, komponenta). Uspoˇrádanou dvojici ~ = (V , E ), G

kde

V = {vj }

a

E = {ej,k ≡ (vj , vk )} ⊆ V × V ,

nazýváme orientovaným grafem. Prvky vj mnoˇziny V nazýváme vrcholy grafu a prvky ej,k ≡ (vj , vk ) mnoˇziny E (tj. uspoˇrádané dvojice vrchol˚ u) nazýváme hrany. ˇ R´ıkáme, ˇze ej,k je hrana vedouc´ı z vrcholu vj do vrcholu vk . Posloupnost hran ej,j1 , ej1 ,j2 , ej2 ,j3 , . . . , ej`−2 ,j`−1 , ej`−1 ,k ∈ E vedouc´ı z vrcholu vj postupnˇe do vj1 , do vj2 , atd. aˇz koneˇcnˇe do vj`−1 a vk se nazýv´ a cesta (pˇr´ıpadnˇe orientovaná cesta) z vrcholu vj do vrcholu vk délky `. ~ Speciálnˇe, Libovolnou podmnoˇzinu mnoˇziny V nazýváme komponenta grafu G. necht’ V = V1 ∪V2 a necht’ pro kaˇzdou hranu ej,k ≡ (vj , vk ) ∈ E plat´ı bud’ vj , vk ∈ V1 , ~ nebo vj , vk ∈ V2 . Pak mnoˇziny V1 a V2 nazýváme nezávislé komponenty grafu G. Komponenta W ⊆ V taková, ˇze mezi libovolnými dvˇema vrcholy vj , vk ∈ W existuje cesta procházej´ıc´ı pouze pˇres vrcholy komponenty W , se nazývá silnˇe souvisl´ a komponenta grafu. Pokud W = V , hovoˇr´ıme také o silnˇe souvislém grafu. Pro upˇresnˇen´ı, jsou-li V1 a V2 nezávislé komponenty, pak v mnoˇzinˇe E neexistuje ˇza´dná hrana taková, která by vedla z nˇekterého vrcholu mnoˇziny V1 do kteréhokoliv vrcholu mnoˇziny V2 , ani ˇzádná hrana taková, která by vedla z nˇekterého vrcholu mnoˇziny V2 do kteréhokoliv vrcholu mnoˇziny V1 . Poznamenejme jeˇstˇe, ˇze mezi libovoln´ ymi vrcholy silnˇe souvislé (koneˇcné) komponenty W (budeme pracovat pouze s grafy, které maj´ı koneˇcn´ y poˇcet vrchol˚ u a hran) vˇzdy existuje cesta délky `, kde ` < |W | (pˇriˇcemˇz |M | znaˇc´ı poˇcet prvk˚ u koneˇcné mnoˇziny M ). Pro bliˇzˇs´ı seznámen´ı se s pojmy teorie graf˚ u doporuˇcujeme napˇr. [16] nebo ˇceské uˇcebnice [9], [10], [20], [21], [22], pˇr´ıpadnˇe rozsáhlejˇs´ı text [19]. Speciálnˇe budeme pracovat s tzv. grafem (ˇctvercové) matice, viz následuj´ıc´ı definici. Definice 7 (Graf matice). Necht’ A ∈ Cn×n je obecná ˇctvercová matice. Orientovaný ~ = (V , E ), kde graf G V = {1, 2, 3, . . . , n}

a

(j, k) ∈ E

⇐⇒ aj,k 6= 0,

~ nazveme grafem matice A. Budeme ho znaˇcit G(A). Graf ˇctvercové matice A obsahuje hranu z vrcholu j do vrcholu k tehdy a jen tehdy, kdyˇz je prvek aj,k nenulov´ y. Poznamenejme, ˇze graf matice lze zavést i jin´ ym zp˚ usobem. Pro podrobnˇejˇs´ı v´ yklad odkazujeme na [12] nebo [8, kapitola II.], popˇr´ıpadˇe na obsáhlejˇs´ı cizojazyˇcné uˇcebnice [6], [7].

20

1.4

Co je to PageRank?

V této ˇcásti se bl´ıˇze seznám´ıme s pojmem PageRank, coˇz je nástroj, kter´ y je pouˇz´ıván jako m´ıra d˚ uleˇzitosti webov´ ych stránek. Definice 8 (PageRank). PageRank webové stránky Pk , znaˇcený r(Pk ) ∈ R, je reálné ˇc´ıslo dané jako souˇcet PageRank˚ u vˇsech stránek Pj , které na stránku Pk odkazuj´ı, dˇelených celkovým poˇctem odkaz˚ u na stránce Pj . Tedy r(Pk ) =

X r(Pj ) , |Pj | P ∈B j

(1.7)

Pk

kde BPk je mnoˇzina vˇsech stránek odkazuj´ıc´ıch na stránku Pk a |Pj | je poˇcet odkaz˚ u na stránce Pj . Autorem tohoto pˇr´ıstupu k hodnocen´ı webov´ ych stránek jsou Larry Page a Sergey Brin, viz [3], [4] a [5]. Z matematického hlediska je takto zavedené mˇeˇr´ıtko d˚ uleˇzitosti stránek, tj. PageRank, tzv. Markovovým ˇretˇezecem (procesem), viz napˇr. [1, kapitola 8], pˇr´ıpadnˇe [23, kapitoly 3–5] ˇci skriptum [18]. Teorie Markovov´ ych ˇretˇezc˚ u nám také dává nástroje, jak se s v´ yˇse uvedenou zacyklenou“ definic´ı vypoˇrádat. ” '$

P1

'$

-

P2

&% &% I @ I @ @@ @ @@ @ '$ @@ @'$ R @

P3

P6

&% &% I @ @@ @@ '$ '$ @@ R @ P4 P5 &%

&%

ˇ adná stránka neObrázek 1.1: Schéma jednoduchého internetu se ˇsesti stránkami. Z´ odkazuje sama na sebe, na kaˇzdou stránku odkazuje alespoˇ n jedna jiná stránka a kaˇzdá stránka obsahuje alespoˇ n jeden odkaz. Nejjednoduˇsˇs´ı bude zaˇc´ıt s mal´ ym pracovn´ım pˇr´ıkladem. V tomto textu budeme vyuˇz´ıvat sluˇzeb malého internetu obsahuj´ıc´ıho pouze ˇsest stránek. Na obrázku 1.1 je pˇr´ıklad takového internetu. Vˇsimnˇeme si, ˇze v naˇsem modelovém internetu: (i) ˇza´dná stránka neodkazuje sama na sebe, (ii) na kaˇzdou webovou stránku odkazuje alespoˇ n jedna jiná stránka a

21

(iii) kaˇzdá stránka obsahuje alespoˇ n jeden odkaz a dokonce (iv) z kaˇzdé stránky je moˇzné dostat se pomoc´ı odkaz˚ u na libovolnou jinou stránku, coˇz uˇz vlastnosti (ii) a (iii) implikuje. ˇ adná z tˇechto situac´ı nen´ı v reálném prostˇred´ı internetu vylouˇcena. Prvn´ı dvˇe Z´ nejsou z hlediska dalˇs´ıho v´ yvoje aˇz tak zaj´ımavé. Tˇret´ı a ˇctvrtou situac´ı se budeme muset pozdˇeji zab´ yvat podrobnˇeji, viz kapitoly 4.1, resp. 4.2. Pokusme se nyn´ı pro stránky tohoto internetu vypoˇc´ıtat jednotlivé PageRanky pomoc´ı vztahu (1.7). Dostaneme tak sadu ˇsesti rovnic r(P1 ) r(P2 ) r(P3 ) r(P4 ) r(P5 ) r(P6 )

= = = = = =

1 1 1 2 1 2

r(P2 ) +

1 3

r(P3 )

r(P1 ) r(P1 )

+ 1 3 1 3 1 3

r(P3 ) r(P3 ) + r(P5 )

+ + 1 1

1 3 1 3

1 2

r(P6 )

r(P5 ) r(P5 )

r(P4 )

kterou m˚ uˇzeme snadno zapsat maticovˇe jako     r(P1 ) 0 1/1 1/3 0 0 0   r(P2 )   1/2 0 0 0 0 1/2       r(P3 )   1/2 0  0 0 1/3 0     =  r(P4 )   0  0 1/3 0 1/3 0      r(P5 )   0 0 1/3 1/1 0 1/2   r(P6 ) 0 0 0 0 1/3 0 {z }| | {z } | π T H

, +

1 2

r(P1 ) r(P2 ) r(P3 ) r(P4 ) r(P5 ) r(P6 ) {z π

    ,   

r(P6 )

(1.8)

}

kde matici H naz´ yváme matic´ı weobových odkaz˚ u tzv. hyperlink˚ u (anglicky hyperlink matrix) a vektor π naz´ yváme PageRank vektor. Vˇsimnˇeme si, ˇze internet na obrázku ~ 1.1 je zároveˇ n grafem G(H) své matice hyperlink˚ u H (aˇz na pojmenován´ı vrchol˚ u; ~ vrchol j v grafu G(H) odpov´ıdá vrcholu Pj v obrázku). Porovnán´ım maticového zápisu (1.8), po zámˇenˇe levé a pravé strany, HT π = π s rovnic´ı (1.1) vid´ıme, ˇze PageRank vektor π mus´ı b´ yt bud’ nulov´ y, coˇz by v daném kontextu nebylo pˇr´ıliˇs pˇr´ınosné, nebo, má-li b´ yt nenulov´ y, mus´ı m´ıt matice hyperlink˚ u H (resp. jej´ı transpozice H T ) vlastn´ı ˇc´ıslo λ = 1. PageRank vektor π je pak vlastn´ım vektorem matice H T odpov´ıdaj´ıc´ı tomuto vlastn´ımu ˇc´ıslu. D˚ uleˇzitou otázkou tedy je, zda má matice hyperlink˚ u vlastn´ı ˇc´ıslo rovné jedné. V matici H si m˚ uˇzeme vˇsimnout následuj´ıc´ı zvláˇstnosti. Souˇcet prvk˚ u v ˇrádc´ıch je vˇzdy roven jedné (kaˇzdá stránka Pj odkazuj´ıc´ı na |Pj | stránek pˇrisp´ıvá k jejich hodnocen´ı stejnou mˇerou rovnou právˇe ˇc´ıslu 1/|Pj |). Kdybychom m´ısto matice H T

22

pracovali pˇr´ımo s matic´ı H, tak urˇcitˇe plat´ı      0 1/2 1/2 0 0 0 1 1  1  1   1  0 0 0 0 0       1/3 0     0 1/3 1/3 0    1  =  1 .  0     0 0 0 1 0    1   1   0 0 1/3 1/3 0 1/3   1   1  0 1/2 0 0 1/2 0 1 1 {z } | {z } | {z } | e e H

(1.9)

Vid´ıme, ˇze vektor e = [1, . . . , 1]T je urˇcitˇe vlastn´ım vektorem matice H odpov´ıdaj´ıc´ım vlastn´ımu ˇc´ıslu λ = 1. Protoˇze det(Iλ − A) = det(Iλ − AT ), viz [11, kapitola 1], pak sp(H) = sp(H T ), a tedy matice H T mus´ı m´ıt také alespoˇ n jedno vlastn´ı ˇc´ıslo rovné jedné, a tud´ıˇz existuje nenulov´ y PageRank vektor π. Poznamenejme, ˇze vlastn´ı vektory matic H a H T odpov´ıdaj´ıc´ı stejnému vlastn´ımu ˇc´ıslu jsou obecnˇe r˚ uzné, tj. e 6= π. To je zp˚ usobeno t´ım, ˇze matice H obecnˇe nen´ı T T normáln´ı, tedy HH 6= H H, viz [11, kapitola 2]. Pouze pro normáln´ı matice plat´ı, ˇze (vˇsechny) jejich levé a pravé vastn´ı vektory jsou stejné; zde je e prav´ ym a π lev´ ym vlastn´ım vektorem matice H.

23

ˇ ast I C´ Existence PageRank vektoru

24

2

Nez´ aporn´ e a stochastick´ e matice

V této kapitole se budeme seznám´ıme se stochastickými maticemi, které jsou specifické právˇe t´ım, ˇze souˇcet prvk˚ u v ˇrádc´ıch je vˇzdy roven jedné. Vycházet budeme z knih [12] a [11]. Zejména zde ukáˇzeme, ˇze pro nˇekteré matice A s nezáporn´ ymi prvky plat´ı, ˇze spektráln´ı polomˇer %(A) je (kladné) vlastn´ı ˇc´ıslo naz´ yvané Perronovo vlastn´ı ˇc´ıslo a ˇze mu odpov´ıdá (ne nutnˇe jedin´ y) vlastn´ı vektor s nezáporn´ ymi prvky naz´ yvan´ y (lev´ y ˇci prav´ y) Perron˚ uv vlastn´ı vektor.

2.1

Aritmetika nez´ aporn´ ych a kladn´ ych matic

Stochastické matice jsou speciáln´ım pˇr´ıpadem tzv. nezáporných matic. Nejprve se tedy seznám´ıme s nimi. Definice 9 (Nezáporná matice, kladná matice). Necht’ A ∈ Rm×n je reálná matice s prvky aj,k . Jestliˇze pro vˇsechny jej´ı prvky plat´ı aj,k ≥ 0, pak tuto matici A nazýváme nezápornou. Tuto vlastnost budeme zapisovat A ≥ 0. Jestliˇze nav´ıc plat´ı aj,k > 0, pak matici A nazýváme kladnou. Tuto vlastnost budeme zapisovat A > 0. Dále je-li B ∈ Rm×n (resp. B ∈ Cm×n ) obecná reálná (resp. komplexn´ı) matice s prvky bj,k , pak zápisem |B| ∈ Rm×n , |B| ≥ 0 budeme znaˇcit nezápornou matici, jej´ıˇz prvky jsou |bj,k |, tj. absolutn´ı hodnoty prvk˚ u matice B. Analogicky zápisem A ≤ 0 a A < 0, budeme znaˇcit, ˇze aj,k ≤ 0, resp. aj,k < 0, a budeme takovou matici A naz´ yvat nekladnou, resp. zápornou. Dále zápisem A ≥ B, kde A a B jsou reálné matice stejn´ ych rozmˇer˚ u, budeme znaˇcit, ˇze A − B ≥ 0, analogicky pro A > B, A ≤ B, A < B. Obdobnˇe zavedeme nerovnosti a znaˇcen´ı také pro vektory. Následuj´ıc´ıch nˇekolik lemmat zformuluje nˇekteré základn´ı vlastnosti aritmetiky nezáporn´ ych matic.

25

Lemma 3. Necht’ A ≥ 0 a B ≥ 0 jsou (reálné) nezáporné matice. Pokud jsou matice A a B stejných rozmˇer˚ u, pak A+B ≥0 je nezáporná. Pokud lze matice A a B násobit (v tomto poˇrad´ı), pak AB ≥ 0

(2.1)

je nezáporná. Je-li nav´ıc A > 0 kladná matice a B 6= 0 nenulová matice, pak AB ≥ 0

AB 6= 0

a zároveˇ n

(2.2)

je nezáporná nenulová matice. D˚ ukaz tohoto lemmatu je elementárn´ı a sestává se pouze z rosepsán´ı maticov´ ych operac´ı po prvc´ıch. Dalˇs´ı lemma, které pro nás bude d˚ uleˇzitˇejˇs´ı, se zamˇeˇr´ı konkrétnˇe na souˇciny nezáporn´ ych matic s vektory. Lemma 4. Necht’ A ∈ Rm×n , A ≥ 0 je nezáporná matice a x, y ∈ Rn vektory, pro které plat´ı x ≥ y. Pak Ax ≥ Ay. (2.3) Je-li nav´ıc A > 0 kladná matice a vektory x 6= y jsou r˚ uzné, pak Ax > Ay.

(2.4)

D˚ ukaz. Nerovnost (2.3) dostaneme snadno z nerovnosti (2.1), pokud budeme v lemmatu 3 uvaˇzovat matici B ve tvaru B ≡ x − y ∈ Rn×1 . Druhou nerovnost (2.4) dokáˇzeme následnˇe. Mˇejme vektory x = [ξ1 , . . . , ξn ]T a y = [ν1 , . . . , νn ]T . Podle nerovnosti x ≥ y plat´ı ξk ≥ νk ,

k = 1, . . . , n.

Protoˇze x 6= y, pak existuje index ` takov´ y, ˇze ξ` > ν` , a bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokládat, ˇze ξk = νk ,

k = 1, . . . , ` − 1, ` + 1, . . . , n.

Pro j-t´ y ˇra´dek souˇcin˚ u Ax a Ay zˇrejmˇe plat´ı ! n X eTj (Ax) = aj,k ξk + aj` ξ` ,

resp.

k=1 k6=`

eTj (Ay) =

n X k=1 k6=`

! aj,k νk

+ aj` ν` =

n X

! aj,k ξk

+ aj` ν` .

k=1 k6=`

26

Protoˇze A > 0, tj. aj,` > 0, a ξ` > ν` , pak eTj (Ax − Ay) = aj,` (ξ` − ν` ) > 0,

pro j = 1, . . . , n.

Tedy Ax − Ay > 0, z ˇcehoˇz ihned plyne Ax > Ay, coˇz jsme chtˇeli dokázat. Vu ´vodn´ım pˇr´ıkladu (1.8)–(1.9) jsme pracovali s nezápornou matic´ı H (resp. H T ), která byla nav´ıc ˇctvercová. Následuj´ıc´ı vˇeta bude uˇziteˇcná pˇri zkoumán´ı ˇctvercov´ ych nezáporn´ ych matic, viz [11, cviˇcen´ı 2.15]. Vˇ eta 2. Necht’ A ∈ Rn×n , A ≥ 0 je nezáporná ˇctvercová matice, x ∈ Rn , x ≥ 0 je nezáporný vektor a ς reálné ˇc´ıslo takové, ˇze Ax > x ς. Pak plat´ı %(A) > ς,

(2.5)

kde %(A) je spektráln´ı polomˇer matice A (viz definice 1). D˚ ukaz. Vzhledem tomu, ˇze A, x a %(A) jsou nezáporná matice, vektor a ˇc´ıslo, viz (1.2), nerovnosti Ax > x ς a %(A) > ς jsou splnˇeny triválnˇe pro ς < 0. Necht’ je tedy ς ≥ 0 (a tud´ıˇz také A 6= 0, x 6= 0). Z pˇredpokladu Ax > x ς vypl´ yvá, ˇze existuje ε > 0 takové, ˇze plat´ı Ax ≥ x(ς + ε). Zadefinujme si nyn´ı matici B ≡ (ς + ε)−1 A. Tato matice je zˇrejmˇe nezáporná, tj. B ≥ 0, B 6= 0, a nav´ıc plat´ı Bx ≥ x. Opakovan´ ym uˇzit´ım tvrzen´ı lemmatu 4, konkrétnˇe vztahu (2.3), pak dostaneme B ` x ≥ B `−1 x ≥ . . . ≥ x,

pro ` = 1, 2, . . .

(2.6)

V´ıme, ˇze plat´ı lim B ` = 0

` −→ ∞

⇐⇒

%(B) < 1,

viz [11, cviˇcen´ı 1.23]. Ze vztahu (2.6) vˇsak vid´ıme, ˇze posloupnost matic B ` nem˚ uˇze konvergovat k nulové matici, a tud´ıˇz mus´ı m´ıt matice B spektráln´ı polomˇer vˇetˇs´ı nebo roven jedné, %(B) ≥ 1, Pro matici A = (ς + ε)B pak ihned dostaneme %(A) ≥ ς + ε > ς, ˇc´ımˇz je d˚ ukaz hotov.

27

Na závˇer jeˇstˇe struˇcnˇe pˇripomeneme vlastnosti aritmetiky komplexn´ıch ˇc´ısel, resp. jejich absolutn´ıch hodnot. Lemma 5. Necht’ A ∈ Cm×n a B ∈ Cn×d jsou dvˇe libovolné komplexn´ı matice, pak |A| |B| ≥ |AB|.

(2.7)

D˚ ukaz. Zˇrejmˇe pro a, b ∈ C plat´ı |a| |b| = |ab|, |a| + |b| ≥ |a + b|. Speciálnˇe pro prvky aj,k a bk,` matice A, resp. B plat´ı n n n X X X |aj,k | |bk,` | = |aj,k bk,` | ≥ aj,k bk,` k=1

k=1

k=1

pro j = 1, . . . , m a ` = 1, . . . , d. Toto triviáln´ı pozorován´ı má následuj´ıc´ı d˚ usledek, kter´ y bude pozdˇeji uˇziteˇcn´ y. Lemma 6. Necht’ A ∈ Rm×n je nezáporná matice, A ≥ 0, a B ∈ Cn×d je libovoln´ a komplexn´ı matice taková, ˇze souˇcin AB ∈ Rm×d je reálný. Pak A|B| ≥ AB.

(2.8)

Je-li nav´ıc matice A kladná, A > 0, pak A|B| = AB

⇐⇒

|B| = B,

(2.9)

tj. v nerovnosti (2.8) nastane rovnost jen tehdy, kdyˇz B je reálná a nezáporná. D˚ ukaz. Je-li A ≥ 0 nezáporná a AB reálná, pak |A| = A, resp. |AB| ≥ AB, a nerovnost (2.8) dostáváme rovnou z nerovnosti (2.7). V druhé ˇca´sti lemmatu je implikace ⇐=“ zˇrejmá. Kdyˇz |B| = B, pak A|B| = AB. Zb´ yvá tedy dokázat implikaci =⇒“ ” ” opaˇcn´ ym smˇerem. Pˇredpokládejme naopak, ˇze druhá implikace neplat´ı, tj. ˇze A|B| = AB

a zároveˇ n

Pˇreuspoˇra´dán´ım prvn´ı rovnosti dostaneme A |B| − B = AM = 0,

kde

|B| = 6 B.

M ≡ |B| − B.

Protoˇze |B| 6= B, pak matice M má alespoˇ n jeden nenulov´ y prvek. Protoˇze A > 0 je kladná, pak AM 6= 0, coˇz je spor. T´ım je dokázána i druhá implikace, a t´ım i celé lemma.

28

2.2

Stochastick´ e matice: spektr´ aln´ı polomˇ er

D˚ uleˇzitou podmnoˇzinou nezáporn´ ych matic jsou tzv. stochastické matice. Tyto matice jsou ned´ılnou souˇca´st´ı v´ ypoˇctu PageRanku, a proto si v této kapitole stochastické matice zadefinujeme a bl´ıˇze pop´ıˇseme jejich vlastnosti. ˇ Definice 10 (Stochastická matice). Ctvercov´ a nezáporná matice S ∈ Rn×n s prvky sj,k , pro kterou plat´ı n X

sj,k = 1,

pro j = 1, . . . , n,

k=1

se nazývá stochastická matice (viz napˇr. [12, str. 99]). Prvky stochastické matice m˚ uˇzeme povaˇzovat napˇr´ıklad za pravdˇepodobnosti. Vˇsimnˇeme si, ˇze v matici hyperlink˚ u H to m˚ uˇzeme interpretovat jako pravdˇepodobnosti pˇrechodu ze stránky Pj na Pk . Jak definice tvrd´ı, stochastická matice S má souˇcet vˇsech prvk˚ u v ˇrádku vˇzdy roven jedné. To lze vyjádˇrit také jako Se = e, kde T e = [1, . . . , 1] . Tedy e je (prav´ y) vlastn´ı vektor stochastické matice S a odpov´ıdá vlastn´ımu ˇc´ıslu λ = 1, viz také (1.9). Vid´ıme, ˇze u ´loha (1.8), kterou chceme ˇreˇsit je následuj´ıc´ı: Hledáme lev´ y vlastn´ı vektor π stochastické matice S odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = 1. Tento vektor je (lev´ y) Perron˚ uv vlastn´ı vektor. To, co bychom nyn´ı rádi ukázali, je, zda lze Perron˚ uv vlastn´ı vektor volit kladn´ y (tj. abychom mohli stránky pomoc´ı komponenty PageRank vektor rozumnˇe seˇradit) a zda je urˇcen jednoznaˇcnˇe. Nyn´ı ukáˇzeme, ˇze pro libovolnou stochastickou matici S dokonce plat´ı %(S) = 1, tj. matice S nemá ˇza´dné vlastn´ı ˇc´ıslo, které by bylo v absolutn´ı hodnotˇe vˇetˇs´ı neˇz jedna. Vˇ eta 3. Necht’ S je ˇctvercová nezáporná stochastická matice, sj,k ≥ 0, pro j = 1, . . . , n. Pak plat´ı %(S) = 1. D˚ ukaz. Pro e = [1, . . . , 1]T zˇrejmˇe plat´ı  Pn   a 1,k k=1    .. Se =  = . Pn k=1 an,k

Pn

k=1

sj,k = 1

 1 ..  = e, .  1

tedy λ = 1 je vlastn´ım ˇc´ıslem stochastické matice, takˇze %(S) ≥ 1.

(2.10)

29

Zároveˇ n vid´ıme, ˇze kSk∞ = 1, viz (1.5). Pouˇzijeme-li tvrzen´ı lemmatu 2 na stochastickou matici S a na ∞-normu (1.4), dostaneme %(S) ≤ kSk∞ = 1. (2.11) Z nerovnost´ı (2.10) a (2.11) zˇrejmˇe vypl´ yvá, ˇze %(S) = 1.

2.3

Stochastick´ e matice: (lev´ y) Perron˚ uv vlastn´ı vektor

Nyn´ı jiˇz v´ıme, ˇze %(S) = 1 pro kaˇzdou stochastickou matici, coˇz znamená, ˇze neexistuje ˇza´dné jiné vlastn´ı ˇc´ıslo matice S, které by bylo v absolutn´ı hodnotˇe vˇetˇs´ı neˇz jedna. Pojd’me se nyn´ı pod´ıvat na dalˇs´ı ˇca´st naˇs´ı u ´lohy. Hledáme lev´ y vlastn´ı vektor π, kter´ y bychom rádi volili kladn´ y. Tato podm´ınka je pro nás d˚ uleˇzitá, protoˇze nám umoˇzn´ı rozumnˇe seˇradit webové stránky. V této kapitole se pˇresvˇedˇc´ıme, ˇze tento kladn´ y vektor exiistuje. Nejprve se ovˇsem pˇresvˇedˇc´ıme, ˇze lev´ y vlastn´ı vektor odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = 1 je moˇzné volit nezáporn´ y. Budeme vycházet z [11, cviˇcen´ı 2.16]. P Vˇ eta 4. Necht’ S je ˇctvercová nezáporná stochastická matice, sj,k ≥ 0, nk=1 sj,k = 1 pro j = 1, . . . , n. Necht’ vlastn´ımu ˇc´ıslu λ ≡ %(S) = 1 odpov´ıdá levý vlastn´ı vektor π. Pak lze tento vektor π volit nezáporný, tj. πT S = πT ,

kde

π ≥ 0.

D˚ ukaz. Mˇejme ˇctvercovou nezápornou stochastickou matici S. Z vˇety 3 v´ıme, ˇze %(S) = 1. Oznaˇcme $j sloˇzky levého vlastn´ıho vektoru π, tedy π = [$1 , . . . , $n ]T . Pokud $j ≥ 0, j = 1, . . . , n, pak π je právˇe hledan´ y nezáporn´ y vektor, pro kter´ y plat´ı πT S = πT . Je-li $j ≤ 0, j = 1, . . . , n pak (−π)T je hledan´ y nezáporn´ y vektor, pro kter´ y plat´ı (−π)T S = (−π)T . Pˇredpokládejme nyn´ı, v rozporu s tvrzen´ım vˇety, ˇze prvky vektoru π maj´ı r˚ uzná znaménka. Pokud existuje alespoˇ n jeden prvek s odliˇsn´ ym znaménkem neˇz maj´ı ostatn´ı prvky, pak n n X X |$j |sj,k > $j sj,k = |$k |, pro k = 1, . . . , n. j=1

j=1

Z toho vypl´ yvá, ˇze plat´ı |π|T S > |π|T ,

kde

h iT |π| ≡ |$1 |, . . . , |$n | .

30

Podle vˇety 2 pro nezápornou matici A ≡ S T , nezáporn´ y vektor x ≡ |π| a reálné ˇc´ıslo T ς ≡ 1 takové, ˇze S |π| ≡ Ax > xλ ≡ |π|, plat´ı %(A) > ς. Takˇze v naˇsem pˇr´ıpadˇe mus´ı b´ yt %(S T ) ≡ %(S) > 1, coˇz je ve sporu s vlastnost´ı %(S) = 1, viz vˇetu 3. T´ım jsme dokázali, ˇze lev´ y vlastn´ı vektor π m˚ uˇzeme volit nezáporn´ y. Z kapitoly 2.2 v´ıme, ˇze spektráln´ı polomˇer ˇcvercové nezáporné stochastické matice je roven jedné. Nav´ıc v´ıme, ˇze spektráln´ı polomˇer je pˇr´ımo vlastn´ım ˇc´ıslem, tj. λ = 1. Nyn´ı jsme zjistili, ˇze lev´ y vlastn´ı vektor odpov´ıdaj´ıc´ı tomuto vlastn´ımu ˇc´ısle lze volit nezáporn´ y. To má následuj´ıc´ı d˚ usledek pro naˇsi u ´lohu. PageRank vektor π splˇ nuj´ıc´ı π T H = π T , viz (1.7) a (1.8), kde H je matice hyperlink˚ u, existuje a jeho sloˇzky, tj. ranky (hodnocen´ı) jednotliv´ ych stránek Pj , jsou nezáporná ˇc´ısla. M˚ uˇzeme je tedy snadno seˇradit.

2.4

Kladn´ e matice: spektr´ aln´ı polomˇ er a (prav´ y) Perron˚ uv vlastn´ı vektor

Vˇetu 4 lze modifikovat pro libovolnou kladnou ˇctvercovou matici, tj. A > 0. Tato modifikace mˇen´ı pˇredpoklady vˇety. Na jedné stranˇe své poˇzadavky zes´ıl´ıme t´ım, ˇze vyˇzadujeme nenulovost prvk˚ u, na druhé stranˇe je ale oslab´ıme t´ım, ˇze nepoˇzadujeme stochasticitu matice. Tvrzen´ı modifikované vˇety je také nepatrnˇe silnˇejˇs´ı. Tato modifikace je známá jako Perronova vˇeta, pˇr´ıpadnˇe Perronovo lemma. Tato vˇeta se bude také hodit v následuj´ıc´ım textu. Budeme vycházet z v´ ykladu v knize [12, str. 86–87]. Vˇ eta 5 (Perronova vˇeta (o spektráln´ım polomˇeru a kladném vlastn´ım vektoru kladn´ ych matic)). Necht’ A je ˇctvercová matice s kladnými prvky, tj. aj,k > 0. Pak λ ≡ %(A) je kladné vlastn´ı ˇc´ıslo matice A a odpov´ıdaj´ıc´ı vlastn´ı vektor x lze volit kladný, tj. Ax = xλ, kde x > 0. D˚ ukaz. Mˇejme A > 0 a vlastn´ı ˇc´ıslo λ matice A, pro které plat´ı %(A) = |λ|.

(2.12)

Mˇejme nenulov´ y vlastn´ı vektor x 6= 0 odpov´ıdaj´ıc´ı ˇc´ıslu λ, tj. Ax = xλ.

(2.13)

Poznamenejme, ˇze pro libovovolná komplexn´ı ˇc´ısla v a w a kladná ˇc´ısla α a β plat´ı α|v| + β|w| ≥ |αv + βw|,

(2.14)

31

pˇriˇcemˇz rovnost nastane právˇe tehdy, kdyˇz existuje komplexn´ı jednotka η (|η| = 1, tj. η = exp(i ϕ) = cos(ϕ) + i sin(ϕ)) tak, ˇze vη, wη ∈ R a nav´ıc vη, wη ≥ 0. Jednoduch´ ym zobecnˇen´ım tohoto pozorován´ı dostaneme, ˇze pro komplexn´ı ˇc´ısla ξ1 , . . . , ξn a kladná ˇc´ısla α1 , . . . , αn plat´ı n n X X αj ξj ; (2.15) αj |ξj | ≥ j=1

j=1

viz také (2.7). Rovnost pˇri tom nastane pouze tehdy, kdyˇz existuje komplexn´ı jednotka η taková, ˇze ξj η ∈ R a nav´ıc ξj η ≥ 0,

pro j = 1, . . . , n.

(2.16)

Pˇredpokládejme nyn´ı, ˇze pro vektor x = [ξ1 , . . . , ξk ]T , respektive pro jeho sloˇzky ξj , neexistuje takové η, aby vztah (2.16) platil. Pak z k-tého ˇra´dku rovnice (2.13) dostaneme uˇzit´ım vztahu (2.15) nerovnost n n X X ak,j ξj = |λ||ξk |, pro k = 1, . . . , n. ak,j |ξj | > j=1

j=1

Z toho vypl´ yvá, ˇze plat´ı A|x| > |x||λ|,

kde

h iT |x| ≡ |ξ1 |, . . . , |ξn | .

Podle vˇety 2 pro nezápornou matici A, nezáporn´ y vektor |x| a reálné ˇc´ıslo |λ| takové, ˇze A|x| > |x||λ|, plat´ı %(A) > |λ|. Tedy v naˇsem pˇr´ıpadˇe mus´ı b´ yt %(A) > |λ|, coˇz je ve sporu s vlastnost´ı z (2.12). T´ım jsme dokázali, ˇze existuje taková komplexn´ı jednotka η, ˇze vztah (2.16) pro sloˇzky vektoru x plat´ı. Takˇze x e = xη ∈ R,

kde x e ≡ [ξe1 , . . . , ξen ],

tj. ξej = ξj η,

a plat´ı x e ≥ 0,

x e 6= 0.

Nav´ıc podle (2.13) plat´ı Ae x=x eλ,

(2.17)

tedy vlastn´ı vektor odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ lze volit nezáporn´ y. Nyn´ı zb´ yvá dokázat, ˇze λ > 0, tj. spektráln´ı polomˇer %(A) = |λ| = λ je pˇr´ımo vlastn´ım ˇc´ıslem, a dále, ˇze x e > 0. Protoˇze A > 0, x e ≥ 0, x e 6= 0, pak podle lemmatu 4 plat´ı Ae x > A · 0, viz (2.4). e Protoˇze x e 6= 0, urˇcitˇe existuje index ` takov´ y, ˇze ξ` > 0. Z `-tého ˇrádku rovnice (2.17), tj. ze vztahu eT` Ae x = λξe` , kde (eT` Ae x) > 0, pak plyne λ > 0. Tud´ıˇz %(A) = |λ| = λ,

32

ˇc´ımˇz jsme dokázali, ˇze spektráln´ı polomˇer matice A s kladn´ ymi prvky je pˇr´ımo jej´ım vlastn´ım ˇc´ıslem. Koneˇcnˇe z k-tého ˇrádku rovnice (2.17), tj. ze vztahu eTk Ae x = λξek , kde (eTk Ae x) > 0 a λ > 0, plyne ξek > 0, pro k = 1, . . . , n. (2.18) T´ım jsme dokázali, ˇze vlastn´ı vektor matice A s kladn´ ymi prvky odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu %(A) vˇzdy m˚ uˇzeme volit kladn´ y.

33

3

Nerozloˇ zitelnost matic

V pˇredchoz´ı kapitole jsme ukázali, ˇze spektráln´ı polomˇer stochastické (pˇr´ıpadnˇe kladné) matice je pˇr´ımo vlastn´ım ˇc´ıslem této matice a ukázali jsme, ˇze vlastn´ı vektor, kter´ y tomuto vlastn´ımu ˇc´ıslu odpov´ıdá je nezáporn´ y (pˇr´ıpadnˇe kladn´ y). Pˇrirozenˇe nás m˚ uˇze dále zaj´ımat, zda je nezáporn´ y (pˇr´ıpadnˇe kladn´ y) vlastn´ı vektor z vˇety 4 (resp. 5) urˇcen jednoznaˇcnˇe.

3.1

Stochastick´ e matice: jednoznaˇ cnost (lev´ eho) Perronova vlastn´ıho vektoru

Perron˚ uv vektor stochastické matice S, tj. lev´ y vlastn´ı vektor π, π ≥ 0 odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = %(S) = 1 obecnˇe nen´ı obecnˇe urˇcen jednoznaˇcnˇe. Pokus´ıme se to ilustrovat na nˇekolika pˇr´ıkladech. Uvaˇzujme nejjednoduˇsˇs´ı ˇctvercovou nezápornou stochastickou matici   1 0 ··· 0  0 1 ··· 0    n×n S ≡ I =  .. ..  ∈ R . . .  . . .  0 0 ··· 1 Zˇrejmˇe %(S) = 1 a λ = 1 je n-násobné vlastn´ı ˇc´ıslo matice S. Pro jakýkoliv nezáporn´ y (pˇr´ıpadnˇe kladn´ y) vektor π, resp. x, plat´ı πT S = πT ,

resp. Sx = x.

´ Uloha tedy obecnˇe nen´ı jednoznaˇcná (a to ani v pˇr´ıpadˇe, ˇze budeme pracovat s normalizovan´ ym vektorem, tj. kdyˇz kπk = kxk = 1). Vezmˇeme si nyn´ı ménˇe triviáln´ı pˇr´ıpad. Mˇejme ˇctvercovou nezáporou stochastickou matici S v blokovˇe diagonáln´ım tvaru se ˇctvercov´ ymi bloky S1 a S2 na diagonále, S1 0 S= . 0 S2 Zˇrejmˇe je matice S nezáporná stochastická matice tehdy a jen tehdy kdyˇz matice S1 a S2 jsou nezáporné stochastické matice. Oznaˇcme π1 a π2 lev´ ymi nezáporn´ ymi vlastn´ımi vektory matic S1 a S2 odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = %(S1 ) = %(S2 ) = 1, tj. π1T S1 = π1T , π1 ≥ 0, π1 6= 0, 34

π2T S2 = π2T ,

π2 ≥ 0, π2 6= 0.

Pak %(S) = 1 a λ = 1 je minimálnˇe dvojnásobné vlastn´ı ˇc´ıslo. Lev´ y vlastn´ı vektor matice S odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = 1, tj. π T S = π T , lze volit napˇr´ıklad následuj´ıc´ımi zp˚ usoby π1 0 π1 π1 α 1 π= , , , pˇr´ıpadnˇe obecnˇe π = , 0 π2 π2 π2 α 2 kde α1 , α2 ∈ R, α1 , α2 ≥ 0, α1 + α2 > 0. Ve vˇsech tˇechto pˇr´ıpadech π ≥ 0, π 6= 0. Je tedy zˇrejmé, ˇze ani nyn´ı lev´ y vlastn´ı vektor π matice S nen´ı dán jednoznaˇcnˇe. V´ yˇse zm´ınˇenou blokovou strukturu budeme ilustorvat na pˇr´ıkladu naˇseho modelového internetu, viz obrázek 1.1, resp. rovnici (1.8). Pˇr´ıklad internetu s takovou blokou strukturou z´ıskáme vynechán´ım nˇekolika odkaz˚ u (hran v grafu), viz obrázek 3.1. Internetu z obrázku 3.1 pak odpov´ıdá rovnice      0 0 0 1/1 1/1 0 r(P1 ) r(P1 )    r(P2 )   1/2 0 0 0 0 0    r(P2 )        r(P3 )   1/2 0 0 0 0   r(P3 )  0   = (3.1)   r(P4 ) ,  r(P4 )   0 0 0 0 1/2 0       r(P5 )   0 0 0 1/1 0 1/1   r(P5 )  r(P6 ) r(P6 ) 0 1/2 0 0 0 0 | {z } | {z } | {z } π π HT vˇsimnˇeme si, ˇze tato matice H má právˇe dvˇe vlastn´ı ˇc´ısla rovna jedné.

3.2

(Ne)rozloˇ ziteln´ e matice

Pˇri zjednoznaˇcnˇen´ı u ´lohy bude hrát d˚ uleˇzitou roli tzv. nerozloˇzitelnost matic. Zaˇcneme proto definic´ı (ne)rozloˇziteln´ ych matic. Vycházet budeme z knihy [12, kapitola 3, str. 71]. Definice 11 ((Ne)rozloˇzitelná matice). Mˇejme ˇctvercovou matici A ∈ Rn×n . Pokud existuje permutace taková, ˇze matice ΠAΠT , kde Π je odpov´ıdaj´ıc´ı permutaˇcn´ı matice, je v blokovˇe (horn´ım) troj´ uheln´ıkovém tvaru s alespoˇ n dvˇema ˇctvercovými bloky na diagonále, tj. A1,1 A1,2 T ΠAΠ = , 0 A2,2 pak se matice A nazývá rozloˇzitelná. Matice, která nen´ı rozloˇzitelná, se nazývá nerozloˇzitelná. Neˇz budeme pokraˇcovat ve v´ ykladu, pokus´ıme se pojem rozloˇzitelnosti ilustrovat opˇet na pˇr´ıkladu naˇseho modelového internetu. Pˇr´ıklad internetu s rozloˇzitelnou

35

matic´ı opˇet z´ıskáme vynechán´ım nˇekolika odkaz˚ u (hran v grafu), viz obrázek 3.2. Internetu z obrázku 3.2 pak odpov´ıdá rovnice      0 0 0 1/1 1/2 0 r(P1 ) r(P1 )   r(P2 )   1/2 0  0 0 0 0    r(P2 )       r(P3 )   1/2 0  0 0 0  0   r(P3 )  .  = (3.2)   r(P4 )   0  0 0 0 1/2 0    r(P4 )      r(P5 )   0 0 1/2 1/1 0 1/1   r(P5 )  r(P6 ) r(P6 ) 0 1/2 0 0 0 0 | {z } | {z } | {z } π π HT ~ Pˇripomeˇ nme, ˇze schémata na obrázc´ıch 1.1, 3.1 a 3.2 jsou grafy G(H) matice H z rovnic (1.8), (3.1) a (3.2). Vˇsimnˇeme si, ˇze graf na obrázku 1.1 je silnˇe souvislý (tj. existuje cesta mezi libovoln´ ymi dvˇema vrcholy; viz sekce 1.3) a matice H, která mu odpov´ıdá, je nerozloˇzitelná. Podobnˇe obˇe nezávislé komponenty S1 = {P1 , P2 , P3 } a S2 = {P4 , P5 , P6 } na obrázku 3.1 jsou silnˇe souvislé a jim odpov´ıdaj´ıc´ı bloky na diagonále matice H jsou opˇet nerozloˇzitelné. Toto pozorován´ı se dá snadno zobecnit. Zˇrejmˇe plat´ı následuj´ıc´ı lemma. ~ Lemma 7. Matice A je nerozloˇzitelná tehdy a jen tehdy, kdyˇz je jej´ı graf G(A) silnˇe souvislý. '$

'$

P1

-

P2

&% &% I @ I @ @@ @ @@ @ '$ @@ @'$ R @

%

P3

P6

&% &% I @ @@ @@ '$ '$ @@ R @ P4 P5

%

&%

%%

&%

Obrázek 3.1: Jednoduch´ y model internetu z obrázku 1.1 po vyˇskrtán´ı nˇekter´ ych odkaz˚ u (hran); symbol “ znaˇc´ı vyˇskrtnutou hranu. Vid´ıme, ˇze internet se nyn´ı ” skládá ze dvou nezávisl´ ych ˇca´st´ı (graf obsahuje dvˇe nezávislé komponenty), s´ıt´ı S1 ≡ {P1 , P2 , P3 } a S2 ≡ {P4 , P5 , P6 }. Masov´ y v´ yskyt takové struktury ve skuteˇcném internetu (tj. v´ yskyt dvou nebo v´ıce rozsál´ ych oblast´ı zcela nepropojen´ ych webov´ ymi odkazy) je znaˇcnˇe nepravdˇepodnobn´ y.

%

36

D˚ ukaz. D˚ ukaz je moˇzné provést snadno. Pˇredpokládáme-li rozloˇzitelnost matice, snadno ukáˇzeme, ˇze jsou v grafu takové vrcholy, mezi nimiˇz neexistuje cesta (tedy silná souvislost implikuje nerozloˇzitelnost). Pˇredpokládáme-li naopak, ˇze graf nen´ı silnˇe souvisl´ y, m˚ uˇzeme mnoˇzinu vrchol˚ u rozloˇzit na systém (alespoˇ n dvou) navzájem disjuktn´ıch podmnoˇzin tvoˇr´ıc´ıch silnˇe souvislé komponenty maximáln´ı velikosti. Mezi libovoln´ ymi dvˇema takov´ ymi komponentami bud’ ˇza´dné hrany nevedou, nebo vedou jen jedn´ım smˇerem (pokud by vedli obˇema smˇery, sjednocen´ı pˇr´ısluˇsn´ ych komponent tvoˇr´ı opˇet silnˇe souvislou komponentu, coˇz je ve sporu s maximáln´ı velikost´ı silnˇe souvisl´ ych komponent). Vhodn´ ym seˇrazen´ım tˇechto komponent (tj. vhodn´ ym oˇc´ıslován´ım vrchol˚ u grafu, tj. vhodnou volbou permutaˇcn´ı matice P z definice 11) dostaneme matici v blokovˇe (horn´ım) troj´ uheln´ıkovém tvaru se ˇctvercov´ ymi bloky (odpov´ıdaj´ıc´ımi silnˇe souvisl´ ym komponentám) na diagonále (tedy nerozloˇzitelnost implikuje silnou souvislost). Pro podrobnˇejˇs´ı v´ yklad viz [12, vˇeta 3.6]. Pro dalˇs´ı v´ yklad bude d˚ uleˇzité následuj´ıc´ı lemma a jeho d˚ usledek, viz [12, vˇety 4.4 a 4.5]. Lemma 8. Necht’ A je ˇctvercová nezáporná matice, tj. aj,k ≥ 0, a ` pˇrirozené ˇc´ıslo, potom pro matici B = A` plat´ı, ˇze bj,k > 0 tehdy a jen tehdy, kdyˇz v orientovaném ~ grafu G(A) existuje cesta z vrcholu j do vrcholu k délky `. '$

P1

'$

-

P2

&% &% I @ I @ @@ @ @@ @ '$ @@ @'$ R @

%

P3

P6

&% &% I @ @@ @@ '$ '$ @@ R @ P4 P5

%

&%

%

&%

Obrázek 3.2: Jednoduch´ y model internetu z obrázku 1.1 po vyˇskrtán´ı nˇekter´ ych odkaz˚ u (hran); symbol “ znaˇc´ı vyˇskrtnutou hranu. Na rozd´ıl od internetu z obrázku ” 3.1, tento internet neobsahuje nezávislé komponenty. Vid´ıme ale, ˇze stále ze s´ıtˇe S2 = {P4 , P5 , P6 } nevede ˇza´dn´ y odkaz do s´ıtˇe S1 = {P1 , P2 , P3 } (graf neobsahuje cestu mezi libovoln´ ymi dvˇema vrcholy). Matice hyperlink˚ u odpov´ıdaj´ıc´ı takovému internetu je (stejnˇe jako v pˇr´ıpadˇe obrázku 3.1) rozloˇzitelná; matice hyperlink˚ u odpov´ıdaj´ıc´ı s´ıt´ım S1 a S2 uˇz rozloˇzitelné nejsou (stejnˇe jako matice celého internetu z obrázku 1.1).

%

37

D˚ ukaz. Tvrzen´ı je zˇrejmˇe pravdivé pro ` = 1. Pˇredpokládejme tedy, ˇze tvrzen´ı plat´ı aˇz do `. Z tohoto pˇredpokladu dokáˇzeme, ˇze plat´ı i pro ` + 1. Oznaˇcme B = A` a C = BA = A`+1 . Pak X cj,k = bj,i ai,k . (3.3) i

~ Necht’ existuje v G(A) cesta délky ` + 1 z j do k, tj. (j, p1 ), (p1 , p2 ), (p2 , p3 ), . . . , (p`−1 , p` ), (p` , k). Pak podle indukˇcn´ıho pˇredpokladu plat´ı bj,p` > 0. Zároveˇ n plat´ı ap` ,k > 0. Vˇsechny sˇc´ıtance v 3.3 jsou nezáporné, pˇriˇcemˇz alespoˇ n jeden z nich je kladn´ y, konkrétnˇe y bj,p` ap` ,k > 0. Tedy cj,k > 0. V matici A`+1 se na pozici (j, k) nacház´ı nenulov´ prvek. Pˇredpokládejme nyn´ı obrácenˇe, ˇze je v matici A`+1 na pozic (j, k) nenulov´ y prvek. Potom v souˇctu 3.3 mus´ı b´ yt nˇekter´ y ˇclen kladn´ y. Necht’ napˇr. bj,t at,k > 0. Pak nutnˇe ~ bj,t > 0 a at,k > 0. Podle indukˇcn´ıho pˇredpokladu existuje v grafu G(A) cesta délky ` z j do t. Protoˇze at,k > 0 exituje v grafu hrana vedouc´ı z t do k. Potom také existuje cesta délky ` + 1 z j do k. Protoˇze v grafu nerozloˇzitelné matice A ∈ Cn×n vˇzdy existuje cesta mezi libovoln´ ymi ~ dvˇema vrcholy délky `, ` < n (graf G(A) má právˇe n r˚ uzn´ ych vrchol˚ u; viz sekce 1.3), má pˇredchoz´ı lemma následuj´ıc´ı d˚ uleˇzit´ y d˚ usledek. Lemma 9. Necht’ A je nezáporná nerozloˇzitelná matice, tj. aj,k ≥ 0, a necht’ α0 , α1 , . . . , αn−1 jsou kladná ˇc´ısla, pak matice α0 I + α1 A + α2 A2 + · · · + αn−1 An−1 je kladná. Speciálnˇe plat´ı (I + A)n−1 > 0. Pn−1 p cet nezáporn´ ych matic. Mus´ıme tedy dokázat, ˇze pro liboD˚ ukaz. p=0 αp A je souˇ volná pevná j a k je u nˇekteré mocniny Ap , 0 ≤ p ≤ n − 1, na m´ıstˇe (j, k) kladn´ y prvek. Pokud j = k, pak je to pravda vˇzdy, protoˇze I má na tomto m´ıstˇe kladn´ y prvek. V pˇr´ıpadˇe, ˇze j 6= k, pak z nerozloˇzitelnosti matice plyne (viz lemma 7), ˇze ~ v grafu G(A) existuje cesta z vrcholu j do vrcholu k délky `, kde ` < n. Podle lemmatu 8 má právˇe matice A` kladn´ y prvek na pozici (j, k). Prvn´ı tvrzen´ı je tud´ıˇz dokázáno a druhé trvzen´ı je triviáln´ım d˚ usledkem. Podle binomické vˇety totiˇz plat´ı (A + I)

n−1

kde A0 ≡ I; staˇc´ı proto poloˇzit αp =

n−1 X n−1 p = A, p p=0

(3.4)

n−1 p

.

Nyn´ı budeme pokraˇcovat v anal´ yze jednoznaˇcnosti vlastn´ıho vektoru, kter´ y odpov´ıdá vlastn´ımu ˇc´ıslu rovnému spektráln´ımu polomˇeru.

38

3.3

Kladn´ e matice: jednoznaˇ cnost (prav´ eho) Perronova vlastn´ıho vektoru

Zaˇcneme rozˇs´ıˇren´ım Perronovy vˇety o spektráln´ım polomˇeru a kladném vlastn´ım vektoru kladn´ ych matic, viz vˇetu 5. Vˇ eta 6 (Perronova vˇeta (o jednoznaˇcnosti Perronova vlastn´ıho páru kladn´ ych matic)). Necht’ A je ˇctvercová matice s kladnými prvky, tj. aj,k > 0. Pak vlastn´ı ˇc´ıslo λ = %(A) matice A je jednoduché a odpov´ıdaj´ıc´ı vlatn´ı vektor x, x > 0, Ax = x%(A), je urˇcen jednoznaˇcnˇe. D˚ ukaz. Poznamenejme nejprve, ˇze vlastn´ı ˇc´ıslo splˇ nuj´ıc´ı λ = %(A) podle prvn´ı Perronovy vˇety (viz vˇetu 5) vˇzdy existuje. Pˇredpokládejme nyn´ı, ˇze k vlastn´ımu ˇc´ıslu λ existuj´ı dva lineárnˇe nezávislé vektory x = [ξ1 , . . . , ξn ]T a v = [ν1 , . . . , νn ]T . Protoˇze x 6= 0, tak existuje index ` takov´ y, ˇze ξ` 6= 0. Vektor w = v − x(ξ`−1 ν` ) je netriviáln´ı lineárn´ı kombinac´ı lineárnˇe nezávisl´ ych vektor˚ u, je tedy nenulov´ y, tj. w 6= 0. Zˇrejmˇe je také vlastn´ım vektorem matice A odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ, Aw = Av − Ax(ξ`−1 ν` ) = vλ − x(ξ`−1 ν` )λ = (v − x(ξ`−1 ν` ))λ = wλ. Jeho `-tá sloˇzka je vˇsak nulová, tj. eT` w = ν` − ξ` (ξ`−1 ν` ) = 0. Z prvn´ı Perronovy vˇety (viz vˇetu 5 a jej´ı d˚ ukaz) ovˇsem vypl´ yvá, ˇze je-li w vlastn´ı vektor odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = %(A), pak existuje komplexn´ı jednota η (η = exp(i ϕ)) taková, ˇze w e = wη ≥ 0. Z `-tého ˇrádku rovnice Aw e = wλ, e tj. T T T T (e` A)w e = λ(e` w), e kde (e` A) > 0 a λ > 0, pak dostaneme (e` A)w e > 0, tedy také T T T λ(e` w) e > 0, coˇz je ovˇsem ve sporu s e` w e η = e` w = 0. T´ım jsme dokázali, ˇze je-li A > 0, pak vlastn´ımu ˇc´ıslu λ = %(A) odpov´ıdá jedin´ y lineárnˇe nezávisl´ y (prav´ y) vlastn´ı vektor. Protoˇze lev´ y vlastn´ı vektor y matice A odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ = %(A) je prav´ ym vlastn´ım vektorem matice AT a ta je kladná, y je jedin´ ym lineárnˇe nezávisl´ ym lev´ ym vlastn´ım vektorem matice A, kter´ y lze volit kladn´ y y > 0. Necht’ T tedy x > 0, y > 0. Speciálnˇe pak y x 6= 0 a z pomocné Schurovy vˇety (viz vˇetu 1) vypl´ yvá, ˇze λ = %(A) je jednoduché vlastn´ı ˇc´ıslo matice A.

3.4

Nez´ aporn´ e nerozloˇ ziteln´ e matice

Nyn´ı uˇz jsme pˇripraveni vyslovit tzv. Perronovu–Frobeniovu vˇetu o nezáporn´ ych matic´ıch (obˇe pˇredchoz´ı Perronovy vˇety hovoˇrily o matic´ıch kladn´ ych). Vˇ eta 7 (Perronova–Frobeniova vˇeta (o nezáporn´ ych nerozloˇziteln´ ych matic´ıch)). Necht’ A ∈ Rn×n je ˇctvercová nezáporná nerozloˇzitelná matice, tj. aj,k ≥ 0. Pak spektráln´ı polomˇer %(A) je kladné jednoduché vlastn´ı ˇc´ıslo matice A a tomuto vlastn´ımu ˇc´ıslu odpov´ıdá kladný vlastn´ı vektor.

39

D˚ ukaz. Uvaˇzujme ˇctvercovou nezápornou nerozloˇzitelnou matici A ∈ Rn×n . Podle lemmatu 9 je matice (I + A)n−1 kladná; zˇrejmˇe je tedy i jej´ı transpozice, tj. matice ((I + A)n−1 )T = (I + AT )n−1 , kladná. Podle Perronovy vˇety o spektráln´ım polomˇeru kladn´ ych matic (viz vˇetu 5) existuje kladn´ y vlastn´ı vektor y > 0 tak, ˇze (I + AT )n−1 y = y % (I + AT )n−1 neboli

y T (I + A)n−1 = % (I + A)n−1 y T .

(3.5)

Mˇejme dále vlastn´ı ˇc´ıslo λ matice A takové, ˇze |λ| = %(A). Necht’ x 6= 0 je nˇejak´ y vlastn´ı vektor matice A odpov´ıdaj´ıc´ı tomuto vlastn´ımu ˇc´ıslu, tj. Ax = xλ. Pak plat´ı A|x| = |A||x| ≥ |Ax| = |xλ| = |x||λ|, kde nerovnost z´ıskáme obdobnˇe jako ve vztahu (2.14), pouˇzijeme-li ho na jednotlivé ˇra´dky levé a pravé strany. Tud´ıˇz plat´ı A|x| ≥ |x|%(A). Vynásob´ıme-li pˇredchoz´ı nerovnost matic´ı A zleva, dostaneme A2 |x| = A(A|x|) ≥ A(|x|%(A)) = (A|x|)%(A) ≥ (|x|%(A))%(A) = |x|%2 (A). Obdobnˇe dostaneme obecn´ y vztah Ap |x| ≥ |x|%p (A),

pro p = 1, . . . , n − 1. (3.6) Jestliˇze vynásob´ıme nerovnost ze vztahu (3.6) ˇc´ıslem n−1 (viz (3.4)) a seˇcteme pro p p = 1, . . . , n − 1, dostaneme, spolu s rovnost´ı |x| = I|x|, vztah n−1 (I + A)n−1 |x| ≥ |x| 1 + %(A) . (3.7) Vynásob´ıme-li tuto nerovnost zleva kladn´ ym vektorem y T > 0, dostaneme n−1 y T (I + A)n−1 |x| ≥ (y T |x|) 1 + %(A) , kde levá strana je podle (3.5) rovna %((I + A)(n−1) )(y T |x|). Protoˇze y T |x| je kladné ˇc´ıslo, dostáváme n−1 % (1 + A)n−1 ≥ 1 + %(A) . (3.8) Matice (I + A)n−1 má vlastn´ı ˇc´ısla ve tvaru (1 + λj )n−1 , kde λj jsou vlastn´ı ˇc´ısla matice A. Protoˇze (I + A)n−1 je kladná matice, jej´ı spektráln´ı polomˇer je pˇr´ımo (kladn´ ym) vlastn´ım ˇc´ıslem. To znamená, ˇze existuje vlastn´ı ˇc´ıslo µ matice A tak, ˇze (1 + µ)n−1 = % (I + A)n−1 . (3.9)

40

Kombinac´ı vztah˚ u (3.8)–(3.9) dostaneme n−1 (1 + µ)n−1 ≥ 1 + %(A) , neboli (po odmocnˇen´ı) |1 + µ| ≥ 1 + %(A). Protoˇze plat´ı %(A) ≥ |µ|, pak 1 + %(A) ≥ 1 + |µ| ≥ |1 + µ| ≥ 1 + %(A). Vid´ıme, ˇze levá strana nerovnosti je shodná s pravou, a proto i ve vˇsech mezilehl´ ych nerovnostech mus´ı nastat rovnost. Speciálnˇe odtud plyne, ˇze %(A) = µ,

µ ≥ 0.

Rovnost také plat´ı v nerovnosti (3.8), v nerovnosti (3.7) a ve vˇsech nerovnostech v (3.6). Zde speciálnˇe pro k = 1 dostáváme A|x| = |x|%(A),

neboli

A|x| = |x|µ.

Specálnˇe také z (3.7) a (3.9) plat´ı (I + A)n−1 |x| = |x|(1 + µ)n−1 = |x|% (I + A)n−1 .

(3.10)

Podle Perronovy vˇety (viz vˇetu 5) je |x| ve vztahu (3.10) kladn´ y, tj. |x| > 0. Z vˇety 6 pak plyne, ˇze k µ existuje jedin´ y lineárnˇe nezávisl´ y vlastn´ı vektor. Nav´ıc je %(A) > 0, protoˇze A je nerozloˇzitelná, a tedy nenulová matice. Protoˇze lev´ y vlastn´ı vektor y matice A je prav´ ym vlastn´ım vektorem matice AT a ta je nezáporná nerozloˇzitelná, je y jedin´ ym lineárnˇe nezávisl´ ym lev´ ym vlastn´ım vektorem matice A a lze volit kladn´ y. Speciálnˇe y T x 6= 0, tedy ze Schurovy pomocné vˇety (viz vˇetu 1) vypl´ yvá, ˇze %(A) je jednoduché vlastn´ı ˇc´ıslo matice A. Pˇredchoz´ı vˇeta má následuj´ıc´ı d˚ uleˇzit´ y d˚ usledek. Vid´ıme, ˇze bude-li (ˇctvercová a nezáporná) matice hyperlink˚ u H nejen stochastická, ale také nerozloˇzitelná, tj. bude-li moˇzné dostat se z kaˇzdé stránky Pj na libovolnou stránku Pk , pak bude (kladn´ y) PageRank vektor π urˇcen jednoznaˇcnˇe. Vˇsimnˇeme si, ˇze tyto vlastnosti (stochasticitu a nerozloˇzitelnost) má právˇe náˇs modelov´ y intenet z obrázku 1.1. Jeho (kladn´ y) PageRank vektor bude urˇcen jednoznaˇcnˇe. Vztahy mezi jednotliv´ ymi druhy matic jsou schématicky znázornˇeny na obrázku 6.3 na str. 62.

41

4

Matice hyperlink˚ u obecnˇ e nen´ı stochastick´ a ani nerozloˇ ziteln´ a. Co s t´ım?

Aˇckoliv naˇsemu modelovému internetu z obrázku 1.1 odpov´ıdá matice hyperlink˚ u, která je stochastická a nerozloˇzitelná, obecnˇe to tak b´ yt nemus´ı. Tento deficit souvis´ı s vlastnostmi (i)–(iv), které jsme zm´ınili na str. 21–22. Stochasticita je d˚ uleˇzitá z hlediska vlastnosti (iii) a nerozloˇzitelnost poˇzadujeme pro vlastnost (iv).

4.1

Matice hyperlink˚ u je obecnˇ e substochastick´ a.

Jiˇz jsme zjistili, ˇze stochasticita souvis´ı s vlastnost´ı (iii), tj. kaˇzdá stránka mus´ı obsahovat alespoˇ n jeden odkaz na jinou stránku. Pod´ıvejme se na internet, kter´ y tuto vlastnost nesplˇ nuje, viz obrázek 4.1. Internetu z tohoto obrázku odpov´ıdá matice H, která má nulov´ y ˇra´dek, tud´ıˇz souˇcet prvk˚ u v ˇra´dku nen´ı vˇzdy roven jedné, pˇresnˇeji '$

P1

'$

-

P2

&% &% I @ I @ @@ @ @@ @ '$ @@ @'$ R @

P3

P6

&% &% I @ @@ @@ '$ '$ @@ R @ P4 P5 &%

%

&%

Obrázek 4.1: Jednoduch´ y model internetu z obrázku 1.1 po vyˇskrtán´ı nˇekter´ ych od“ znaˇc´ı vyˇskrtnutou hranu. Vid´ıme, ˇze nyn´ı nevede ˇza´dn´ y kaz˚ u (hran); symbol ” ˇ odkaz ze stránky P4 . Odpov´ıdaj´ıc´ı matice hyperlink˚ u je substochastická. Rádek matice H, jehoˇz souˇcet nen´ı roven jedné, je zv´ yraznˇen.

%

42

ˇreˇceno, souˇcet prvk˚ u v ˇrádku je v intervalu [0, 1],      0 0 r(P1 ) r(P1 ) 0 1/1 1/3 0   r(P2 )   1/2 0  0 0 1/2  0    r(P2 )      r(P3 )   1/2 0  0 0 1/3 0     r(P3 ) , =   r(P4 )   0  0 1/3 0 1/3 0     r(P4 )      r(P5 )   0  0 1/3 0 0 1/2 r(P5 )  0 1/3 0 0 0 0 r(P6 ) r(P6 ) {z } | {z } | {z } | π π HT

(4.1)

taková matice se naz´ yvá substochastická. Uvˇedomme si, co pˇredstavuje matice hyperlink˚ u H. V podstatˇe ˇr´ıká, ˇze uˇzivatel internetu ze stánky Pj pˇrejde na Pk s pravdˇepodobnost´ı 1/|Pj |, kdyˇz Pj na Pk odkazuje, respektive s pravdˇepodobnost´ı 0, kdyˇz Pj na Pk neodkazuje. To je konzistentn´ı s t´ım, ˇze na ˇrádku jsou samé nuly. Problém nalezen´ı PageRanku postaven´ y pouze na hyperlinkové matici modeluje uˇzivatele, kter´ y náhodnˇe pˇrecház´ı ze stránky na stránku (tzv. random surfer) s pravdˇepodobnost´ı 1/|Pj |, kdyˇz to jde. Celková doba, kterou tento uˇzivatel stráv´ı na jedné konkrétn´ı stránce v pr˚ ubˇehu delˇs´ıho ˇcasového u ´seku, je meˇr´ıtkem relativn´ı d˚ uleˇzitosti této stránky. Jestliˇze na jedné konkrétn´ı stránce stráv´ı celkovˇe v´ıce ˇcasu neˇz na ostatn´ıch, pak je zˇrejmé, ˇze se k této stránce vrac´ı pravidelnˇe. Tato stránka (a také vˇsechny dalˇs´ı, na které se uˇzivatel vrac´ı pravidelnˇe) mus´ı b´ yt d˚ uleˇzitá a mus´ı na n´ı b´ yt odkazováno dalˇs´ımi jin´ ymi d˚ uleˇzit´ ymi stránkami. Bohuˇzel uˇzivatel, kter´ y náhodnˇe procház´ı internet, také obˇcas naraz´ı na stránky, které jiˇz neodkazuj´ı dále. Bˇeˇzn´ ym pˇr´ıkladem jsou pdf soubory nebo obrázky. To jsou vrcholy grafu (tzv. dangling node), do kter´ ych vede hrana, ale nevede uˇz z nich. Zakladatelé PageRanku tento problém vyˇreˇsili následovnˇe. Vˇsechny nulové ˇra´dky matice hyperlink˚ u H nahradili ˇra´dkem eT /n, kde e = [1, . . . , 1]T ∈ R a n je poˇcet stránek celého internetu. PageRank vektor π je pak lev´ ym vlastn´ım vektorem novˇe vzniklé matice 1 e ≡ H + D, H kde D ≡ deT , n která uˇz je stochastická. Vektor d (anglicky naz´ yvan´ y dangling node vector) nab´ yvá hodnot jedna nebo nula, konkrétnˇe dj = 1, jestliˇze j-tá stránka je právˇe t´ım vrcholem, z nˇehoˇz nevede hrana ven. V ostatn´ıch pˇr´ıpadech je dj = 0. Spektráln´ı polomˇer e = 1 a vlastn´ı vektor π je nezáporn´ %(H) y, tj. π ≥ 0. V tuto chv´ıli uˇz je splnˇena vlastnost (iii), tzn. uˇzivatel m˚ uˇze, i po tom co se dostane do vrcholu, ze kterého nevede e stochastická, ˇc´ımˇz hrana ven, pˇrecházet mezi stránkami nahodile. Nyn´ı je matice H jsme vyˇreˇsili problém vrchol˚ u bez zpˇetn´ ych hran (dangling node). Ovˇsem nemus´ı b´ yt jeˇstˇe nerozloˇzitelná.

4.2

Stochastick´ a matice hyperlink˚ u je obecnˇ e rozloˇ ziteln´ a.

Nerozloˇzitelnost je ekvivalentn´ı s vlastnost´ı (iv), tj. s poˇzadavkem, aby bylo moˇzné dostat se z kaˇzdé stránky pomoc´ı odkaz˚ u na libovolnou jinou stránku. To ovˇsem

43

obecnˇe neplat´ı, viz napˇr. intenet na obrázc´ıch 3.1 a 3.2, resp. odpv´ıdaj´ıc´ı matice hyperlink˚ u (3.1) a (3.2). V závˇeru pˇredchoz´ı sekce model pˇrisoudil uˇzivateli schopnost pˇrej´ıt kamkoliv, a to dokonce z tzv. dangling node. Proˇc by tedy uˇzivatel nemohl pˇrej´ıt kamkoliv odkudkoliv? Samozˇrejmˇe to lze. Pˇredstavme si uˇzivatele, kter´ y nejen pˇrecház´ı mezi stránkami pomoc´ı odkaz˚ u, ale obˇcas také nap´ıˇse pˇr´ımo adresu webové stránky. Pokud toto uˇzivatel udˇelá, pak se tzv. teleportuje pˇr´ımo na poˇzadovanou stránku bez pouˇzit´ı odkaz˚ u, odkud pokraˇcuje v nahodilém pˇrecházen´ı mezi stránkami pomoc´ı odkaz˚ u aˇz do té doby, neˇz se opˇet teleportuje jinam. Tuto teleportaci, tj. schopnost uˇzivatele pˇrecházet odkudkoliv kamkoliv, vyˇreˇsili Page a Brin matemae opˇet upravili a z´ıskali tzv. googlovskou matici ticky tak, ˇze stochastickou matici H e + (1 − α)E, G ≡ αH

E≡

kde

1 T ee n

je tzv. teleportaˇcn´ı matice a 0 < α < 1. ˇ ıslo α zde udává pomˇer mezi ˇcasem, kter´ C´ y bˇeˇzn´ y uˇzivatel stráv´ı pˇrecházen´ım mezi stránkami pomoc´ı odkaz˚ u, a ˇcasem, kter´ y vˇenuje teleportaci. Bude-li α = 0, 8, pak 80 % ˇcasu uˇzivatel pˇrecház´ı náhodnˇe mezi stránkami pomoc´ı odkaz˚ u a 20 % ˇcasu uˇzivatel tráv´ı pˇrechodem pˇr´ımo na nové stránky zadán´ım jejich webové adresy. Teleportace je náhodná, protoˇze uˇzivatel m˚ uˇze kdykoliv pˇrej´ıt náhodnˇe na kteroukoliv jinou stránku tak, ˇze nap´ıˇse jej´ı webovou adresu. Googlovská matice G je konvexn´ı e a teleportaˇcn´ı kombinac´ı dvou stochastick´ ych matic, opravené matice hyperlink˚ uH matice E, která je nav´ıc kladná, e = H + 1 deT , H n

E=

1 T ee . n

Protoˇze α < 1, pak (1 − α) > 0, a tedy googlovská matice G je urˇcitˇe kladná, G ≥ 0. Podle následuj´ıc´ıho lemmatu je googlovská matice nav´ıc stochastická. Lemma 10. Necht’ S1 a S2 jsou stochastické matice a α ∈ [0, 1]. Pak konvexn´ı kombinac´ı tˇechto dvou stochastických matic vznikne stochastická matice S, tj. S = αS1 + (1 − α)S2 . D˚ ukaz. D˚ ukaz je elementárn´ı. Staˇc´ı si uvˇedomit, ˇze v j-tém ˇra´dku matice S je souˇcet j-tého ˇrádku matice S1 (kter´ y je roven jedné) vynásoben´ y α a j-tého ˇra´dku matice S2 (kter´ y je také roven jedné) vynásoben´ y (1 − α). T´ım jsme se dostali k nejd˚ uleˇzitˇejˇs´ımu pozorován´ı.

44

Googlovská matice 1 1 G = α H + deT + (1 − α) eeT , n n

0<α<1

je stochastická a nerozloˇzitelná (pˇresnˇeji ˇreˇceno kladná, vˇsechny jej´ı prvky jsou nenulové), takˇze jsou splnˇeny vlastnosti (iii) a (iv), viz stranu 22. Tud´ıˇz je moˇzné dostat se z kaˇzdé stránky pomoc´ı odkaz˚ u nebo teleportac´ı na libovolnou jinou stránku, tj. kladný PageRank vektor pro googlovskou matici existuje a je jednoznaˇcný. Pro vyjasnˇen´ı vztah˚ u mezi jednotliv´ ymi druhy matic viz schéma na obrázku 6.3 na str. 62.

45

ˇ ast II C´ Výpoˇcet PageRank vektoru

46

5

Mocninn´ a metoda

Kdyˇz uˇz v´ıme, ˇze PageRank vektor existuje a je jednoznaˇcn´ y, rádi bychom ho umˇeli spoˇc´ıtat. V´ ypoˇcet budeme provádˇet pomoc´ı tzv. mocninné metody (power method). Ta slouˇz´ı k nalezen´ı vlastn´ıho ˇc´ısla matice A, které je v absolutn´ı hodnotˇe nejvˇetˇs´ı (tzv. dominantn´ı vlastn´ı ˇc´ıslo), resp. k nalezen´ı vlastn´ıho vektoru, kter´ y mu odpov´ıdá (tj. k nalezen´ı dominantn´ıho vlastn´ıho páru). Nejprve si ukáˇzeme, kdy mocninná metoda funguje a zjist´ıme, ˇze pro hyperlinkovou matici tato metoda obecnˇe platit nemus´ı. Nakonec ovˇsem budeme schopni upravit matici tak, aby se tato metoda dala pouˇz´ıt.

5.1

Diagonalizovateln´ e matice

Pro jednoduchost se v následuj´ıc´ım v´ ykladu omez´ıme jen na tzv. diagonalizovatelné matice, zaˇcneme definic´ı, viz napˇr. [11, kapitola 2]. Definice 12 (Diagonalizovatelná matice). Matice A ∈ Cn×n se nazývá diagonalizovatelná matice, pokud existuje regulárn´ı matice X ∈ Cn×n taková, ˇze D ≡ X −1 AX ∈ Cn×n je diagonáln´ı. Diagonalizovatelná matice je tedy taková ˇctvercová matice, která neobsahuje ˇzádné netriviáln´ı Jordanovy bloky (tj. dimenze 2 × 2 a vˇetˇs´ı), viz [11, kapitoly 1.8, 2.2]. Bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokládat, ˇze sloupce xj matice X jsou normalizované, tedy X = [x1 , . . . , xn ] ∈ Cn×n

kde

kxj k = 1,

j = 1, . . . , n.

Oznaˇcme dále λj diagonáln´ı prvky matice D, tj.   λ1   n×n .. D= ∈C . . λn Matici A pak m˚ uˇzeme psát ve tvaru rozkladu A = XDX −1 .

(5.1)

47

Oznaˇcme dále Y ≡ X −H = (X H )−1 = (X T )−1 ,

Y = [y1 , . . . , yn ],

tj. H

Y X=X

−1

X=I

a

ykH xj

=

1, kdyˇz k = j . 0, kdyˇz k 6= 0

Pomoc´ı (regulárn´ı) matice Y m˚ uˇzeme rozklad A = XDX −1 (5.1) pˇrepsat ve tvaru A = Y −H DY H a z´ıskat tak rozklad matice AH v analogickém tvaru, tj. AH = Y DY −1 .

(5.2)

Maticové rovnosti (5.1) a (5.2) lze také pˇrepsat do tvaru AX = XD, resp. AH Y = Y D, Y H A = DY H , tj. Axj = xj λj , resp. AH yj = yj λj ,

yjH A = λj yjH ,

kde j = 1, . . . , n.

Vid´ıme, ˇze xj jsou pravé vlastn´ı vektory, yj levé vlastn´ı vektory a λj vlastn´ı ˇc´ısla matice A. Pravé vlastn´ı vektory jsou normalizovány kxj k = 1 pomoc´ı nˇejaké normy k · k (zámˇernˇe nespecifikujeme jaké). Levé vlastn´ı vektory jsou pak normalizovány u m˚ uˇzeme matici A tak, aby platilo yjH xj = 1. Uˇzit´ım obou sad vlastn´ıch vektor˚ zapsat pomoc´ı tzv. dyadického rozvoje následuj´ıc´ım zp˚ usobem. Zˇrejmˇe plat´ı    y1H λ1   ..   ... A = XDY H = [x1 , . . . , xn ]   .  ynH

λn 

 y1H n  ..  X = [x1 λ1 , . . . , xn λn ]  .  = xj λj yjH . j=1 ynH

(5.3)

Rozklad A = XDX −1 , resp. A = XDY H , se nˇekdy naz´ yvá spektráln´ı rozklad matice A.

5.2

Mocninn´ a metoda pro diagonalizovateln´ e matice

Uvaˇzujme diagonalizovatelnouPmatici A ∈ Cn×n a jej´ı spektráln´ı rozklad, resp. dyadick´ y rozvoj A = XDX −1 = nj=1 xj λj yjH . Protoˇze matice A je diagonalizovatelná, jej´ı pravé (a také levé) vlastn´ı vektory xj (resp yj ) tvoˇr´ı bázi celého Cn . Necht’ v ∈ Cn je libovoln´ y vektor a νj , j = 1, . . . , n, jeho souˇradnice v bázi xj , tj.   ν 1 n X   v= xj νj = X  ...  . j=1 νn

48

Zˇrejmˇe plat´ı 

   ν1 λ 1 ν1 n  ..   ..  X −1 −1 Av = (XDX )v = XDX X  .  = X  .  = xj (λj νj ). j=1 νn λ n νn Obdobnˇe, pro libovolné pˇrirozené k plat´ı 

 λ`−1 n 1 ν1   X . ` −1 `−1 −1 . A v = (XDX )(A v) = XDX X  xj (λ`j νj ). = . j=1 λ`−1 n νn Oznaˇcme λ1 vlastn´ı ˇc´ıslo s nejvˇetˇs´ı absolutn´ı hodnotou a pˇredpokládejme, ˇze je nenulové (tedy, ˇze matice A je nenulová), tj. |λ1 | = %(A),

λ1 6= 0;

pˇredpokládejme také ν1 6= 0.

Pˇredpoklad ν1 6= 0 nen´ı pˇri praktick´ ych v´ ypoˇctech (tj. v aritmetice s koneˇcnou pˇresnost´ı) pˇr´ıliˇs d˚ uleˇzit´ y a je témˇeˇr vˇzdy vynucen zaokrouhlovac´ımi chybami, viz [15, kapitola 7.3.1]. Pak zˇrejmˇe ! n n X X νj λj (λ1 ν1 ), Av = x1 (λ1 ν1 ) + xj (λj νj ) = x1 + xj λ ν 1 1 j=2 j=2 resp. A` v =

x1 +

n X j=2

xj

λj λ1

`

νj ν1

!

(λ`1 ν1 ),

` = 1, 2, 3, . . . .

Protoˇze vlevo je mocnina matice, mohlo by se stát, ˇze prvky vektoru A` v, resp. jejich absolutn´ı hodnoty, porostou do nekoneˇcna. Abychom tomu zabránili, budeme vektor normalizovat, neboli ` ! ` n X A` v λj νj λ 1 ν1 = x + x , (5.4) 1 j ` vk kA` vk λ ν kA 1 1 j=2 kde zlomek nalevo je vektor délky (resp. normy) jedna a zlomek napravo je skalár. Pokud plat´ı |λ1 | > |λj | pro j = 2, . . . , n, pak zˇrejmˇe λj < 1, λ1 a tedy lim

`−→∞

λj λ1

` =0

a také

lim

`−→∞

n X j=2

xj

λj λ1

`

νj ν1

= 0.

49

A proto za pˇredpokladu, ˇze matice A má jediné (a jednoduché) vlastn´ı ˇc´ıslo, pro které plat´ı |λ1 | = %(A), pak A` v λ`1 ν1 lim = lim x1 ` . `−→∞ kA` vk `−→∞ kA vk Posloupnost λ`1 ν1 kA` vk obecnˇe limitu nemá. Staˇc´ı si uvˇedomit, co se dˇeje, kdyˇz je λ1 záporné. Protoˇze jsou A` v e, plat´ı ale velikosti (resp. normy) obou vektor˚ u kA ` vk a x1 rovny jedn´ ` λ ν1 lim 1` = 1. `−→∞ kA vk `

A v Pokud budeme kaˇzd´ y vektor kA ıc násobit nˇejakou vhodnˇe zvolenou komplexn´ı ` vk nav´ jednotkou η` (|η` | = 1, η` = exp(i ϕ` )), napˇr. tak aby prvn´ı nenulová sloˇzka vektoru z˚ ustávala kladná, pak A` v lim η` = x1 . `−→∞ kA` vk

Pokud libovoln´ y vektor v násob´ıme stále dokola matic´ı A a meziv´ ysledky (ˇsikovnˇe) normalizujeme, proces bude konvergovat k (pravému) vlastn´ımu vektoru x1 , kter´ y odpov´ıdá vlastn´ımu ˇc´ıslu λ1 .

5.3

Mocninn´ a metoda pro obecn´ eˇ ctvercov´ e matice

Pˇredpoklad diagonalizovatelnosti v pˇredchoz´ı sekci byl pouze z d˚ uvodu zjednoduˇsen´ı v´ ykladu. Mocninnou metodu zformulujeme v následuj´ıc´ı vˇetˇe pro obecné ˇctvercové matice. Vˇ eta 8. Necht’ A ∈ Cn×n je libovolná ˇctvercová matice, λ1 , . . . , λn jej´ı vlastn´ı ˇc´ısla, pˇriˇcemˇz |λ1 | = %(A), a x1 je odpov´ıdaj´ıc´ı vlastn´ı vektor, tj. Ax1 = x1 λ1 . Necht’ v ∈ Cn je libovolný vektor. Pokud plat´ı |λ1 | > |λj |, j = 2, . . . , n a zároveˇ n ν1 6= 0, pak A` v η` = x1 `−→∞ kA` vk lim

pro nˇejaká vhodnˇe volená η` , |η` | = 1.

50

Pro diagonalizovatelné matice je vˇeta dokázána jiˇz v pˇredchoz´ı sekci. V d˚ ukazu pro obecné matice by bylo potˇreba zavést tzv. zobecnˇené vlastn´ı vektory a uvaˇzovat netriviáln´ı Jordanovy bloky (tj. dimenze 2×2 a vˇetˇs´ı) a sledovat, jak se chovaj´ı jejich mocniny, viz napˇr. [11, kapitoly 1.8, 2.4]. Postup je jinak stejn´ y jako v pˇredchoz´ı sekci, jen techniˇctˇejˇs´ı. Vˇeta opˇet obsahuje formáln´ı pˇrepoklad ν1 6= 0, kter´ y nen´ı pˇri praktick´ ych v´ ypoˇctech (tj. v aritmetice s koneˇcnou pˇresnost´ı) pˇr´ıliˇs d˚ uleˇzit´ y ani v pˇr´ıpadˇe obecn´ ych matic. Opˇet je témˇer vˇzdy vynucen vlivem zaokrouhlovac´ıch chyb, viz [15, kapitola 7.3.1]. Z tohoto d˚ uvodu se také pˇr´ıliˇs nezab´ yváme v´ yznamem ˇc´ısla ν1 pro obecnou matici A (v pˇredchoz´ı sekci pˇredstavovala ˇc´ısla νj souˇradnice v bázi xj vlastn´ıch vektor˚ u matice A; vlastn´ı vektory obecné matice n ale obecnˇe netvoˇr´ı bázi C , museli bychom si vz´ıt na pomoc právˇe v´ yˇse zm´ınˇené zobecnˇené vlastn´ı vektory). Obecnˇe m˚ uˇzeme algoritmus mocninné metody shrnout do následuj´ıc´ıch schématick´ ych krok˚ u: • • • • • •

Dáno: obecná ˇctvercová matice A ∈ Cn×n . Vyber nebo vytvoˇr náhodn´ y vektor v ∈ Cn . Opakuj kroky: v ← Av, v ← v/kvk, kde k · k je nˇejaká vhodnˇe zvolená norma, dokud nejsi s vektorem v spokojen.

Ze vztahu (5.4) je zˇrejmé, ˇze mocninná metoda bude konvergovat k vlastn´ımu vektoru x1 tak rychle, jak rychle p˚ ujde ` λj max , ` = 1, 2, 3, . . . j = 2,...,n λ1 k nule. Pro dalˇs´ı detaily, viz [15, kapitola 7.3.1], [17, kapitola 15].

51

6

V´ ypoˇ cet Perronova vlastn´ıho vektoru

Z v´ ykladu o mocinné metodˇe vid´ıme, ˇze na to, abychom mohli PageRank vektor spoˇc´ıtat (touto metodou), mus´ı b´ yt jemu odpov´ıdaj´ıc´ı vlastn´ı ˇc´ıslo λ1 = 1 jednoduché (coˇz v pˇr´ıpadˇe googlovské matice G, G > 0, je, viz vˇetu 6) a v absolutn´ı hodnotˇe ostˇre vˇetˇs´ı neˇz vˇsechna ostatn´ı vlastn´ı ˇc´ısla. Zda tomu tak je, budeme nejprve ilustrovat na pˇr´ıkladech.

6.1

(Im)primitivn´ı matice

Vezmˇeme si ku pomoci opˇet náˇs modelov´ y internet, ze kterého vyˇskrtáme vˇsechny hrany tak, aby matice jemu odpov´ıdaj´ıc´ı z˚ ustala stochastická a nerozloˇzitelná, viz obrázek 6.1. Tomuto internetu odpov´ıdá matice hyperlink˚ u H, která má v kaˇzdém ˇra´dku a v kaˇzdém sloupci jedin´ y nenulov´ y prvek. Rovnice pro v´ ypoˇcet PageRank '$

'$

P % &% &% I @ I @ @@ @ @@ % @ '$ @@ @'$

P1

2

R @

P3

P6

&% &% I @ @@ @@ '$ '$ @@ R @ P4 P5

%

&%

%%

%

&%

Obrázek 6.1: Jednoduch´ y model internetu z obrázku 1.1 po vyˇskrtán´ı nˇekter´ ych odkaz˚ u (hran); symbol “ znaˇc´ı vyˇskrtnutou hranu. Matice hyperlink˚ u, která ” mu odpov´ıdá, je stochastická (kaˇzdá stránka obsahuje alespoˇ n jeden odkaz) a nerozloˇzitelná (z kaˇzdé stránky je moˇzné se dostat na kteroukoliv jinou stránku).

%

52

vektoru z této matice hyperlink˚ u pak    r(P1 ) 0 1/1  r(P2 )   0 0     r(P3 )   1/1 0     r(P4 )  =  0 0     r(P5 )   0 0 r(P6 ) 0 0 | {z } | π

vypadá následovnˇe   r(P1 ) 0 0 0 0   0 0 0 1/1    r(P2 )    0 0 0 0   r(P3 )    r(P4 )  . 1/1 0 0 0    0 1/1 0 0   r(P5 )  r(P6 ) 0 0 1/1 0 {z } | {z } π HT

(6.1)

Po permutaci vrchol˚ u grafu (pˇreˇc´ıslován´ı stránek) permutac´ı 1 2 3 4 5 6 1 6 2 3 4 5 tak, jak je naznaˇceno na  0  0   0 T S ≡ ΠHΠ =   0   0 1

obrázku 6.2, dostaneme matici   1 0 0 0 0  0 1 0 0 0     0 0 1 0 0   , kde Π =    0 0 0 1 0    0 0 0 0 1  0 0 0 0 0

1 0 0 0 0 0

0 0 0 0 0 1

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

       

je permutaˇcn´ı matice. Zˇrejmˇe je tato matice S stochastická a nerozloˇzitelná (z kaˇzdého vrcholu odpov´ıdaj´ıc´ıho grafu je moˇzné dostat se do vˇsech ostatn´ıch vrchol˚ u). Pod´ıvejme se, jak budou vypadat jej´ı vlastn´ı ˇc´ısla. Zˇrejmˇe det(S − λI) = 0,  −λ 1 0 0 0 0  0 −λ 1 0 0 0     0 0 −λ 1 0 0     = 0, det   0 0 0 −λ 1 0    0 0 0 0 −λ 1  1 0 0 0 0 −λ    0 1 0 0 0 0   −λ 1 0 0 0  0        0 −λ 1 0 0  = 0, 0  − 1 det     0 0 −λ 1 0  1  −λ 0 0 0 −λ 1 



−λ  0   −λ det   0  0 0

1 −λ 0 0 0

0 1 −λ 0 0

0 0 1 −λ 0

λ6 − 1 = 0, λ6 = 1, tedy λ1,2 = ±1,

λ3,4,5,6

√ 1 3 =± ± i. 2 2 53

'$

P1

'$

P6

&% &% @ I @ @ @ @ @ '$ R @ @'$

P2

P5 &%

&% '$

P3 &%

'$ -

P4 &%

Obrázek 6.2: Internet z obrázku 6.1 po permutaci oˇc´ıslován´ı stránek. Vid´ıme, ˇze |λ1 | = |λ2 | = |λ3 | = |λ4 | = |λ5 | = |λ6 |, a proto v tomto pˇr´ıpadˇe nebude mocninná metoda fungovat, resp. konvergovat. To je zp˚ usobeno t´ım, ˇze matice hyperlink˚ u je tzv. imprimitivn´ı. Z obrázku 6.2 je zˇrejmé, ˇze graf tohoto internetu je cyklick´ y (pˇresnˇeji bychom ˇrekli, ˇze tvoˇr´ı tzv. kruˇznici; v terminologii Markov´ ych ˇretˇezec˚ u bychom ˇrekli, ˇze se jedná o periodický ˇretˇezec). Právˇe (a)cykliˇcnost grafu spolu s jeho silnou souvislost´ı (nerozloˇzitelnost´ı odpov´ıdaj´ıc´ı nezáporné matice) definuje (im)primitivn´ı matice. Pˇresná definice následuje. Definici i následuj´ıc´ı vˇety lze nalézt napˇr. v [17, str. 172–175]. Definice 13 ((Im)primitivn´ı matice, index imprimitivity). Nezáporná nerozloˇziteln´ a matice A ∈ Rn×n se nazývá primitivn´ı, pokud na spektráln´ı kruˇznici K (A) ≡ {%(A) exp(i ϕ) : 0 ≤ ϕ < 2π}, tj. na kruˇznici v komplexn´ı rovinˇe se stˇredem v poˇcátku a o polomˇeru %(A), leˇz´ı jediné vlastn´ı ˇc´ıslo λ = %(A). Naopak nezáporn´ a n×n nerozloˇzitelná matice A ∈ R , která nen´ı primitivn´ı, se nazývá imprimitivn´ı. Poˇcet vlastn´ıch ˇc´ısel leˇz´ıc´ıch na spektráln´ı kruˇznici K (A) se nazývá index imprimitivity matice A.

6.2

Spektr´ aln´ı vlastnosti (im)primitivn´ıch matic

Primitivita je z hlediska PageRanku velmi v´ yznamná. Pokud by matice byla imprimitivn´ı, nefungovala by mocninná metoda a nebyli bychom schopni PageRank spoˇc´ıtat, a proto si uvedeme jeˇstˇe nˇekolik vˇet, z nichˇz nˇekteré uvedeme bez u ´pln´ ych d˚ ukaz˚ u. Prvn´ı a nejd˚ uleˇzitˇejˇs´ı z tˇechto vˇet popisuje, jak jsou vlastn´ı ˇc´ısla rozm´ıstˇena na spektráln´ı kruˇznici, viz napˇr. [17, str. 173] nebo [14, Vol. 2, kapitola XIII, §2, str. 53–66] (pˇr´ıpadnˇe p˚ uvodn´ı ruské vydán´ı [13, kapitola XIII, §2, str. 354–365]).

54

Vˇ eta 9. Necht’ A ∈ Rn×n je nezáporná nerozloˇzitelná matice a necht’ h je jej´ı index imprimitivity. Pak λ1 ,

λ2 ≡ λ1 ω,

λ3 ≡ λ1 ω 2 ,

...,

λh ≡ λ1 ω h−1 ,

kde λ1 ≡ %(A) ∈ R,

ω ≡ exp(2πi/h) ∈ C,

jsou jednoduchá vlastn´ı ˇc´ısla matice A. Pokud nav´ıc h > 1, existuje permutaˇcn´ı matice Π taková, ˇze   0 A1,2 }n1   0 A2,3 h   }n2 X   .. T . . . . ΠAΠ =  , nj = n,  . . .   j=1  0 Ah−1,h  }nh−1 Ah,1 0 }nh | {z } | {z } | {z } · · · | {z } n1 n2 n3 nh

(6.2)

tj. diagonáln´ı (vyznaˇcené nulové) bloky jsou ˇctvercové a jediné nenulové bloky jsou nezáporné (obecnˇe obdéln´ıkové) bloky Aj,j+1 ∈ Rnj ×nj+1 , j = 1, . . . , h − 1, a Ah,1 ∈ Rnh ×n1 . ´ y d˚ D˚ ukaz. D˚ ukaz jen naznaˇc´ıme. Upln´ ukaz lze nalézt napˇr. v knize [14]. Nezáporná nerozloˇzitelná matice s indexem imprimitivity h má právˇe h vlastn´ıch ˇc´ısel na spektráln´ı kruˇznici. Necht’ jsou to λ` ≡ %(A) exp(i ϕ` ),

` = 1, . . . , h.

Podle vˇety 7 je jedn´ım z nich pˇr´ımo spektráln´ı polomˇer. Toto vlastn´ı ˇc´ıslo je nav´ıc jednoduché. Necht’ tedy napˇr. λ1 = %(A)

neboli

ϕ1 ≡ 0,

a necht’ dále ϕ1 < ϕ2 ≤ ϕ3 ≤ . . . ≤ ϕh < 2π. Uvaˇzujme dále vlastn´ı vektor x` ∈ Cn pˇr´ısluˇsn´ y vlastn´ımu ˇc´ıslu λ` , tj. Ax` = x` λ` , x` = [ξ1 , . . . , ξn ] 6= 0, kde ξj = |ξj | exp(i ψj ), pak   exp(i ψ1 )   ... x` = D` |x` |, kde D` =  (6.3) . exp(i ψn ) Zˇrejmˇe D` D` = |D` | = I. Takˇze Ax` AD` |x` | D` AD` |x` | exp(−i ϕ` )D` AD` |x` | M |x` |

= = = = =

x` λ ` , D` |x` |%(A) exp(i ϕ` ), |x` |%(A) exp(i ϕ` ), |x` |%(A), |x` |%(A),

(6.4)

55

kde M ≡ exp(−i ϕ` )D` AD` ∈ Cn×n ,

M |x` | ∈ Rn

(6.5)

je obecnˇe komplexn´ı matice, resp. reáln´ y vektor. Splˇ nuj´ı tedy pˇredpoklady prvn´ıho tvrzen´ı lemmatu 6. Uˇzit´ım nerovnosti (2.8) z lemmatu 6 (spolu s (6.4)) dostáváme |M | |x` | ≥ M |x` | = |x` |%(A).

(6.6)

Protoˇze matice D` je diagonáln´ı s komplexn´ımi jednotkami na diagonále, plat´ı zˇrejmˇe |M | = A,

(6.7)

viz (6.3) a (6.5). Nerovnost (6.6) tak m˚ uˇze b´ yt dále upravena |M | |x` | = A|x` | ≥ |x` |%(A). Protoˇze ale nezáporná matice A nem˚ uˇze ˇza´dn´ y nezáporn´ y vektor |x` | zes´ılit po komponentách v´ıce, neˇz zes´ıl´ı vlastn´ı vektor x1 > 0 odpov´ıdaj´ıc´ı nejvˇetˇs´ımu (kladnému) vlastn´ımu ˇc´ıslu λ1 = %(A), mus´ı v pˇredchoz´ıch vztaz´ıch nastat rovnosti. Speciálnˇe |M | |x` | = |x` |%(A). Z pˇredchoz´ı rovnice a z rovnice (6.4) pak plyne, ˇze |x` | je vlastn´ım vektorem matice |M | (pˇripomeˇ nme, ˇze |M | = A) a zároveˇ n matice M , kter´ y odpov´ıdá v obou pˇr´ıpadech stejnému vlastn´ımu ˇc´ıslu. Tedy |M | |x` | = M |x` |.

(6.8)

D´ıky tomu, ˇze |x` | je také vlastn´ım vektorem matice A odpov´ıdaj´ıc´ı vlastn´ımu ˇc´ıslu λ1 = %(A), je, podle vˇety 7, kladn´ y, tj. |x` | > 0. Podle druhého tvrzen´ı lemmatu 6 T (viz (2.9), kde A ≡ |x` | > 0, B ≡ M T ) dostáváme, ˇze rovnost (6.8) m˚ uˇze b´ yt splnˇena jen tehdy, kdyˇz |M | = M. Tato rovnice spolu s rovnicemi (6.5) a (6.7) dává nejd˚ uleˇzitˇejˇs´ı identitu A = exp(−i ϕ` )D` AD` ,

` = 1, . . . , h.

Uvaˇzujme tyto dvˇe rovnosti, napˇr. A = exp(−i ϕ`1 )D`1 AD`1

a

A = exp(−i ϕ`2 )D`2 AD`2

⇐⇒

exp(i ϕ`2 )D`2 AD`2 = A

pro `1 = 1, . . . , h, `2 = 1, . . . , h. Jejich kombinac´ı, pˇresnˇeji dosazen´ım druhé (v obou variantách) do prvn´ı, dostáváme A = exp(−i (ϕ`1 + ϕ`2 ))D`1 D`2 AD`2 D`1 ,

resp.

A = exp(−i (ϕ`1 − ϕ`2 ))D`1 D`2 AD`2 D`1 .

56

Zde jiˇz d˚ ukaz nepatrnˇe zjednoduˇs´ıme. Lze ukázat, ˇze ϕ`1 ± ϕ`2 ∈ {ϕ1 , . . . , ϕh }

a

D`2 D`1 , D`2 D`1 , ∈ {D1 , . . . , Dh }

a také, ˇze %(A) exp(i (ϕ`1 ± ϕ`2 )) ∈ {λ1 , . . . , λh }. ´ Uhly ϕ` tud´ıˇz tvoˇr´ı koneˇcnou aditivn´ı Abelovu (komutativn´ı) grupu ˇra´du h. Plat´ı proto hϕ` = ϕ1 ≡ 0. Vlastn´ı ˇc´ısla λ` , ` = 1, . . . , h leˇz´ı na vrhcholech pravidelného h-´ uheln´ıku, tedy ϕ2 = 2π/h,

ϕ` = (` − 1)ϕ2 = 2π(` − 1)/h,

` = 3, . . . , h.

Takˇze plat´ı λ` = %(A) exp(i ϕ` ) = %(A)ω (`−1) ,

ω ≡ 2πi/h,

` = 1, . . . , h,

pˇriˇcemˇz tato vlastn´ı ˇc´ısla jsou r˚ uzná, takˇze jednoduchá, coˇz jsme chtˇeli dokázat. Podobnˇe se dá ukázat, ˇze dokonce celé spektrum (vˇsech n vlastn´ıch ˇc´ısel) se nezmˇen´ı pˇri pootoˇcen´ı komplexn´ı roviny o libovoln´ y celoˇc´ıseln´ y násobek u ´hlu 2π/h. Podobnˇe také zjist´ıme, ˇze matice D` tvoˇr´ı koneˇcnou multiplikativn´ı Abelovu (komutativn´ı) grupu ˇra´du h. Plat´ı tedy D`h = D1 ≡ I. Srovnán´ım diagonáln´ıch prvk˚ u matice D2 podle jednotliv´ ych u ´hl˚ u ψj z´ıskáme permutaci, která je zmiˇ nována v druhé ˇcásti vˇety. Pro podrobnosti viz [14, Vol. 2, str. 61–62].

6.3

Testov´ an´ı (im)primitivity matice

Nezáporná nerozloˇzitelná matice má obecnˇe h jednoduchých vlastn´ıch ˇc´ısel, jejichˇz absolutn´ı hodnota je rovna spektráln´ımu polomˇeru. Tato ˇc´ısla jsou rozm´ıstˇena pravidelnˇe na spektráln´ı kruˇznici K (A), pˇriˇcemˇz jedno z nich je kladné. Jsou to tedy koˇreny binomické rovice h λh = %(A) . Aby mocninná metoda fungovala, potˇrebujeme, aby na spektráln´ı kruˇznici leˇzelo jediné vlastn´ı ˇc´ıslo. Jestliˇze máme nezápornou nerozloˇzitelnou matici, je pro nás velice d˚ uleˇzité zjistit, zda je primitivn´ı, tj. zda h = 1. K tomuto u ´ˇcelu slouˇz´ı dva základn´ı testy, které jsou zformulované v následuj´ıc´ıch vˇetách. Prvn´ı je velmi snadn´ y, viz napˇr. [17, str. 174]. Vˇ eta 10. Necht’ A ∈ Rn×n je nezáporná nerozloˇzitelná matice. Pokud existuje alespoˇ n jeden pozitivn´ı prvek na diagonále, pak je matice A primitivn´ı. D˚ ukaz. D˚ ukaz je jednoduch´ y. Pokud je matice imprimitivn´ı, ˇcili je jej´ı index imprimitivity h vˇetˇs´ı neˇz jedna, tj. h > 1, pak podle vˇety 9 existuje permutaˇcn´ı matice Π taková, ˇze simultánn´ı permutace ˇrádk˚ u a sloupc˚ u ΠAΠT vede na matici, která

57

má na diagonále právˇe h nulov´ ych ˇctvercov´ ych blok˚ u. Speciálnˇe vˇsechny diagonáln´ı T prvky permutované matice ΠAΠ jsou nulové. Pˇri simultánn´ı permutaci ˇra´dk˚ u a sloupc˚ u z˚ ustávaj´ı ale diagonáln´ı prvky stále na diagonále. Pokud má matice A na diagonále alespoˇ n jeden nenulov´ y prvek, pak T matice ΠAΠ má na diagonále také alespoˇ n jeden nenulov´ y prvek, pro libovolnou permutaˇcn´ı matici Π. Matice A tedy nem˚ uˇze b´ yt imprimitivn´ı. Tento test je velmi snadn´ y, avˇsak ˇcasto nepouˇziteln´ y. Podm´ınka nezáporn´ ych prvk˚ u na diagonále je pouze postaˇcuj´ıc´ı, nikoliv nutná. Pˇr´ıkladem m˚ uˇze b´ yt právˇe naˇse matice hyperlink˚ u (1.9), tj.   0 1/2 1/2 0 0 0  1 0 0 0 0 0     1/3 0  0 1/3 1/3 0 . H= (6.9)  0 0 0 0 1 0     0 0 1/3 1/3 0 1/3  0 1/2 0 0 1/2 0 Jak uvid´ıme za malou chv´ıli, tato matice hyperlink˚ u skuteˇcnˇe primitivn´ı je, má vˇsak vˇsechny diagonáln´ı prvky nulové, tud´ıˇz test primitivity, kter´ y je zaloˇzen na vˇetˇe 10, pouˇz´ıt nem˚ uˇzeme. Poznamenejme jeˇstˇe, ˇze pro matici hyperlink˚ u plat´ı následuj´ıc´ı postaˇcuj´ıc´ı podm´ınka. Je-li matice hyperlink˚ u nerozloˇzitelná (nezáporná je vˇzdy), pak je primitivn´ı právˇe tehdy, kdyˇz v internetu existuje alespoˇ n jedna stránka, která odkazuje sama na sebe. Nakonec uvedeme vˇetu, která formuluje nutnou a postaˇcuj´ıc´ı podm´ınku primitivity, viz napˇr. [17, str. 174]. Vˇ eta 11. Necht’ A ∈ Rn×n je nezáporná matice. Matice A je primitivn´ı tehdy a jen ~ tehdy, kdyˇz existuje takové `, ˇze A` > 0, tj. pokud v grafu G(A) existuje cesta mezi libovolnými dvˇema uzly stejné délky `. D˚ ukaz. D˚ ukaz opˇet jen naznaˇc´ıme. Podle vˇety 9 lze imprimitivn´ı matice s indexem primitivity h > 1 simultánnˇe pˇrepermutovat do tvaru (6.2). Simultánn´ı permutace ˇra´dk˚ u a sloupc˚ u matice pˇredstavuje jen pˇreˇc´ıslován´ı vrchol˚ u grafu. M˚ uˇzeme tedy bez u ´jmy na obecnosti uvaˇzovat matici pˇr´ımo ve tvaru (6.2). Vrcholy mnoˇziny I1 ≡ {1, . . . , n1 } mohou b´ yt pospojovány pouze cestami délek h, 2h, 3h, atd. Z vrchol˚ u mnoˇziny I1 do vrchol˚ u mnoˇziny I2 ≡ {n1 + 1, . . . , n1 + n2 } vˇsak mohou existovat pouze cesty délek 1, 1 + h, 1 + 2h, 1 + 3h, atd. Cesty stejn´ ych délek tak mohou existovat jen tehdy, kdyˇz h = 1, tj. kdyˇz je matice primitivn´ı. Vˇsimnˇeme si, ˇze vˇeta 11 nevyˇzaduje nerozloˇzitelnost matice. Pokud ale plat´ı A` > 0 pro nˇejaké `, pak je A nerozloˇzitelná, a naopak pokud je matice rozloˇzitelná, tj. v jej´ım grafu existuje dvojice bod˚ u, mezi kter´ ymi nevede ˇza´dná cesta, pak bude ` pˇr´ısluˇsná komponenta matice A nulová pro libovolné `, viz lemmata 7 a 8 a také viz definici 6.

58

Poznamenejme, ˇze pro v´ yˇse uvedenou matici ` = 5. Zˇrejmˇe  0 3 3 0  6 0 0 0  1 2 0 0 2 H=   0 0 0 0 6  0 0 2 2 0 3 0 0  12 0 0 3  0 9 9 0   1 0 3 5 2  H2 =  0 6 6 18  0  2 3 0 2 9 0 3 3  0 36 42 6  72 0 0 18   28 1 6 12 22  H3 =  0 12 108  12 18  18 6 28 22 6 36 27 6  150 9 18 60  0 108 126 18  1  4  30 60 70 40 H = 324   54 18 84 66  46 60 39 40 135 9 42 60  90 504 588 174  900 54 108 360  1  5  500 174 282 332 H = 1944   276 360 234 240  438 174 392 332 138 504 495 174

hyperlink˚ u H plat´ı H ` > 0 pro 0 0 2 6 0 3

0 0 0 0 2 0



3 0 6 0 11 0

0 0 2 6 0 3



18 18 28 66 12 33

6 0 12 0 22 0



69 54 96 36 127 45

18 18 28 66 12 33



450 414 464 762 354 543

138 108 192 72 254 90



   ,   

   ,   

   ,   

   ,   

    > 0;   

viz také tabulku 6.1, kde jsou vypsány cesty délky pˇet mezi libovoln´ ymi dvˇema e + (1 − α)E, vrcholy grafu. Reálnˇe ale pracujeme s googlovskou matic´ı G = αH 0 < α < 1, pro kterou plat´ı G` > 0 pro ` = 1 a která je tedy vˇzdy primitivn´ı.

59

Googlovská matice 1 1 G = α H + deT + (1 − α) eeT , n n

0<α<1

(6.10)

je nezáporná (pˇresnˇeji ˇreˇceno kladná), nerozloˇzitelná a primitivn´ı. Mocninná metoda aplikovaná na matici GT bude pro libovoln´ y startovac´ı vektor π0 , π0 > 0, vˇzdy konvergovat k jednoznaˇcnˇe danému Perronovu vlastn´ımu vektoru π, π > 0, kter´ y je zároveˇ n hledan´ ym PageRank vektorem. Pro vyjasnˇen´ı vztah˚ u mezi jednotliv´ ymi druhy matic opˇet odkazujeme na schéma na obrázku 6.3 na konci textu na str. 62.

6.4

Mocninn´ a metoda pro googlovskou matici

V sekci, kde jsme vysvˇetlili mocninnou metodu pro obecné ˇctvercové matice, jsme zm´ınili, ˇze je potˇreba pouˇz´ıt nˇejakou vhodnˇe zvolenou normu. Nyn´ı mocninnou metodu specifikujeme pro googlovskou matici, a proto potˇrebujeme vybrat uˇz konkrétn´ı normu. Lemma 11. Necht’ vektor v ≥ 0, kvk1 = 1 a S je stochastická matice. Pak pro vektor w, w = S T v, plat´ı w ≥ 0, kwk1 = 1. D˚ ukaz. Pro dokázán´ı tohoto lemmatu si staˇc´ı uvˇedomit, ˇze pokud existuje vektor v ≥ 0, jehoˇz souˇcet prvk˚ u je roven jedné, pak urˇcitˇe vektor w, kter´ y vznikne T vynásoben´ım stochastické matice S (která má souˇcet prvk˚ u ve sloupci roven jedné) vektorem v, je také kladn´ y a jeho jedniˇcková norma je také jedna. Vezmˇeme si nyn´ı googlovskou matici G (G > 0) a zvolme si kladn´ y (protoˇze PageRank vektor pˇredpokládáme kladn´ y) startovac´ı vektor π0 > 0, kπ0 k1 = 1. Pro vektor   r` (P1 )   .. π` ≡ (GT )` π0 ≡   , kde ` = 1, 2, 3, . . . . r` (Pn ) plat´ı π` > 0,

kπ` k1 = 1,

podle lemmatu 11 a také plat´ı lim π` = (GT )` π0 = π,

`−→∞

(6.11)

kde π je PageRank vektor podle vˇety 8, a tedy lim r` (Pk ) = r(Pk ),

`−→∞

k = 1, . . . , n.

(6.12)

60

Tabulka 6.1: V grafu (internetu) na obrázku 1.1 existuje cesta délky pˇet mezi libovoln´ ymi dvˇema vrcholy (stránkami). Odkud P1 P1 P1 P1 P1 P1 P2 P2 P2 P2 P2 P2 P3 P3 P3 P3 P3 P3 P4 P4 P4 P4 P4 P4 P5 P5 P5 P5 P5 P5 P6 P6 P6 P6 P6 P6

1 −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→

P3 P2 P3 P3 P3 P3 P1 P1 P1 P1 P1 P1 P1 P5 P5 P4 P5 P4 P5 P5 P5 P5 P5 P5 P6 P3 P3 P4 P6 P6 P5 P2 P2 P5 P5 P2

2 −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→


3 −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→


4 −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→


5 −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→ −→

Kam P1 P2 P3 P4 P5 P6 P1 P2 P3 P4 P5 P6 P1 P2 P3 P4 P5 P6 P1 P2 P3 P4 P5 P6 P1 P2 P3 P4 P5 P6 P1 P2 P3 P4 P5 P6

61

Obrázek 6.3: Pˇrehled vztah˚ u mezi jednotliv´ ymi druhy ˇctvercov´ ych matic

62

Nezáporné matice A, A ≥ 0, aj,k ≥ 0 (sekce 2.1, definice 9, str. 25)

P Stochastické matice S, k sj,k = 1 (sekce 2.2, definice 10, str. 29) • ∃λ > 0, λ = %(S) = 1, obecnˇe násobné (vˇeta 3, sekce 2.2, str. 29) • e ≡ [1, . . . , 1]T , Se = e • ∃π ≥ 0, S T π = π, obecnˇe nejednoznaˇcn´ y (sekce 2.3, vˇeta 4, str. 30) e ≡ H + 1 deT • napˇr. opravená matice H, tj. H n

•

Kladné stochastické matice e + (1 − α) 1 eeT , 0 < α < 1 • napˇr. googlovská matice G ≡ αH n P Substochastické matice A, 1 ≥ k aj,k ≥ 0 (sekce 4.1, str. 42) • napˇr. matice hyperlink˚ uH

•

Primitivn´ı matice A (sekce 6.1, definice 13, str. 54) • ∃` ∈ N, A` > 0 (sekce 6.3, vˇeta 11, str. 58)

Nezáporné nerozloˇzitelné matice A • (I + A)n−1 > 0 (sekce 3.2, lemma 9, str. 38) • ∃λ > 0, λ = %(A), jednoduché • ∃x > 0, Ax = x%(A), jednoznaˇcnˇe dan´ y (sekce 3.4, vˇeta 7, str. 39)

Nerozloˇzitelné matice (sekce 3.2, definice 11, str. 35)

Kladné matice A, A > 0, aj,k > 0 (sekce 2.1, definice 9, str. 25) • ∃λ > 0, λ = %(A), jednoduché • ∃x > 0, Ax = x%(A), jednoznaˇcnˇe dan´ y (sekce 2.4, vˇeta 5, str. 31; existence) (sekce 3.3, vˇeta 6, str. 39; jednoznaˇcnost)

Vrat’me se nyn´ı k definici PageRanku, viz rovnici (1.7). K urˇcen´ı hodnot r(Pk ) je potˇreba provést limitn´ı pˇrechod (6.12), coˇz nen´ı v praxi moˇzné. Mocninná metoda je v tento okamˇzik vhodn´ y iteraˇcn´ı postup, jak nalézt alespoˇ n nˇejakou aproximaci hodnot r(Pk ). Tento pˇr´ıstup také navrhli zakladatelé PageRank, Brin a Page, protoˇze si byli vˇedomi, ˇze hodnoty r(Pk ), tedy PageRank odkazuj´ıc´ıch stránek na Pj , jsou neznámé. Na zaˇca´tku vˇsem stránkám na webu pˇriˇrad´ıme napˇr´ıklad stejné hodnoty PageRank. Tyto hodnoty jsou 1/n, kde n je poˇcet vˇsech stran webu. Tento postup pak poˇc´ıtá r` (Pk ), tj. aproximaci r(Pk ) v `-tém kroku pro kaˇzdou stránku Pj . Dojdeme proto k modifikaci vzorce (1.7) r`+1 (Pk ) =

X r` (Pj ) . |Pj | P ∈B j

(6.13)

Pk

O tomto vztahu mus´ıme vˇsak jeˇstˇe chv´ıli uvaˇzovat. Prvn´ı problém s touto rovnic´ı je, ˇze nepoˇc´ıtá s modelem uˇzivatele, kter´ y náhodnˇe pˇrecház´ı ze stránky na stránku (s modelem random surfer) a obˇcas naraz´ı na dangling node, tj. vrchol grafu, do kterého vede cesta, ale uˇz nevede cesta z nˇej. Je proto potˇreba zaprvé zahrnout do rovnice (1.7) dangling node vektor. Druh´ ym problémem je, ˇze vztah nepoˇc´ıtá ani s uˇzivatelem, kter´ y nejenom ˇze procház´ı internetem pomoc´ı odkaz˚ u, ale obˇcas také nap´ıˇse pˇr´ımo adresu webové stránky a teleportuje se jinam, a proto je nutné zahrnout do definice teleportaˇcn´ı matici. Definici PageRanku, která zahrnuje jiˇz vˇsechny v´ yˇse zm´ınˇené modifikace je n X r` (Pj ) α X 1−α X + r` (Pj ) + r` (Pj ), r`+1 (Pk ) = α |P n n j| j=1 Pj ∈D Pj ∈BPk | {z } | {z } | {z } (deT )T π`

H T π`

(6.14)

(eeT )π`

kde D je mnoˇzina vˇsech stránek, které neobsahuj´ı ˇza´dn´ y odkaz (dangling nodes) a kde jednotlivé souˇcty pˇredstavuj´ı v´ yˇse zm´ınˇené modifikace, viz (6.10). Po krátké u ´vaze zjist´ıme, ˇze vrozec m˚ uˇzeme jeˇstˇe upravit. V´ıme totiˇz, ˇze plat´ı n X

r` (Pj ) = kπ` k1 = 1,

j=1

a proto r`+1 (Pk ) = α

X r` (Pj ) 1−α α X + r` (Pj ) + . |P n n j| P ∈B P ∈D j

Pk

(6.15)

j

Poznamenejme, ˇze p˚ uvodn´ı definice pˇred u ´pravami je platná a naprosto správná pro model, ve kterém by nebyl problém s dangling nodes, s nerozloˇzitelnost´ı a také s teleportac´ı. V´ ypoˇcet PageRank vektoru pro náˇs modelov´ y internet z obrázku 1.1 je moˇzné nalézt v pˇr´ıloze A.

63

Z´ avˇ er V této práci jsme se zab´ yvali PageRank vektorem, kter´ y je vyuˇz´ıván v mnoha odvˇetv´ıch, napˇr´ıklad silniˇcn´ı doprava nebo fyzika. My jsme hovoˇrili o PageRank vektoru neboli také o Perronovu vlastn´ım vektoru v souvislosti s internetov´ ym vyhledávaˇcem Google. PageRank byl také navrˇzen pro potˇreby internetu, a to uˇz v roce 1976 Larry Pagem a Sergeyem Brinem na univerzitˇe ve Stanfordu. Pro spoleˇcnost Google se stal jej´ım srdcem, které napomáhá spoleˇcnosti si drˇzet pˇredn´ı pozici mezi internetov´ ymi vyhledávaˇci. V kapitole 1 jsme se vˇenovali nejprve nˇekter´ ym základn´ım pojm˚ um z teorie matic a jejich vlastn´ıch ˇc´ısel, z teorie graf˚ u a také jsme si uvedli p˚ uvodn´ı definici PageRank vektoru. Dále následovala prvn´ı ˇca´st práce, která se zab´ yvala existenc´ı PageRank vektoru. Zadefinovali jsme si stochastické matice, bez kter´ ych by PageRank neexistoval. Dále jsme se vˇenovali problematice (ne)rozloˇzitelnosti, protoˇze jsme zjistili, ˇze v pˇr´ıpadˇe, ˇze je matice rozloˇzitelná, nebude PageRank vektor jednoznaˇcn´ y. Museli jsme tedy upravit matici hyperlink˚ u, která obecnˇe nen´ı ani stochastická ani nerozloˇzitelná a dostali jsme googlovskou matici, pro kterou jiˇz PageRank vektor existuje a je jednoznaˇcn´ y. V druhé ˇca´sti textu jsme se vˇenovali samotnému v´ ypoˇctu PageRank vektoru. K v´ ypoˇctu byla pouˇzita mocninná metoda, kterou jsme si pˇredstavili v kapitole 5. V závˇereˇcné kapitole 6 jsme jeˇstˇe narazili na problém spojen´ y s mocninnou metodou. Zjistili jsme, ˇze proto aby se PageRank vektor ustálil k nˇejaké konkrétn´ı hodnotˇe, tj. aby mocninná metoda fungovala, potˇrebujeme pracovat s primitivn´ı matic´ı. Proto jsme si jeˇstˇe definovali (im)primitivn´ı matice a ukázali si testy (im)primitivity. Po té nám jiˇz nic nebránilo k u ´pravˇe definice PageRanku a k samotnému v´ ypoˇctu. V pr˚ ubˇehu celé práce jsme pracovali s modelov´ ym internetem o ˇsesti stránkách. Pro tento model jsme také PageRank vektor spoˇc´ıtali, viz pˇr´ılohu A.

64

A

PageRank vektor modelov´ eho internetu z obr´ azku 1.1

Zde uvád´ıme pˇr´ıklad v´ ypoˇctu PageRanku. PageRank je vypoˇc´ıtán pro náˇs modelov´ y internet z obrázku 1.1. Zvol´ıme startovac´ı vektor π0 = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]T a zkus´ıme mocninnou metodu. Ta nám ukáˇze, ˇze nejd˚ uleˇzitˇejˇs´ı stránkou je P5 a nejménˇe d˚ uleˇzitou je P6 . Zkus´ıme nyn´ı mocninnou metodu znovu, a to zaprvé pro startovac´ı vektor π0 = [1/10, 1/10, 1/10, 1/10, 1/2, 1/10]T , tzn. té nejd˚ uleˇzitˇejˇs´ı stránce P5 pˇriˇrad´ıme jiˇz na zaˇzátku nejvˇetˇs´ı d˚ uleˇzitost a vid´ıme, ˇze nic zvláˇstn´ıho se nedˇeje. Hodnoty PageRanku se ustálily po nˇekolika málo iterac´ıch a stránka P5 z˚ ustala nejd˚ uleˇzitˇejˇs´ı. Zkusme se pod´ıvat na to, co se stane, kdyˇz si jako startovac´ı vektor zvol´ıme π0 = [1/10, 1/10, 1/10, 1/10, 1/10, 1/2]T , tzv. stránce P6 pˇriˇrad´ıme na zaˇzátku nejvˇetˇs´ı d˚ uleˇzitost. Zadáme tedy faleˇsnou stopu a nejvyˇsˇs´ı d˚ uleˇzitost pˇriˇrad´ıme ve skuteˇcnosti nejménˇe d˚ uleˇzité stránce. M˚ uˇzeme vidˇet, ˇze proces konvergence trvá o nˇeco déle, ale nakonec dojdeme ke stejnému závˇeru, a to ˇze vypoˇctené PageRanky jsou r(P5 ) > r(P1 ) > r(P3 ) > r(P2 ) ≈ r(P4 ) > r(P6 ), viz obrázek A.1. Poznamenejme, ˇze zde pracujeme pouze s matic´ı hyperlink˚ u H, viz (1.8), parametr α = 1, a proto se teleportaˇcn´ı matice v´ ypoˇctu ne´ uˇcastn´ı. Na obrázku A.2 jiˇz studujeme vliv parametru α pro r˚ uzné hodnoty a pracujeme jiˇz s googlovskou matic´ı G = αH + (1 − α)E. V pˇr´ıpadˇe, kdy je α velké, má teleportaˇcn´ı matice ménˇe v´ yznamn´ y vliv a rozd´ıly mezi PageRanky jsou v´ yraznˇejˇs´ı. Zjednoznaˇcn´ı se tak poˇrad´ı stránek P2 a P4 , takˇze vid´ıme, ˇze r(P5 ) > r(P1 ) > r(P3 ) > r(P2 ) > r(P4 ) > r(P6 ).

65

V opaˇcném pˇr´ıpadˇe, tj. pro malá α, se PageRanky liˇs´ı ménˇe a nav´ıc dojde k zámˇenˇe poˇrad´ı stránek P3 a P2 na r(P5 ) > r(P1 ) > r(P2 ) > r(P3 ) > r(P4 ) > r(P6 ). R Poznamenejme, ˇze v´ ypoˇcet je proveden v programu Matlab 8.1.0.604 (R2013a) R

TM na poˇc´ıtaˇci Dell Latitude 6430U s procesorem Intel Core i7-3687U, 2.10 GHz R s 8.00 GB RAM a se 64 bitov´ ym operaˇcn´ım systémem Windows 7 Professional, SP1.

66

0

P

P1

1

0.3

P2 P

PageRank

P

4

0.2

P

0.15

P6

5

poøadí stránky

3

0.25

1

P2

2

P3

3

P5

5

0.05

6

5

10 iterace

15

7 0

20

P

6

4

0.1

0 0

P4

5

10 iterace

15

0

P

P1

0.3

P2

1

P2

0.25

P3

2

P3

0.2

P5

3

P

0.15

P6

P4

poøadí stránky

PageRank

1

5

0.05

6

5

10 iterace

15

7 0

20

0.25

P3

0.2

P5

0.15

P6

P4

20

20

P P

2

P

3

P

4

P5

4

P6

6

15

15

3

0.05 10 iterace

10 iterace

2

5

5

5

1

0.1

0 0

6

1 poøadí stránky

P2

5

P

0

P1 0.3

P4

4

0.1

0 0

PageRank

20

7 0

5

10 iterace

15

20

Obrázek A.1: Konvergence PageRank vektoru internetu z obrázku 1.1. Googlovská matice G = αH + (1 − α)E, kde matice hyperlink˚ u H je (1.8) a α = 1 (teleportaˇcn´ı matice E se tedy v´ ypoˇctu ne´ uˇcastn´ı). Vlevo v´ yvoj jednotliv´ ych PageRank˚ u, vpravo v´ yvoj poˇrad´ı stránek. V jednotliv´ ych ˇradách byla mocninná metoda nastartována, 1 T 1 1 1 1 1 odshora, vektorem 6 [1, 1, 1, 1, 1, 1] , 2 [ 5 , 5 , 5 , 5 , 1, 15 ]T , resp. 21 [ 15 , 51 , 15 , 15 , 51 , 1]T . Vektor je normalizován tak, aby souˇcet prvk˚ u byl roven jedné. Vykresleno je prvn´ıch dvacet iterac´ı. Vypoˇctené PageRanky jsou r(P5 ) > r(P1 ) > r(P3 ) > r(P2 ) ≈ r(P4 ) > r(P6 ).

67

0

P

P1

0.3

P2

1

P2

0.25

P3

2

P3

0.2

P

3

P5

0.15

P6

P

4 5

poøadí stránky

PageRank

1

5

0.05

6

5

10 iterace

15

7 0

20

0.25

P3

0.2

P5

0.15

P6

P4

0.25

P3

0.2

P5

0.15

P6

P4

20

10 iterace

15

20

P P

2

P

3

P

4

P5 P

6

4

6

15

5

3

0.05 10 iterace

6

2

5

5

P

1

0.1

0 0

P5

1 poøadí stránky

PageRank

P2

3

P

0

P1 0.3

2

P

4

7 0

20

P

4

6

15

20

P

3

0.05 10 iterace

15

2

5

5

10 iterace

1

0.1

0 0

5

1 poøadí stránky

PageRank

P2

6

0

P1 0.3

P

4

0.1

0 0

P4

7 0

5

10 iterace

15

20

Obrázek A.2: Konvergence PageRank vektoru internetu z obrázku 1.1. Googlovská matice G = αH +(1−α)E, kde matice hyperlink˚ u H je (1.8) a α = 0.9, 0.6, resp. 0.3, v jednotliv´ ych ˇradách. Vlevo v´ yvoj jednotliv´ ych PageRank˚ u, vpravo v´ yvoj poˇrad´ı 1 T stránek. Mocninná metoda byla nastartována vektorem 6 [1, 1, 1, 1, 1, 1] . Vektor je normalizován tak, aby souˇcet prvk˚ u byl roven jedné. Vykresleno je prvn´ıch dvacet iterac´ı. Pro velká α se vypoˇctené poˇrad´ı stránek P2 a P4 zjednoznaˇcn´ı tak, ˇze r(P5 ) > r(P1 ) > r(P3 ) > r(P2 ) > r(P4 ) > r(P6 ). Pro malá α (tj. pˇri velkém vlivu teleportace) se zmenˇsuj´ı rozd´ıly mezi PageRanky. Nav´ıc dojde k zámˇenˇe poˇrad´ı stránek P3 a P2 na r(P5 ) > r(P1 ) > r(P2 ) > r(P3 ) > r(P4 ) > r(P6 ).

68

Literatura [1] A. Berman, R. J. Plemmons: Nonnegative matrices in the mathematical sciences, SIAM Publications, Philadelphia, 1994. [2] M. W. Berry, M. Browne: Understanding search engines. Mathematical modeling and text retrieval, 2nd ed., SIAM Publications, Philadelphia, 2005. [3] S. Brin, L. Page: The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems 30(1–7) (1998), str. 107–117. [4] S. Brin, R. Motwani, L. Page, T. Winograd: What can you do with a Web in your pocket?, Data Engineering Bulletin 21(2) (1998), str. 37–47. [5] S. Brin, R. Motwani, L. Page, T. Winograd: The PageRank citation ranking: Bringing order to the Web, Technical Report 1999-0120, Computer Science Department, Stanford University, Stanford, 1999. [6] R. A. Brualdi, H. J. Ryser: Combinatorial matrix theory, Cambridge University Press (edice Encyclopedia of Mathematics and its Applications, vol. 39), Cambridge, 1991 (reprint 2003). [7] D. Cvektović, P. Rowlinson, S. Simić: Eigenspaces of graphs, Cambridge University Press (edice Encyclopedia of Mathematics and its Applications, vol. 66), Cambridge, 1997 (reprint 2004). ˇ ık, V. Doleˇzal, M. Fiedler: Kombinatorikcá analýza v praxi, SNTL, Státn´ı [8] K. Cul´ nakladatelstv´ı technické literatury, Praha, 1967. [9] J. Demel: Grafy a jejich aplikace, Academia, Praha 2002. ˇ [10] J. Demel: Grafy, SNTL, Státn´ı nakladatelstv´ı technické literatury (edice MVST, Matematika pro vysoké ˇskoly technické, seˇsit XXXIV), Praha, 1988, resp. 1989 (dotisk). [11] J. Duintjer Tebbens, I. Hnˇetynková, M. Pleˇsinger, Z. Strakoˇs, P. Tich´ y: Analýza metod pro maticové výpoˇcty. Základn´ı metody, Matfyzpress, Praha, 2012. [12] M. Fiedler: Speciáln´ı matice a jejich pouˇzit´ı v numerické matematice, SNTL, Státn´ı nakladatelstv´ı technické literatury (edice TKI, Teoretická kniˇznice inˇzen´ yra), Praha, 1981.

69

[13] F. R. Gantmaqer: Teori matric, Izdatel~stvo Nauka, Moskva, 1966. [14] F. R. Gantmacher: The theory of matrices, AMS Chelsea Publishing, Providence, 1998. [15] G. H. Golub, C. F. Van Loan: Matrix computations (ˇctvrté vydán´ı), The Johns Hopkins University Press, Baltimore, 2013. [16] G. Chartrand: Introductory graph theory, Dover Publications, New York, 1985. [17] A. N. Langville, C. D. Meyer: Google’s PageRank and beyond. The science of search engine rankings, Princeton University Press, Princeton, 2006. [18] L. Maixner: Makovovy procesy a jejich aplikace, Univerzita Palackého v Olomouci, Olomouc, 1991. [19] J. Matouˇsek, J. Neˇsetˇril: Kapitoly z diskrétn´ı matematiky, Karolinum, Praha, 2009. [20] J. Neˇsetˇril: Teorie graf˚ u, SNTL, Státn´ı nakladatelstv´ı technické literatury (edice MS, Matematick´ y semináˇr, ˇc. 13), Praha, 1979. ´ [21] J. Sedláˇcek: Kombinatorika v teorii a praxi. Uvod do teorie graf˚ u, Academia (edice CV, Cesta k vˇedˇen´ı, ˇc. 7), Praha, 1964. ´ [22] J. Sedláˇcek: Uvod do teorie gra˚ u, Academia (edice CV, Cesta k vˇedˇen´ı, ˇc. 25, resp. 29), Praha, 1977 (2. vydán´ı), resp. 1981 (3. vydán´ı). [23] L. Unˇconvsk´ y: Stochastické modely operaˇcnej analýzy, Alfa/SNTL, Bratislava, 1980. [24] J. Vran´ y: Lokalizace algoritm˚ u pro ˇrazen´ı výsledk˚ u vyhledáván´ı informac´ı na webu, Disertaˇcn´ı práce, TU v Liberci, Liberec, 2009.

70

Google PageRank: Relevance webových

Recommend Documents