UNIVERSIDADE FEDERAL DE SANTA MARIACENTRO DE CIÊNCIAS NATURIAS E EXATAS

MATEMÁTICA BACHARELADO

CADEIAS DE MARKOV E APLICAÇÕES

TRABALHO DE GRADUAÇÃO

Fernanda Alves Lamberti

Santa Maria, RS, Brasil

2015

CADEIAS DE MARKOV E APLICAÇÕES

Fernanda Alves Lamberti

Trabalho de Graduação apresentado ao Curso de Matemática Bacharelado da

Universidade Federal de Santa Maria (UFSM, RS), como requisito parcial para

a obtenção do grau de

Bcharelado-Matemática

Orientador: Professor Dr. João Roberto Lazzarin

Santa Maria, RS, Brasil

2015

Universidade Federal de Santa MariaCentro de Ciências Naturias e Exatas

Matemática Bacharelado

A Comissão Examinadora, abaixo assinada,

aprova o Trabalho de Graduação

CADEIAS DE MARKOV E APLICAÇÕES

elaborado por

Fernanda Alves Lamberti

como requisito parcial para obtenção do grau de

Bcharelado-Matemática

COMISSÃO EXAMINADORA:

João Roberto Lazzarin, Dr.

(Presidente/Orientador)

Lidiane Buligon, Dra. (CCNE-UFSM)

Karine Faverzani Magnago, Dra. (CCNE-UFSM)

Santa Maria, 03 de Dezembro de 2015.

AGRADECIMENTOS

Agradeço à todos que de alguma forma contribuiram para meu crescimento. Ao meu

orientador João Lazzarin, por ter aceito participar deste trabalho. Aos meus pais, Hellen e

Gercimar, por terem me ajudado nos melhores e piores momentos. Ao meu irmão, Lucas, por

estar ao meu lado e por toda a ajuda. Ao meu noivo, Jaldecir, por ter me apoiado e pelas

muitas palavras de insentivo nos momentos que pensei em desistir. À todos estes, o meu muito

obrigado. Este trabalho só foi possível por vocês.

RESUMO

Trabalho de Graduação

Matemática Bacharelado

Universidade Federal de Santa Maria

CADEIAS DE MARKOV E APLICAÇÕES

AUTORA: FERNANDA ALVES LAMBERTI

ORIENTADOR: JOÃO ROBERTO LAZZARIN

Local da Defesa e Data: Santa Maria, 03 de Dezembro de 2015.

Atualmente a internet tem feito parte do dia-a-dia da maioria das pessoas. Ferramentas

simples como as da Álgebra Linear podem contribuir muito no uso de sites de busca. As Ca-

deias de Markov são exemplos disso. Com algumas definições importantes e alguns teoremas

podemos formar uma base para um algoritmo de grande utilizade, o PageRank.

Palavras-chave: Cadeias de Markov. Álgebra Linear. PageRank.

ABSTRACT

Undergraduate Final Work

Graduate Program in Mathematics

Federal University of Santa Maria

CHAIN MARKOV AND APPLICATIONS

AUTHOR: FERNANDA ALVES LAMBERTI

ADVISOR: JOÃO ROBERTO LAZZARIN

Defense Place and Date: Santa Maria, December 03st, 2015.

Today the internet has been part of day-to-day life of most people . Simple tools such

as the linear algebra can go a long way in the use of search engines . The Markov chains are

examples. With some important definitions and some theorems we can form a basis for a big

plus algorithm, PageRank.

Keywords: Markov chain, linear algebra, PageRank.

SUMÁRIO

1 PRÉ-REQUISITOS E DEFINIÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.1 Autovalores e Autovetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 PROCESSOS ESTOCÁSTICOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 PROCESSOS MARKOVIANOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 CADEIAS DE MARKOV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 MATRIZES DE TRANSIÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.6 CADEIAS DE MARKOV REGULARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6.1 CONVERGÊNCIA DE UMA MATRIZ DE TRANSIÇÃO . . . . . . . . . . . . . . . . . . . . . . . . 14

2 O QUE É A MÉTRICA PAGERANK E COMO FUNCIONA . . . . . . . . . . . . . . . . . . . . . . 17

2.0.2 Fator de amortecimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.0.3 Cálculo interativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.0.4 Ilustrando o método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1 Casos em que o método pode não dar certo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.1.1 Caso 1: Rede simples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.1.2 Caso 2: Ciclo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.1.3 Caso 3: Páginas sem ligação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

8

1 PRÉ-REQUISITOS E DEFINIÇÕES

Neste capítulo iremos apresentar alguns dos conceitos necessários para entender o algo-

ritmo PageRank, iniciaremos com as definições de Processos Estocásticos, Cadeias de Markov

e resultados de convergência de matrizes, como citado anteriormente, é necessário um conheci-

mento básico de matrizes, probabilidade e conjuntos.

Não entraremos em detalhes no que seja probabilidade, porém, em termos informais, a

probabilidade de um experimento ou de uma observação produzir um certo resultado é apro-

ximadamente a fração de vezes durante a qual esse resultado ocorreria se o experimento fosse

repetido muitas vezes sob condições constantes; quanto maior o número de repetições, mais

preciso ficará esse valor. Também usaremos o termo evento de modo informal, que servirá para

indicar todo fenômeno que pode ser observado e analisado seus possíveis resultados, exemplos

destes fenômenos podem ser atirar uma moeda (podemos observar se cairá cara ou coroa), jo-

gar um dado de seis faces e observar qual ficará virada para cima, a quantidade de produtos em

uma loja, o número de alunos de uma sala de aula e , no nosso caso, a chance de partindo de

clicks aleatórios, chegar a um determinado site. Também usaremos livremente o termo vetor-

probabilidade para toda matriz-linha em que a soma de todos elementos desta linha tem soma

igual a 1.

1.1 Autovalores e Autovetores

Lembremos da Álgebra Linear que toda matriz quadrada An×n satifaz a seguinte igual-

dade

9

XA = XIλ Onde Xn×1 é chamado de autovetor e λ é chamado de autovalor.

1.2 PROCESSOS ESTOCÁSTICOS

Um Processo Estocástico é qualquer evento que varia aleatoriamente com o passar do

tempo, chamamos a variável correspondente ao tempo de t e o valor associado ao evento no

tempo t de x(t) (para mais detalhes ver (3) ).

Exemplo 1.2.1 Consideremos t o período em semanas, e x(t) a quantidade de produtos no es-

toque de uma loja, ao findar de cada período. Se no início da observação temos 14 produtos no

estoque, ao passar de uma semana temos 19, ao passar da segunda semana temos 22, podemos

fazer a seguinte associação:

t(semanas) 0 1 2

x(t)(peças) 14 19 22

Quando os valores de x(t) se encontram em um conjunto enumerável ou finito, dizemos

que o evento tem estado discreto, portanto nosso Processo Estocástico tem estado discreto, caso

contrário, dizemos ter estado contínuo.

Exemplo 1.2.2 Conseidere x(t) o número de alunos na disciplina de TCC I a cada ano, em

uma determinada Universidade. Notemos que se trata de um estado discreto (quando se refere

ao número de pessoas se usa os números naturais, logo se trata de um conjunto enumerável) e

tempo discreto (o número de anos também se dá por números naturais). Tomando por t0 = 0

o ano de 2010, se no ano de 2010 a turma tinha 15 alunos, ao passar de um ano aumentou 5

alunos, no ano seguinte diminuiu 3, no próximo, 2013, 2 alunos a mais que no ano anterior, e

10

nos próximos 2 anos, a turma aumentou 1 aluno a cada ano. Portanto temos

t(anos) 0 1 2 3 4

x(t)(pessoas) 15 20 17 19 20

Exemplo 1.2.3 Em uma viagem entre Santa Maria e Porto Alegre, supondo que t esteja repre-

sentado em horas, analisando a velocidade x(t), obtemos os seguintes valores:

t(h) 1, 5 2, 4 3, 1 4

x(t)(km) 60 66, 33 54 73

Note que os valores de t encontram-se em um subconjunto finito dos números reais positivos,

pois a viagem terá um tempo definido e os valores de x(t) também, desde que a velocidade de

um carro é limitada. Portanto, podemos dizer que nosso Processo Estocástico apresenta estado

e tempo discretos.

1.3 PROCESSOS MARKOVIANOS

Um Processo se diz Markoviano (em homenagem a Andrei Andrevevich Markov) quando

o estado futuro depende apenas do estado anterior, ou seja, os estados passados não exercem

influência alguma. Processos deste tipo são chamados de processos sem memória (memory-

less process). As probabilidades condicionais representam a probabilidade do estado x(tk + 1)

ser xk+1 no instante tk + 1, dado que o estado x(tk) é xk em tk ((6), 2009). Por exemplo, se

no tempo t = 1, o estado é A e no tempo t = 2, o estado é A + 3, denotamos x(1) = A e

x(2) = A + 3, poderíamos deduzir que x(t) = x(t − 1) + 3 e assim x(t) depende apenas do

estado anterior, o que nos leva a um processo sem memória, isto é, a um Processo Markoviano.

Exemplo 1.3.1 A quantidade de um determinado produto no estoque de uma loja, ao fim de

cada dia, sabendo que são vendidos 50 produtos por dia e adquiridos 66 produtos por dia é um

11

Processo Markoviano, pois a quantidade de produtos depende apenas da quantidade anterior

e do que foi adquirido ou vendido nesse intervalo de tempo.

1.4 CADEIAS DE MARKOV

Processo Markoviano é dito uma Cadeia de Markov quando o estado é discreto ((6),

2009).

Exemplo 1.4.1 Saldo (em reais) de uma conta no banco, de uma determinada pessoa num

período de tempo em semanas é uma Cadeia de Markov, pois o estado é discreto (valores

em reais são enumeráveis). Por exemplo, na semana 1 temos R$500, 00 de saldo em conta.

Na semana 2 tivemos um aumento de R$100, 00 ao saldo anterior. Na semana 3 temos uma

redução de R$175, 00. E assim podemos dizer que

t(semanas) 1 2 3

x(t)(reais) 500 600 425

Exemplo 1.4.2 Seja x(t) = 12x(t − 1) a função que descreve os valores de x no tempo t, e

x(0) = x0 ∈ N. Notemos que x(t) descreve uma Cadeia de Markov, pois é um evento que varia

conforme o tempo, só depende do estado anterior, e tem estado discreto.

1.5 MATRIZES DE TRANSIÇÃO

Consideremos um vetor-probabilidade num processo estocástico que é denotado por

x(t) =[x1(t) x2(t) · · · xn(t)

]

12

em que xi(t) é a probabilidade com que o sistema esteja no estado i no instante t, para i =

1, 2, ..., n. Vale lembrar quen∑i=1

xi(t) = 1.

Uma Matriz de Transição é uma matriz quadrada de ordem Pn×n = (pij) onde cada pij

é a probabilidade de que haja uma transição do estado i para o estado j ((6), 2009). No caso das

Cadeias de Markov, quando o evento varia do estado i para o estado j, num determinado tempo

t. A cada cadeia de Markov, podemos associar uma matriz de transição P conforme vemos no

próximo exemplo.

Exemplo 1.5.1 Numa determinada loja temos três produtos a venda do mesmo setor, a cada

período de uma semana podemos notar que 50% dos compradores continuam comprando o

mesmo produto. Dos que compravam o produto 1, 20% passam a comprar o produto 2 e 30%

o produto 3. Dos que compravam o produto 2, 10% passam a comprar o produto 1 e 40%

passam a comprar o produto 3. E dos que compravam o produto 3, 30% passam a comprar o

produto 1 e 20% passam a comprar o produto 2. Podemos notar que é uma Cadeia de Markov,

pois o estado futuro depende do estado anterior, que o estado é discreto, pois a quantidade de

valores é finita, já que vamos observar uma quantidade finita de clientes. Podemos descrever tal

evento utilizando uma matriz (aij)3×3, onde aij representa a probabilidade de um comprador

do produto i trocar para o produto j. Assim

P =

0, 5 0, 3 0, 2

0, 1 0, 5 0, 4

0, 3 0, 2 0, 5

Analisando 50 compradores destes produtos, vemos que, inicialmente, 20 compravam o produto

1, 15 compravam o produto 2, e 15 o produto 3. Para saber a quantidade de clientes que

13

compram cada produto fazemos a multiplicação da matriz com a quantidade de compradores

inicialmente pela matriz de transição montada acima:

[20 15 15

]0, 5 0, 3 0, 2

0, 1 0, 5 0, 4

0, 3 0, 2 0, 5

=[

16 16, 5 17, 5].

Temos então, em média, 16 compradores do produto 1, 16, 5 compradores do produto 2 e 17, 5

compradores do produto 3, depois de uma semana.

1.6 CADEIAS DE MARKOV REGULARES

Uma Cadeia de Markov ou sua matriz de transição P é dita ser regular se existir uma

potência inteira positiva n tal que P n tenha todas as entradas positivas ((8), 2010).

Exemplo 1.6.1 a matriz

0, 1 0, 7 0, 2

0, 3 0, 05 0, 65

0, 6 0, 05 0, 35

tem todas as entradas positivas para qualquer

n, logo é uma matriz de transição regular.

Exemplo 1.6.2 Considere a matriz A =

0, 3 0, 2 0 0, 5

0 0, 3 0, 3 0, 4

0, 6 0 0 0, 4

0, 4 0, 3 0 0, 3

.

Temos que A2 =

0, 29 0, 27 0, 06 0, 38

0, 34 0, 21 0, 09 0, 36

0, 34 0, 24 0 0, 42

0, 24 0, 26 0, 09 0, 41

e A3 =

0, 275 0, 253 0, 081 0, 391

0, 3 0, 239 0, 063 0, 398

0, 27 0, 266 0, 072 0, 392

0, 29 0, 249 0, 078 0, 383

.Note que A e A2 tem entradas iguais a zero, porém A3 já não apresenta entradas nulas,

portanto, desde que a soma dos elementos das linhas de A resulta em 1, temos que A é uma

matriz de transição regular.

14

1.6.1 CONVERGÊNCIA DE UMA MATRIZ DE TRANSIÇÃO

Nosso ojetivo é provar uma versão Markoviana do teorema de Perron-Frobenius (ver

referência (5)), antes porém, precisamos fixar algumas notações e resultados.

Para a prova do Teorema precisaremos do seguinte resultado auxiliar:

Lema 1.6.3 Seja M uma matriz de transição de uma cadeia de Markov, e x = (xi) ∈ Rn.

Se y = xM , entãon∑i=1

yi ≤n∑i=1

xi . Se a matriz M tiver todas as entradas positivas e duas

coordenadas xi 6= 0 e xj 6= 0 tais que xixj/∈ R+, então a desigualdade é estrita.

Demonstração 1.6.4 observemos quen∑j=1

|yj| =n∑j=1

|x1a1j + x2a2j + · · ·+ xnanj|

≤n∑j=1

|x1| a1j + |x2| a2j + · · ·+ |xn| anj = |x1|(

n∑k=1

ak1

)+ · · ·+ |xn|

(n∑k=1

akn

),

considerando que cada

(n∑k=j

akj

)= 1 para j = 1, 2, ..., n temos

n∑j=1

|yj| ≤n∑i=1

|xi|

Além disso, a desigualdade será estrita quando houver sinais trocados entre os termos xi dis-

tintos e não nulos como afirma o restante da hipótese.

Teorema 1.6.5 (i) (Teorema de Perron-Frobenius, caso Markoviano) Seja M uma matriz de

transição de uma cadeia de Markov, então

(i) Se λ é autovalor de M , então |λ| ≤ 1;

(ii) λ = 1 é autovalor de M .

Demonstração 1.6.6 (i)Seja u = (u1, u2, ..., un) 6= 0 um autovetor qualquer de M , com au-

tovalor associado λ. isto é, uM = λu assim, Pelo Lema acima, |λ|∑|ui| ≤

∑|ui|, o que

15

implica que |λ| ≤ 1.

(ii) Lembrando que a soma de cada uma das linhas da matriz de transição vale 1, segue-se que[1 1 · · · 1

]M = 1

[1 1 · · · 1

], o que prova o resultado afirmado.

Teorema 1.6.7 Se P é uma matriz de transição de uma cadeia de Markov regular, então:

(i) Existe um único vetor-probabilidade q tal que q.P = q;

(ii) Para qualquer vetor-probabilidade inicial x0 , a sequência de vetores de estado

x0, x0P, ..., x0Pk tende a q como um limite, ou seja, x0P k→ q quando k →∞. (O vetor

q é chamado de vetor de estado estacionário). ((5), 2011 ou (4)).

Demonstração 1.6.8 A existência de q está garantida pelo Teorema anterior. A unicidade será

mostrada depois. Vamos mostrar que x0P k → q quando k →∞.

Como a cadeia é regular, existe r natural tal que P r tem todas as entradas positivas, ou

seja, prij > 0, para todo i, j..

Para 0 < δ < 1 temos que P rij > δq. Agora, seja ε = 1− δ e Π a matriz quadrada cujas

linhas sejam iguais a q e considere a matriz Q tal que P r = (1− ε)Π + εQ.

Note que MΠ = Π e ΠP = Π, assim, aplicando plicando o princípio de indução sobre

k, temos que

P kr = (1− εk)Π + εkQk.

Multiplicando a igualdade acima por P j para j ∈ N, temos

P kr+j = (1− εk)ΠP j + εkQkP j.

16

Mas ΠP = Π e portanto ΠP j = Π, logo

P kr+j = (1− εk)Π + εkQkP j

ou

P kr+j − Π = −εkΠ + εkQkP j

ou ainda mais,

P kr+j − Π = εk(QkP j − Π

)lembrando que ||A|| = supx∈Rn||x|| = 1, temos que

∣∣∣∣P kr+j − Π∣∣∣∣ = εk

∣∣∣∣QkP j − Π∣∣∣∣ ≤ εk,

agora, fazendo k → ∞ obtemos que P kr+j → q. Nos falta provar a unicidade de q, para isso

basta supor que exista um q1tal que q1P = q1,fazendo q1P k, pelo fato de q1P k = q teremos

então que q = q1.

Exemplo 1.6.9 A matriz de transição P de uma determinada cadeia de Markov é

0, 8 0, 2

0, 9 0, 1

.Como as entradas são positivas temos que a cadeias de Markov é regular e, portanto, tem um

único vetor de estado estacionário q. Então segundo o Teorema, para encontrarmos q ob-

servamos que qP = q ⇔ 0 = q − qP ⇔ q(I − P ) = 0, daí temos o seguinte sistema

−0, 2q1 + 0, 9q2 = 0 que resulta em q1 = 4, 5q2. Como queremos que q seja um vetor probabi-

lidade, temos ainda que 1 = q1 + q2 daí segue que q1 = 0, 82 e q2 = 0, 18.

17

2 O QUE É A MÉTRICA PAGERANK E COMO FUNCIONA

Neste capítulo iresmos apresentar como funcuina o algoritmo PageRank, dar um exem-

plo com um número razoável de páginas e mostrar os casos onde o algoritmo não funciona

muito bem.

A métrica apresenta a probabilidade de chegarmos a um determinado link clicando em

links aleatórios, tal cálculo é feito através de iterações, que se observarmos as condições do Te-

orema 1.6.5, podemos obter um vetor-probabilidade que fornecerá os valores de PageRank que

buscamos. Nosso próximo passo e estabelecer a matriz de transição de uma cadeia Markoviana

obtida estabelecendo vetores-probabilidades em cada iteração que fornece o PageRank (índice

que estabelece a importância deste site dentro da rede em que ele pertence) de vários sites que

estejam lincados entre si.

2.0.2 Fator de amortecimento

Além das conexões entre os sites de uma rede, muitas vezes é considerado o fato do

navegador não utilizar as ligações entre os sites, pensando assim, leva-se em consideração um

fator de amortecimento, que denotaremos por d, e que fornece a probabilidade do navegador se-

guir as ligações, portanto 1−d será então a probabilidade do navegador não utilizar as ligações.

O fator de amortecimento leva em consideração os seguintes pontos:

1. Uma página tem uma probabilidade de ser acessada por uma escolha aleatória pelo sim-

ples fato de existir;

2. Uma página isolada que não é indicada por nenhuma outra e indica todas as outras páginas

18

existentes na rede;

3. outros fatores.

Levando em consideração os fatos listados, em geral utiliza-se o valor d = 0, 85 para o

fator de amortecimento. Notemos que se o fator de amortecimento a ser considerado for muito

pequeno, então a estrutura de links não tem muita força, ou seja, ela não nos mostra realmente

quem é o mais ou menos importante.

Consideraremos os seguinte caso ideal: uma rede com N páginas, sendo elas

P1, P2, P3, ..., PN , onde cada Pi indica ao menos uma outra página Pj. Denotaremos por R o

vetor-probabilidade que representa o valor de PageRank de cada uma das páginas num instante

t, isto é

R =[PR(P1) PR(P2) · · · PR(PN)

](a notação PR vem de PageRank).

Com o fator de amortecimento, o cálculo do valor de PageRank foi estabelecido por seus

idealizadores pela seguinte fórmula:

PR(Pi) =1− dN

+ d

(n∑j=1

PR(Pj)δijL(Pj)

). (2.1)

onde L(Pj) é o número de ligações que saem da página j e

δij =

0 se Pi não é indica o Pj;

1 se Pi indica o Pj.

(ver (9)).

A fórmula 2.1 fornece a seguinte interpretação matricial:

19

R =[PR(P1) PR(P2) · · · PR(PN)

]=

[1−dN

+ d

(n∑j=1

PR(Pj)δijL(Pj)

)1−dN

+ d

(n∑j=1

PR(Pj)δijL(Pj)

)· · · 1−d

N+ d

(n∑j=1

PR(Pj)δijL(Pj)

) ]

que portanto, utilizando a matriz (de transição)MN×N = (mij), ondeN é o número de páginas

e mij = l(Pi, Pj) =δijL(Pi)

definida por:

l(Pi, Pj) =

0, se nao existe referência da pag i para pag j;1

L(Pi), se existe referência da pag i para j,

onde L(Pi) é o número de ligações que saem da página i. Portanto, R pode ser obtido pela

fórmula

R =[

1−dN· · · 1−d

N

]+ dR

l(P1, P1) l(P1, P2) · · · l(P1, PN)

l(P2, P1) l(P2, P2) · · · l(P2, PN)...

... . . . ...

l(PN , P1) l(PN , P2) · · · l(PN , PN)

Se substituirmos por U = [1, 1, ...1] o vetor com U em todas as colunas então pela

igualdade acima temos:

R = dRM +1− dN

U

Sabendo que a soma dos valores de cada linha de R é 1, se tomarmos E como sendo a matriz

N×N com 1 em todas as entradas, obtemosRE = U e assim rescrevemos a expressão anterior

como

R = dRM +1− dN

RE

ou

R = R

(dM +

1− dN

E

).

20

Segue-se que R é o autovetor associado ao autovalor autovalor 1da matriz M definida por

M = dM +1− dN

E.

Para ver que de fato M é uma matriz de transição devemos observar que a soma de uma linha k

desta matriz será

N∑j=1

(dl(Pk, Pj) +

1− dN

)= (1− d) + d

N∑j=1

l(Pk, Pj) = (1− d) + d = 1.

2.0.3 Cálculo interativo

Em geral, R é calculado utilizando-se o Teorema 1.6.5, estudando-se a convergência

da seguinte cadeia Markoviana: chamando de x(0) o vetor-probabilidade que contém os valores

de PR(X) iniciais de cada página e de x(t) este mesmo vetor-probabilidade na iteração t,

podemos calcular x(t+ 1) multiplicando x(t) pela matriz pela matriz M . Ou seja

x(t+ 1) = x(t)M

Teremos então

x(1) = x(0)M

x(2) = x(0)M2

x(t+ 1) = x(0)M t+1

Notando que a matriz M segue as exigências do Teorema 1.6.5 afinal M é uma matriz regular

de transição, pois pij são todos não-nulos e a soma de cada linha é 1, então podemos concluir

que x(t) converge para o vetor R procurado quando t→∞.

21

Não discutiremos a velocidade de convergência, no entanto o processo em geral não

é demorado e com um número relativamente pequeno de iteração temos um valor bastante

aproximado de R.

2.0.4 Ilustrando o método

Nesta seção vamos considerar uma mini internet com 5 sites denotados respectivamente

por A,B,C,D e E e cujas ligações estão ilustradas na Figura 2.1 abaixo:

Figura 2.1:

Fonte: O autor

podemos montar a matriz M , como definida anteriormente,

M =

0 13

0 13

13

14

0 14

14

14

12

12

0 0 0

15

15

15

15

15

13

0 13

13

0

22

Utilizando d = 0, 85, temos então que

M = 0, 85

0 13

0 13

13

14

0 14

14

14

12

12

0 0 0

15

15

15

15

15

13

0 13

13

0

+

1− 0, 85

5

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

que fornece

M =

0, 03 0, 3133 0, 03 0, 3133 0, 3133

0, 2425 0, 03 0, 2425 0, 2425 0, 2425

0, 455 0, 455 0, 03 0, 03 0, 03

0, 2 0, 2 0, 2 0, 2 0, 2

0, 3133 0, 03 0, 3133 0, 3133 0, 03

Utilizando o software matemático MATLAB para fazer as sucessivas multiplicações

podemos notar que calculando a nona e decima iteração obtemos

0.03 0.313 33 0.03 0.313 33 0.313 33

0.242 5 0.03 0.242 5 0.242 5 0.242 5

0.455 0.455 0.03 0.03 0.03

0.2 0.2 0.2 0.2 0.2

0.313 33 0.03 0.313 33 0.313 33 0.03

9

=

0.230 72 0.202 82 0.161 92 0.227 33 0.177 17

0.230 76 0.202 82 0.161 95 0.227 32 0.177 12

0.230 77 0.202 92 0.161 89 0.227 28 0.177 1

0.230 75 0.202 83 0.161 94 0.227 32 0.177 13

0.230 78 0.202 84 0.161 95 0.227 3 0.177 09

e

23

0.03 0.313 33 0.03 0.313 33 0.313 33

0.242 5 0.03 0.242 5 0.242 5 0.242 5

0.455 0.455 0.03 0.03 0.03

0.2 0.2 0.2 0.2 0.2

0.313 33 0.03 0.313 33 0.313 33 0.03

10

=

0.230 76 0.202 83 0.161 94 0.227 31 0.177 11

0.230 75 0.202 85 0.161 93 0.227 31 0.177 12

0.230 74 0.202 82 0.161 94 0.227 32 0.177 14

0.230 76 0.202 85 0.161 93 0.227 31 0.177 12

0.230 75 0.202 85 0.161 92 0.227 31 0.177 13

donde observamos que

0.03 0.313 33 0.03 0.313 33 0.313 33

0.242 5 0.03 0.242 5 0.242 5 0.242 5

0.455 0.455 0.03 0.03 0.03

0.2 0.2 0.2 0.2 0.2

0.313 33 0.03 0.313 33 0.313 33 0.03

9

−

0.03 0.313 33 0.03 0.313 33 0.313 33

0.242 5 0.03 0.242 5 0.242 5 0.242 5

0.455 0.455 0.03 0.03 0.03

0.2 0.2 0.2 0.2 0.2

0.313 33 0.03 0.313 33 0.313 33 0.03

10

=

−4. 40× 10−5 −8. 23× 10−6 −1. 84× 10−5 1. 60× 10−5 5. 87× 10−5

2. 71× 10−6 −3. 37× 10−5 2. 44× 10−5 1. 31× 10−5 −2. 49× 10−6

3. 39× 10−5 9. 88× 10−5 −4. 56× 10−5 −4. 36 × 10−5 −3. 95× 10−5

−4. 79× 10−6 −2. 00× 10−5 1. 12× 10−5 1. 00× 10−5 7. 60× 10−6

3. 46× 10−5 −1. 06× 10−5 2. 70× 10−5 −3. 70× 10−6 −4. 32× 10−5

o que mostra que o método convergiu e se pode usar com boa margem de segurança M9 para

se obter R. Assim tomando vetor-probabilidade inicial (consideramos que o PageRank de cada

24

site são inicialmente iguais):

R0 =[

15

15

15

15

15

]temos que

R0M9 =

[0, 2307 0, 2028 0, 1619 0, 2272 0, 1777

]Portanto, se fossemos classificar os sites quanto sua importância, teríamos a seguinte

ordem crescente de importância: A;D;B;E e C.

2.1 Casos em que o método pode não dar certo

Vale lembrar que na vida real as coisas não são tão simples, por exemplo se um nave-

gante buscar por assuntos pertinentes a matemática, ele poderá esbarar nos seguintes fatores

que dificultarão a classificação:

1. O número muito grande de sites na internet;

2. Quando buscamos sobre matemática, não podemos levar tanto em consideração os sites

sobre futebol, por exemplo, que possuem links que levam a sites relacionados à matemá-

tica.

3. Fatores publicitários e distratores que podem levar o navegador a se "embrenhar"em sites

que não eram de interesse e nem possuem alguma ligação com a matemática.

Porém, nada disso tira a importância do mecanismo de classificação descrito acima e

que ainda é largamente utilizado pela Google. Além disso, existem casos que o método geral

25

visto na seção acima não funciona bem mesmo em redes pequenas. Relataremos abaixo cada

um destes casos.

2.1.1 Caso 1: Rede simples.

Na Figura 2.2 abaixo, temos uma pequena rede com 4 sites (A, B, C e D), cada um vai

iniciar com o valor de 14, ou seja, todos tem inicialmente a mesma importância:

Figura 2.2:

Fonte: O autor

Num segundo passo, como vemos na Figura 2.2, cada ligação transfere 0,25 para o

PageRank de A, daí,

PR(A) = PR(B) + PR(C) + PR(D)

podemos associar a este sistema a seguinte matriz de transição M e sua respectiva M : M =

26

0 0 0 0

1 0 0 0

1 0 0 0

1 0 0 0

e M = 0.85

0 0 0 0

1 0 0 0

1 0 0 0

1 0 0 0

+ 1−0.855

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

=

0.03 0.03 0.03 0.03

0.88 0.03 0.03 0.03

0.88 0.03 0.03 0.03

0.88 0.03 0.03 0.03

que de fato não é uma matriz de transição (as somas dos elementos

de cada linha não dá 1), o que não garante a convergência do método, Aliás M10 ≈ 0 fazendo

com que o vetor-probabilidade nivele a zero a importância de todos os sites.

Um outro modelo desta mesma situação pode ser visto na Figura 2.3, vemos pelas liga-

ções existentes na figura, que o valor de B é transferido metade para A e metade para C. O valor

de C é transferido para A e o de D, um terço para A, um terço para B e um terço para C. assim,

PR(A) =PR(B)

2+PR(C)

1+PR(D)

3,

mesmo assim, M apresentará uma linha nula, fazendo com que a convergência não seja garan-

tida pelo Teorema 1.6.2.

Outro problema que o algoritmo encontra é quando a rede é em forma de ciclo, como

mostra a Figura 2.3 (fenômeno chamado rank sink).

2.1.2 Caso 2: Ciclo

27

Figura 2.3:

Fonte: O autor

Neste caso M =

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

e

M = 0.85

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

+ 1−0.855

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

=

0.03 0.88 0.03 0.03

0.03 0.03 0.88 0.03

0.03 0.03 0.03 0.88

0.88 0.03 0.03 0.03

é

tal que

[1 1 1 1

]

0.03 0.88 0.03 0.03

0.03 0.03 0.88 0.03

0.03 0.03 0.03 0.88

0.88 0.03 0.03 0.03

10

=

[0.737 42 0.737 42 0.737 42 0.737 42

]Notemos que o problema, neste caso, se encontra

no fato de todos os valores finais serem iguais, ou seja, todos apresentam a mesma importância,

e não tem como formarmos uma ordem para exibi-los.

2.1.3 Caso 3: Páginas sem ligação

Figura 2.4:

Fonte: O autor

O algoritmo também encontra problemas quando uma página é isolada das outras. Como

mostra a Figura 2.4:

Nesta pequena Rede com apenas 2 site teremos a matriz associada M =

0 1

0 0

e

M = 0.85

0 1

0 0

+ 1−0.855

1 1

1 1

=

0.03 0.88

0.03 0.03

que também não é uma matriz de

transição pois suas linhas não são vetores-probabilidades.

29

3 CONCLUSÃO

A importância do trabalho vem do fato de termos utilizado apenas ferramentas simples,

como os conceitos de Álgebra Linear e Probabilidade para explorar uma área que não é apre-

sentada ao longo do curso de graduação e que nos leva a um algoritmo de grande importância

nos dias atuais.

Na elaboração do trabalho foi necessária a utilização de um software matemático para

obtermos resultados mais rápidos e precisos, tanto no desenvolvimento dos exemplos apresen-

tados quanto para explorarmos os resultados que utilizamos até sua total compreensão. O que

foi um desafio de grande aproveitamento.

Como os sites de busca são ferramentas muito utilizadas nos dias atuais, o algoritmo

pode ser visto como indispensável, pois se fossemos fazer uma busca na internet onde os re-

sultados são apresentados de forma aleatória passaríamos horas até encontrarmos uma página

realmente relevante. Ou seja, podemos perceber que conceitos simples podem nos gerar muitos

benefícios, o que nos faz acreditar que ainda podemos ter muitas outras contribuições como

esta.

30

REFERÊNCIAS

(1) BOLDRINI, J. L.; COSTA, S.I.R.; RIBEIRO, V. L.,WETZLER, H.G., Álgebra Linear,

Harper-Row, São Paulo; 1986.

(2) GERHARDT, M. L. Descobrindo a pesquisa no ensino médio. Santa Maria: UFSM, 2013.

(3) GOLMAKANI, et al. Cadeias de Markov. Maceió: [s.n.], 2014.

(4) HOWARD, A; RORRES, C. Álgebra linear com aplicações, 8 ed. Rio de Janeiro: Bookman„

2002.

(5) MALAJOLVICH,G., Álgebra Linear. Rio de Janeiro, [s.n.], 2010.

(6) NOGUEIRA, F. Modelagem e simulação cadeias de Markov. [Juiz de fora]: [s.n.], 2009.

Notas de aula.

(7) PEDROSO. C.M. Modelagem e avaliação de desempenho. Paraná:[s.n.], 2011.

(8) PORILHO, D. F.; VARGAS. V. Conceitos e simulação de cadeias de Markov. Goiás: [s.n.],

2010.

(9) WIKIPÉDIA. PageRank. Disponível em: http://pt.wikipedia.org/wiki/PageRank. Acesso

em 20 de maio de 2015.