bc1414 Passeio aleatório em grafos

Seja G=(V,E) um grafo finito e conexo. O leitor não familiarizado com as nomenclaturas elementares da Teoria dos Grafos pode consultar estas notas.

Um passeio aleatório em {G} é uma sequência {v_0,v_1,v_2,\dots} de vértices de {V} de modo que {v_{i+1}} é escolhido uniformemente em {N(v_i)=\{u\in V\colon \{u,v_i\}\in E\}}, a vizinhança de {v_i}, para todo {i\in{\mathbb N}}. Dizendo de outro modo, é uma cadeia de Markov {\{X_t\}_{t\geq 0}} homogênea com {V} como conjunto de estados e

\displaystyle p_{v,u}= \mathop{\mathbb P} ( X_{t+1}=u~|~X_t=v) = \frac 1{d(v)}

para todo {u\in N(v)} e todo {t\in {\mathbb N}}, onde {d(v)=|N(v)|} é o {grau do vértice} {v}.

Se {A=A(G)} é a matriz de adjacências de {G}, isto é {A=(a_{v,u})} com {a_{v,u}\in\{0,1\}} e {a_{v,u}=1} sse e só se {\{v,u\}} é aresta, e {D=(d_{u,v})} é a matriz diagonal {d_{v,v}=1/d(v)} então a matriz de transições do passeio aleatório em G é

\displaystyle P= A D.

Exemplo 129 Seja {G} o grafo sobre o conjunto de vértice {\{1,2,\dots,n\}} com todas as {\binom n2} arestas, chamado de grafo completo, e consideremos um passeio aleatório em {G}, assim

\displaystyle p_{v,u} = \frac 1{n-1}

e a matriz de transição é {P=\frac 1{n-1}A}.

Nesse caso, o número esperado de passos para atingir {v} a partir de {u} é {n-1}. De fato, a probabilidade de atingir {v} em 1 passo é {f_{u,v}^{(1)}=1/(n-1)}, a probabilidade de atingir {v} em 2 passos é {f_{u,v}^{(2)}=(n-2)/(n-1)^2}, em 3 passos {f_{u,v}^{(3)}=(n-2)^2/(n-1)^3}, e assim por diante.

O número esperado de passos é

\displaystyle \sum_k k f_{u,v}^{(k)}= \sum_{k\geq 1} k \frac 1{n-1} \left( \frac{n-2}{n-1}\right)^{k-1}= \frac 1{n-1} \frac 1{\left( 1-\frac{n-2}{n-1}\right)^2} = n-1.

O número esperado de passos para visitar todos os vértices do grafo pode ser estimado da seguinte forma. Seja {t_i} o instante em que pela primeira vez temos exatamente {i} vértices visitados, portanto, {t_{i+1} - t_{i}} é uma variável aleatória geométrica que conta o número de passos enquanto espera-se para conhecer um novo vértice, evento que ocorre com probabilidade {(n-i)/(n-1)}, logo {\mathop{\mathbb E} \big( t_{i+1} - t_{i} \big) = (n-1)/(n-i)} e {t_n} é o número de passos até visitar todos os vértices

\displaystyle \mathop{\mathbb E} (t_n) =\sum_{i=1}^{n-1}\mathop{\mathbb E}(t_{i+1} - t_{i}) =\sum_{i=1}^{n-1}\frac{n-1}{n-i} =(n-1)\sum_{i=1}^{n-1}\frac{1}{i} =(n-1)H_{n-1}

onde {H_{n}} denota o {n}-ésimo número harmônico, {H_n= \sum_{i=1}^n 1/i = \ln n+\gamma +\Theta(n^{-1})}, onde {\gamma\approx 0,577} é a constante de Euler–Mascheroni.

Um passeio aleatório num grafo conexo é uma cadeia de Markov irredutível e em certos casos aperiódica. O próximo resultado caracteriza tais passeios aleatórios aperiódicos.

Teorema 22 Se {G} é conexo com pelo menos dois vértices então um passeio aleatório em {G} define uma cadeia de Markov irredutível. Ainda, tal cadeia de Markov é periódica se e só se {G} é bipartido.

Demonstração: Se {G} é conexo então para dois vértices {u} e {v} quaisquer que estão a distância {k} vale {p_{u,v}^{(k)}>0}. Como {G} é conexo a distância entre quaisquer dois vértices é algum {k\in{\mathbb N}}, portanto a cadeia de Markov definida pelo passeio aleatório é irredutível.

Seja {G} um grafo conexo e bipartido com bipartição {\{A,B\}}. Então, todos os passeios de {u} para {v} têm a mesma paridade no número de arestas, para o caso {u,v\in A} ou {u,v\in B} e ímpar caso {u\in A} e {v\in B} ou {v\in A} e {u\in B}. Logo

  • se {u,v\in A} ou {u,v\in B} então {p_{u,v}^{(k)}>0} exceto quando {k} é ímpar,
  • se {u\in A} e {v\in B}, ou {v\in A} e {u\in B}, então {p_{u,v}^{(k)}>0} exceto quando {k} é par.

Portanto a cadeia tem período {2}.

Agora, suponhamos G não-bipartido, então contém um circuito de comprimento ímpar C. Tomemos P um passeio de u a v, vértices que distam k em G, com o menor número de arestas. Um passeio de u para v com k+2r arestas existe para todo r\in\mathbb N, basta repetir r vezes alguma aresta do passeio P. Como G é conexo existe um passeio de algum vértice de P até algum vértice de C, portanto, podemos usar as arestas de C para obter passeios de u para v que têm a paridade oposta a de k. Logo, p_{u,v}^{(t)} >0 para todo t suficientemente grande, ou seja, a cadeia é aperiódica. \Box

Corolario 23 Se {G=(V,E)} é conexo, não-bipartido e com pelo menos dois vértices então a cadeia de Markov dada por um passeio aleatório em {G} admite um vetor estacionário. Ademais, a distribuição estacionária é única e dada por

\displaystyle \mathbf{\pi} =(\pi_v)_{v\in V}, \textrm{ com } \pi_v =\frac{d(v)}{2|E|}. \ \ \ \ \ (65)

 

Demonstração: A cadeia é irredutível e aperiódica, portanto admite um único vetor estacionário pelo teorema 20. Agora, basta verificar que (65) é estacionário.

A soma dos graus dos vértices de um grafo é {2|E|}, logo {\sum_{v\in V}\pi_v = 1}. Resta verificar que {\mathbf{\pi}=\mathbf{\pi}P}, onde {P} é a matriz de transição, mas

\displaystyle (\mathbf{\pi}P)_v = \sum_{u\in V} \pi_u p_{u,v} = \sum_{u\in N(v)} \frac{d(u)}{2|E|} \frac 1{d(u)}= \sum_{u\in N(v)} \frac{1}{2|E|} = \frac{d(v)}{2|E|} = \pi_v

portanto, o vetor dado em (65) é o vetor estacionário. \Box

Observação 10 Se {G=(V,E)} é bipartido então podemos contornar essa propriedade indesejada (no sentido do corolário acima) acrescentando laços aos vértices do grafo com probabilidade de transição {1/2} (ou seja, {p_{v,v}=1/2}) e dividir por 2 a probabilidade das outras arestas, ou seja, se {P} é a matriz de transição da cadeia no grafo original, a nova matriz de transição é

\displaystyle Q= \frac{P+Id}{2}

onde {Id} é a matriz identidade {|V|\times |V|}. Essa transformação apenas “reduz a velocidade” do passeio.

Exemplo 130 De volta ao grafo completo {G} do exemplo 129, vamos usar a estratégia de acrescentar laço e o número esperado de passos até um passeio aleatório passar por todos os vértices de {G}. Seja {P} a matriz de transição da cadeia de Markov do passeio em {G} e consideremos a modificação acima, acrescentando um laço em cada vértice ficamos com a matriz de transição do novo passeio

\displaystyle Q=\frac{P+Id}2.

Seja {T} o número de passos para o passeio definido por {Q} visitar todos os vértice e {q_i = (n-i)/n} a probabilidade de visitar um vértice novo se outros {i} vértices já foram visitados, então o número esperado de passos até o passeio visitar o {i+1}-ésimo vértice é {1/q_i}. Assim,

\displaystyle \mathop{\mathbb E} (T) = \sum_{i=1}^{n} \frac ni = n H_n.

{s-t} conexidade em grafos

O problema da {s-t} conexidade em grafos é: dado um grafo {G=(V,E)} e dois vértices {s,t} em {G} decidir se há um passeio entre esses dois vértices. Esse problema pode ser resolvido em tempo linear no tamanho do grafo, {|V|+|E|}, e usando espaço {\Omega(|V|)}.

A pergunta que interessa nesse caso é se o problema pode ser resolvido usando espaço logarítmico. Essa pergunta foi respondida afirmativamente em [Reingold, Undirected connectivity in log-space, J. ACM 58, 2008], até então o único progresso significativo foi o algoritmo aleatorizado que apresentaremos a seguir devido a [Aleliunas, Karp, Lipton, Lovasz, Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, SFCS ’79].

Notemos que o espaço extra gasto pelo algoritmo é para manter o vértice atual e o contador de rodadas para o laço, portanto, o espaço utilizado é {O(\log n)} para um grafo com {n} vértices.

Se o algoritmo devolve sim então o grafo contém um passeio entre os vértices {s} e {t}. Agora, se o algoritmo responde não, então ou não há caminho, ou o algoritmo não foi capaz de encontrá-lo em tempo. Portanto, se não existe caminho a resposta está correta, caso contrário a resposta pode estar errada e vamos limitar a probabilidade de erro.

Seja {T} o tempo para um passeio aleatório no grafo {G} visitar todos os vértices de {G}. O tempo de cobertura de {G} (cover time) é

\displaystyle \max_{v\in V(G)} \mathop{\mathbb E}(T~|~X_0=v).

Lema 24 O tempo de cobertura de um grafo {G=(V,E)} conexo é no máximo {4|V||E|}.

Demonstração: Tomemos um subgrafo acíclico maximal de {G=(V,E)} (ou, uma árvore geradora) e consideremos um passeio {W=v_0,v_1,\dots,v_{2|V|-2}=v_0} nas |V|-1 arestas dessa árvore de modo que cada aresta seja percorrida exatamente duas vezes, uma vez em cada direção. O tempo de cobertura de {G} é limitado superiormente pelo tempo esperado para um passeio percorrer a sequência {W} que é

{\displaystyle \sum_{i=0}^{2|V|-3} \mathbb{E}( T_{v_{i+1}}~|~X_0=v_i) < (2|V|-2)(2|E|) <  4|V||E|}

pois { \mathop{\mathbb E}( T_{v_{i+1}}~|~X_0=v_i) < 2|E|} para toda aresta {\{v_i,v_{i+1}\}} em {G}. De fato, , calculando \mu_{v} de dois modos distintos

\displaystyle \frac{2|E|}{d(v)} = \frac{1}{\pi_v}=\mu_{v}=\sum_{u\in N(v)}\frac{1+ \mathop{\mathbb E}(T_{v}~|~X_0=u)}{d(u)}

portanto, {2|E| = \sum_{u\in N(v)}\big(1+ \mathop{\mathbb E}(T_{v}~|~X_0=u)\big)}. \Box

Com isso conseguimos estimar a probabilidade de erro da seguinte maneira. Seja {G} um grafo e {s} e {t} dois vértices de {G} que são ligados por um passeio. O algoritmo erra se em {n^4} rodadas não consegue achar um {s-t} caminho em {G}. Denotemos por {C(G)} o tempo de cobertura de {G}

\displaystyle \mathop{\mathbb P} \big( \mathrm{erro} \big) = \sum_{k>n^4} f_{s,t}^{(k)} \leq \frac{\mathop{\mathbb E}(T_{t}~|~X_0=s) }{n^4}

pela desigualdade de Markov, logo

\displaystyle \mathop{\mathbb P} \big( \mathrm{erro} \big) \leq \frac {C(G)}{n^4} \leq \frac{4n|E|}{n^4} < \frac 4n.

— Passeio aleatório em grafos regulares —

Um grafo é regular se todos os vértices têm o mesmo grau. Nesse caso temos um bom tanto de informação que podemos retirar da matriz de transição que é duplamente estocástica (veja o exercício 103). A começar, que essa matriz é simétrica, portanto, todos os seus autovalores são reais, ademais, o Teorema Espectral garante a existência de uma família ortonormal de autovetores, tantos quanto é a dimensão da matriz. Um passeio aleatório num grafo regular converge para a distribuição uniforme (exercício 103) e nesta seção mostraremos que a velocidade dessa convergência é ditada pelo segundo maior autovalor da matriz de transição.

Um grafo {G=(V,E)} é {d}-regular, {d\in{\mathbb N}}, se todos os vértice de {V} têm grau {d}. No que segue, vamos assumir que todo grafo é sobre {V=\{1,2,\dots,n\}}, é conexo e {d}-regular.

Nesse caso, a matriz de transição de um passeio em {G} é

\displaystyle P= \frac 1d A

, para {A=A(G)} a martiz de adjacências. A matriz {P} é simétrica, portanto, seus autovalores são reais. Sejam

\displaystyle \lambda_1 \geq \lambda_2 \geq \cdots\geq \lambda_n \ \ \ \ \ (66)

 

os autovalores de {P}. Do Teorema de Perron–Frobenius temos que se {G} é conexo então

  • {\lambda_1 > \lambda_2};
  • {\lambda_1 =-\lambda_n} se e somente se {G} é bipartido.

Não é difícil constatar que o vetor {\mathbf{\pi}} com todas as coordenadas iguais a {1/|V|} é um autovetor de {P} associado ao autovalor {1}, ou seja, {P\pi = 1\pi} e como {P} é simétrica

\displaystyle \mathbf{\pi} = \mathbf{\pi} P

que, em outras palavras, quer dizer que a distribuição uniforme sobre {V} é a distribuição estacionária do passeio aleatório em {G}.

Ainda, se {k} é tal que {|\pi_k| = \max_v |\pi_v|} então

\displaystyle |\lambda_1 \pi_k| = \left|\sum_{v=1}^n \pi_v p_{v,k}\right| \leq \sum_{v=1}^n |\pi_v| |p_{v,k}| \leq |\pi_k|\sum_{v=1}^n |p_{v,k}| = |\pi_k|

ou seja, {\lambda_1 \leq 1}, portanto {\lambda_1=1}.

Seja {G} um grafo conexo, não-bipartido, {d}-regular e com {n} vértices. Fixemos

\displaystyle \lambda = \max\big\{|\lambda_2|, |\lambda_n|\big\} \ \ \ \ \ (67)

 

e {\varrho =\varrho^{(0)}} uma distribuição inicial sobre {V}, seja {\varrho^{(t)}} a distribuição de probabilidade sobre os vértices de {G} no instante {t\in{\mathbb N}}. Vamos mostrar que {\varrho{p}^{(t)}} converge para {\pi} com velocidade controlada por {\lambda}.

Seja {\xi_i}, {1\leq i\leq n}, uma base ortonormal de autovetores de {P}, de modo que {\xi_i} é autovetor associado a {\lambda_i}. Notemos que {\xi_1 = \sqrt{n} \pi }. Se {\varrho = a_1\xi_1 +\cdots+a_n\xi_n} então { \varrho^{(t)} = p P^t = a_1\mathbf{v}_1P^t +\cdots+a_n\mathbf{v}_nP^t = a_1\lambda_1^t\xi_1 +\cdots+a_n\lambda_n^t\xi_n } e

\displaystyle \Vert\varrho^{(t)} - a_1\xi_1\Vert_2^2= \left( a_1{\lambda_1}^t-a_1\right)^2 +\sum_{i>1}(a_i{\lambda_i}^t)^2 \leq \lambda^{2t}\sum_{i>1}a_i^2 \leq \lambda^{2t}\Vert\varrho^{(0)}\Vert_2^2

donde segue que

\displaystyle \Vert\varrho^{(t)} - a_1\xi_1\Vert_2 \leq {\lambda}^{t}\Vert\varrho^{(0)}\Vert_2 \leq {\lambda}^{t}\Vert\varrho^{(0)}\Vert_1 = {\lambda}^{t}

e como {\lambda < 1} temos {\varrho^{(t)}} converge para {a_1\xi_1} quando {t\rightarrow\infty}, logo {a_1\xi_1} é igual a {\pi}, pelo teorema 20.

Com isso, provamos

Lema 25 Sejam {G} um grafo com {n} vértices, conexo, {d}-regular e não-bipartido, {P=A(G)/d} a matriz de transição de um passeio aleatório em {G} e

\displaystyle \lambda = \max \big\{|\alpha|\colon \alpha \textrm{ \'e autovalor de }P\textrm{ e } \alpha<1 \big\}

Então para todo vetor de probabilidades {\varrho} e todo {t\in{\mathbb N}}

\displaystyle \Vert \varrho^{(t)} - \mathbf{\pi} \Vert_2 \leq {\lambda}^t

onde {\mathbf{\pi}=(1/n,1/n,\dots,1/n)} é o vetor estacionário do passeio aleatório.

Exercício 108 Seja {\rho = (p_1,\dots,p_n)\in{\mathbb R}^n} um vetor, então {\Vert\rho \Vert_\infty} é uma norma dada por

\displaystyle \Vert\rho \Vert_\infty = \max\big\{|p_i|\colon 1\leq i\leq n\big\}.

Prove que { \Vert\rho \Vert_\infty \leq \Vert\rho \Vert_2} para todo {\rho \in{\mathbb R}^n}.

Teorema 26 Seja {\{X_t\}_{t\in N}} um passeio aleatório num grafo {G} com {n} vértices, conexo, {d}-regular e não-bipartido e com segundo maior autovalor {\lambda}. Então, para todo {\delta >0} existe {k = k(\lambda,\delta)} tal que

\displaystyle \left| \mathop{\mathbb P} (X_k=v) -\frac 1n \right| < \delta

para todo vértice {v}.

Demonstração: Seja {G} como no enunciado. Vamos mostrar que

\displaystyle \Vert\varrho A^k - \pi \Vert_\infty = \left|\mathop{\mathbb P}(X_k=v) -\frac 1n \right| < \delta.

Seja {\varrho=\varrho^{(0)}} uma distribuição inicial qualquer, então a distribuição de {X_k} é dada pelo vetor {\varrho P^k},

\displaystyle \mathop{\mathbb P}(X_k=v) = (\varrho P^k)_v

em que {P} é a matriz de transição do passeio aleatório.

Pelo lema 25 e exercício acima

\displaystyle \Vert\varrho A^k - \mathbf{\pi}\Vert_\infty \leq \Vert\varrho A^k - \mathbf{\pi}\Vert_2 \leq \lambda^{k+1}

portanto, se {k> \log_{\lambda}(\delta/\lambda)} então {\Vert\varrho A^k - \mathbf{\pi}\Vert_\infty < \delta}. \Box

Exercício 109 Verifique se vale o resultado anterior para {G} bipartido, conexo e {d}-regular com o passeio aleatório dado por {Q=(P+\mathrm{Id})/2}, onde {P=A(G)/d}.

Exercício 110 Sejam {G} um grafo com {n} vértices, conexo, {d}-regular e {\mu_1 \geq \mu_2\geq \cdots \geq \mu_n} os autovalores da matriz de adjacências de {G}. Consideremos as matrizes estocásticas {P=A(G)/d} e {Q=(P+\mathrm{Id})/2} cujos autovalores são, respectivamente, {\lambda_1\geq \lambda_2\geq \cdots, \lambda_n} e {\nu_1\geq \nu_2\geq \cdots \geq \nu_n}. Prove que

\displaystyle \lambda_i =\frac{\mu_i}d = 2\nu_i-1

para todo inteiro {1\leq i\leq n}.

Exercício 111 Sejam {G} um grafo com {n} vértices, {m} arestas e {\mu_1 \geq \mu_2\geq \cdots \geq \mu_n} os autovalores da matriz de adjacências de {G}. Prove que

\displaystyle \sum_{i=1}^n \mu_i^2 = 2m. \ \ \ \ \ (68)

 

(Segestão: {\sum_i \mu_i^2} e a soma da diagonal princial da matriz {A^2} e {A} é diagonalizável.)

— Passeios aleatórios em grafos expansores —

Da discussão anterior podemos concluir que quanto menor for o segundo autovalor de um grafo, que passamos a denotar por {\mu}, mais rápido um passeio aleatório converge para a distribuição uniforme, entretanto {\mu} não pode ser arbitrariamente pequeno. De (68) temos

\displaystyle (n-1)\mu^2 + \mu_1^2 \geq 2m

portanto, no caso {d}-regular {\mu = \Omega (\sqrt{d})}.

No que segue, {G^n} é um grafo com {n} vértices, conexo e {d}-regular para {d} fixo. Dizemos que {G^n} é um grafo {\epsilon}-expansor se {\mu \leq d-\epsilon}.

Seja {W} um subconjunto de vértices de {G^n}. Denotamos por {N(W)} o subconjunto dos vértices de {V\setminus W} que são adjacente a algum vértice de {W}. Dizemos que {G} é {c}-vértice expansor separa todo {W} com {|W| \leq n/2} vale que {|N(W)| \geq c |W|}, daí vem o expansor. Essas definições são equivalentes no seguinte sentido: se {G^n} é {\epsilon}-expansor então é {\epsilon/(2d)}-vértice-expansor. Por outro lado, se {G^n} é {c}-vértice-expansor então é {c^2/(4+2c^2)}-expansor. Logo, grafos expansores são caracterizados combinatorialmente por possuir alta conexidade, que é equivalente a dizer que a distância espectral (diferença {d-\mu} entre os dois maiores autovalores da matriz de adjacências do grafo) é grande.

Grafo expansores esparsos são objetos aparentemente contraditórios, mas a existência desses grafos segue de métodos probabilísticos usuais, como mostrou Pinsker em 1973 que quase todo grafo {d}-regular, {d\geq 3}, é expansor. Embora abundantes, a construção explícita desses grafos não é simples; de fato, em geral a construção mas a prova da expansão usa ferramentas profundas e complexas da matemática. Sortear um grafo e testar se é expansor é inviável, o sorteio usa muitos bits aleatórios (uma das principais aplicações desses grafos que veremos aqui é o uso para economizar bits aleatórios em algoritmos aleatorizados) e o problema de decisão está em {\mathtt{coNP}}.

No que segue vamos assumir a possibilidade de construir explicitamente grafos expansores tais que dados um vértice {x} e {i\in\{1,2,\dots,d\}} o vértice {v_i(x)} pode ser determinado em espaço logarítmico. Para as construções explícitas o leitor pode consultar este documento O nosso interesse é no uso desses grafos para desaleatorização em BPP que segue a seguinte estratégia. Suponha que temos um algoritmo que decide {L\in\mathtt{BPP}} com probabilidade de erro menor que {\epsilon} usando {n} bits aleatórios para entradas de tamanho fixo. Então, podemos construir um algoritmo que decide a mesma linguagem com probabilidade de erro menor que {\epsilon^k} usando {kn} bits tomando {k} rodadas independentes do algoritmo. Agora, suponha que temos um grafo expansor 3-regular {2^n} vértices. Um gerador pseudoaleatório consiste em determinar um vértice desse grafo uniformemente, de modo que temos os {n} bits aleatórios necessários para uma rodada do algoritmo. Para determinar um desses vértices usamos o lema 25, que diz que é suficiente começamos um passeio aleatório de comprimento {\approx n}, cada passo do passeio precisa de 2 bits genuinamente aleatórios. Como o algoritmo é executado {k} vezes, o número de bits aleatórios usados é {O(n+k)}.

Antes de expormos formalmente a idéia acima chamamo a atenção para um resultado conhecido estreitamente relacionado com os resultados discutidos nessa seção.

Expander mixing lemma

É sabido que se {X,~Y\subseteq V(G^n)} então a distribuição de arestas entre {X} e {Y} em {G^n} satisfaz

\displaystyle \big| |E(X,Y)| -\frac dn |X||Y|\big| \leq \mu \sqrt{|X||Y|} \ \ \ \ \ (69)

 

Esboço de demonstração: Seja {\xi_i}, {1\leq i\leq n}, uma base ortonormal de autovetores de {A}. Sejam {\mathbf{x}} e {\mathbf{y}} os vetores (linha) característicos de {X} e {Y}, respectivamente. Então {|E(X,Y)|= \mathbf{x}A\mathbf{y}^\mathtt{T}}, onde {\mathtt{T}} denota o transposto. Escrevendo na base de autovetores {|E(X,Y)|= \sum_i \mu_i\alpha_i\beta_i}, onde {\alpha_i} e {\beta_i} são os produtos escalares {\langle \mathbf{x},\xi_i\rangle} e {\langle \mathbf{y},\xi_i\rangle}, respectivamente. O resultado segue de {\sum_i \mu_i\alpha_i\beta_i = d|X||Y|/n + \sum_{i\neq 1} \mu_i\alpha_i\beta_i.} \Box

Portanto, {\lambda } pequeno garante um distribuição de arestas como num grafo aleatório com densidade de arestas {d/n}. Grafos com {\lambda} pequeno são ditos pseudoaleatórios . Linial e Bilu provaram uma recíproca desse resultado, se 69 vale para algum {\mu>0} então segundo maior autovalor de {A(G)} é {O(\mu \log(d/\mu))}.

De (69) temos

\displaystyle \left| \frac{|E(X,Y)|}{nd} - \frac {|X||Y|}{n^2} \right| \leq \frac{ \mu}{d} \ \ \ \ \ (70)

ou seja, a probabilidade de sortear um par de vértices e cair em {X\times Y} é próxima a probabilidade de sortear uma aresta e cair em {E(X,Y)}. Escrevendo de ouro modo, consideremos a vizinhança de cada vértice de {G} indexada por {\{1,2,\dots,d\}} e denotemos por {v_i(x)} o {i}-ésimo vizinho do vértice {x} de acordo com essa indexação. Assim, a equação (69) pode ser interpretada como

\displaystyle \Big| \mathop{\mathbb P}_{(x,i)\in_\mathrm{R}V\times [d]}\big( [x\in X]\cap [v_i(x)\in Y]\big) - \mathop{\mathbb P}_{(x,y)\in_\mathrm{R}X\times Y}\big([x\in X]\cap[y\in Y]) \Big| \leq \frac {\mu}d.

— Passeio aleatório na Web: O Google Page Rank

To test the utility of PageRank for search, we built a web search engine called Google” Page, Brin, Motwani, Winograd, The PageRank Citation Ranking: Bringing Order to the Web.

O grafo web é um grafo dirigido definido pelas páginas web e as ligações (links ou hyperlinks) entre as páginas. Conhecer a estrutura desse grafo é importante para o desenvolvimento de algoritmos eficientes para a web, por exemplo.

Um marco no projeto e desenvolvimento desses algoritmos é o algoritmo PageRank [Page, Brin, Motwani, Winograd, The PageRank Citation Ranking: Bringing Order to the Web] desenvolvido como parte da ferramenta de busca na web batizada Google pelos fundadores da empresa com mesmo nome.

O PageRank é um algoritmo para classificação (ranking) de páginas na web. A idéia que o motivou é modelar a importância relativa de uma página de modo que uma busca resulte em resultados com relevância. A própria empresa explica a idéia da seguinte maneira:

“O coração do nosso software é o PageRank(TM), um sistema para dar notas para páginas na web, desenvolvido pelos nossos fundadores Larry Page e Sergey Brin na Universidade de Stanford. E enquanto nós temos dúzias de engenheiros trabalhando para melhorar todos os aspectos do Google no dia a dia, PageRank continua a ser a base para todas nossas ferramentas de busca na web.
Explicações sobre o PageRank

A classificação das páginas (PageRank) confia na natureza excepcionalmente democrática da Web, usando sua vasta estrutura de links como um indicador do valor de uma página individual. Essencialmente, o Google interpreta um link da página A para a página B como um voto da página A para a página B. Mas o Google olha além do volume de votos, ou links, que uma página recebe; analisa também a página que dá o voto. Os votos dados por páginas “importantes” pesam mais e ajudam a tornar outras páginas “importantes.””

(http://www.google.com.br/why_use.html)

Assim, uma página tem uma classificação alta se é referenciada por páginas com classificação alta.

O que nos interessa no momento é que o modelo adotado no PageRank pode ser interpretado como um passeio aleatório no grafo web: um internauta absorto, começa a navegar na web a partir de uma página qualquer, e segue a navegação por um dos links da página atual escolhido uniformemente; depois de muito tempo nessa tarefa as páginas começam a repetir e o internauta entediado pára o processo e recomeça-o a partir de alguma outra página.

O modelo simplificado do PageRank é descrito da seguinte maneira. Seja {G=(V,E)} o grafo da web, ou seja, {V} é o conjuntos formado pelas páginas web, as quais serão consideradas sem perda de generalidade {\{1,2,\dots,n\}=V}, e {(a,b)\in E} se na página {a} há um link para a página {b}. Denotamos por {N^+(a)} o conjunto dos vértices {b} tais que {(a,b)} é uma aresta de {G}, e por {N^-(a)} denotamos o conjunto dos vértices {b} tais que {(b,a)} é uma aresta de {G}. No grafo web da figura 0 {|N^+(3)|=2} e {|N^-(3)|=3}.

A classificação é dada por um vetor {\mathbf{r}} onde {r_a} é a classificação da página {a} e satisfaz

\displaystyle r_a = \sum_{b\in N^-(a)} \frac {r_b}{|N^+(b)|} \ \ \ \ \ (73)

 

ou seja, se {b} aponta para {a} então {b} contribui com {1/{|N^+(b)|}} de sua relevância para a relevância de {a}. Seja {P} a matriz

\displaystyle p_{a,b} = \begin{cases} \frac 1 {|N^+(a)|}&\textrm{ se }(a,b)\textrm{ \'e aresta}\\ 0&\textrm{ caso contr\'ario,} \end{cases}

então de (73)

\displaystyle \mathbf{r} = \mathbf{r}P

ou seja, {\mathbf{r}} é um autovetor à esquerda de {P}. No grafo web da figura 0 está descrita a matriz de transição {P} para aquele grafo.

Se {P} for uma matriz estocástica então o vetor {\mathbf{r}} é um vetor estacionário e dessa forma, {\mathbf{r}} pode ser calculado escolhendo uma distribuição inicial {\mathbf{r}^{(0)}} e fazendo { \mathbf{r}^{(k+1)} = \mathbf{r}^{(k)}P}. Como vimos, sob certas hipóteses { \mathbf{r}^{(k)}} converge para {\mathbf{r}}. Esse método, conhecido como método das potências, é usado há muito tempo para calcular autovetores associado ao maior autovalor. Entretanto, na atual situação não sabemos se o vetor converge pois não temos garantia que a matriz {P} seja irredutível (garante {\lambda_1 > \lambda_2}, portanto convergência) ou estocástica (garante o autovalor {\lambda_1=1}, portanto o método converge para o vetor estacionário).

Exemplo 131 Por exemplo, para

\displaystyle P= \begin{pmatrix} 0&0\\1&0 \end{pmatrix}

e {\mathbf{r}^{(0)}=(0,1)} temos {\mathbf{r}^{(2)} = \mathbf{r} = (0,0)}, No caso de um circuito dirigido, um vetor inicial pode não convergir.

No exemplo da figura 0 abaixo a matriz {P} não é estocástica.

Os vértices sem arestas que saem, ou seja os vértices {v} tais que {|N^+(v)|=0} são chamados de pendentes (dangling) e por causa deles a matriz não é estocástica. No exemplo da figura 0 o vértice {6} é pendente. Na web de fato há vários vértices pendentes, por exemplo, os documentos em pdf disponíveis em páginas web são vértices pendentes do grafo.

Seja {n} o número de vértices em {G}. Definimos uma matriz auxiliar {A} pondo para cada vértice pendente {a}, o que corresponde a uma página sem links, a linha {a} com entradas {1/n} e tomamos

\displaystyle Q= P+A

isso significa que um passeio aleatório que chega numa página sem saída continua em qualquer outra página com igual probabilidade.

A matriz {Q} é estocástica. A matriz {Q} referente a matriz {P} da figura 0 é dada a seguir na figura 0 ao lado do grafo web que corresponde à modificação no grafo que reflete a modificação na matriz {P}. No grafo da figura 0 as arestas tracejadas são as arestas incluídas e correspondem à possibilidade de navegação do internauta que chega a uma página sem saída e recomeça a navegação de qualquer lugar uniformemente.

No exemplo dado na figura 0, o maior autovalor da matriz {Q} é {1} com multiplicidade {1} e autovetor associado {(1,1,1,0,0,0)}. Notemos que os vértices {4,~5,~6} tem classificação {0}. Isso decorre do fato de não haver aresta que sai de {\{1,2,3\}} e chega em qualquer outro vértice diferente desses. Esse conjunto é chamado de sorvedouro (rank sink).

Para lidar com esses sorvedouros basta garantir que a matriz seja irredutível pois se {p_{a,b}^{(k)}>0} para algum {k}, para todo {a,~b\in V} então não há sorvedouros no grafo. Para garantir uma matriz irredutível (em linguagem de Teoria dos Grafos, o grafo dirigido tem que ser fortemente conexo, caso contrário o vetor estacionário pode ter todas as coordenadas nulas fora de uma componente fortemente conexa do grafo.) tomamos {p\in (0,1)} e consideramos um passeio aleatório que segue as transições de {Q} com probabilidade {p} ou que com probabilidade {1-p} vai pra qualquer outra página web (como o comportamento do internauta absorto que ficou entediado), ou seja,

\displaystyle R = pQ + (1-p)\frac 1n\mathbf{1} \ \ \ \ \ (74)

 

onde {\mathbf{1} } é a matriz com todas as entradas iguais a {1}. A matriz obtida de {Q} do exemplo da figura~0

\displaystyle R=\begin{pmatrix} \frac{1-p}{6} & \frac{p}{2}+\frac{1-p}{6} & \frac{p}{2}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6}\cr \frac{p}{2}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{p}{2}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6}\cr \frac{p}{2}+\frac{1-p}{6} & \frac{p}{2}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6} & \frac{1-p}{6}\cr \frac{1-p}{6} & \frac{1-p}{6} & \frac{p}{3}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{p}{3}+\frac{1-p}{6} & \frac{p}{3}+\frac{1-p}{6}\cr \frac{1-p}{6} & \frac{p}{3}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{p}{3}+\frac{1-p}{6} & \frac{1-p}{6} & \frac{p}{3}+\frac{1-p}{6}\cr \frac{p}{6}+\frac{1-p}{6} & \frac{p}{6}+\frac{1-p}{6} & \frac{p}{6}+\frac{1-p}{6} & \frac{p}{6}+\frac{1-p}{6} & \frac{p}{6}+\frac{1-p}{6} & \frac{p}{6}+\frac{1-p}{6} \end{pmatrix}

É sabido que o método iterativo para computar o vetor estacionário descrito, o método das potências, converge com velocidade {|\lambda_2/\lambda_1|} onde {\lambda_1>\lambda_2} são os dois maiores autovalores da matriz {R}. Ainda, é sabido que {\lambda_1=1} e que {|\lambda_2| \leq p}. O parâmetro {p} é conhecido como fator de amortecimento (damping factor). No trabalho que originou o algoritmo os autores do PageRank estabeleceram o valor {p=0,85} após testes. Atualmente, a Google não divulga o valor desse fator. No mesmo trabalho , os autores reportam de 50 a 100 iterações do método das potências até a condição de parada do método das potências. 0 critério tradicional de parada é da forma {\Vert \mathbf{p}^{(t+1)} - \mathbf{p}^{(t)}\Vert_2 < \epsilon} para uma tolerância {\epsilon>0} pequena; notemos que não é necessário conhecer as grandezas do vetor estacionário, só é preciso determinar a ordem das coordenadas, o que pode ser usado para diminuir o número de iterações. Para {p=0,85} foi reportado que com 29 iterações {\Vert\mathbf{\pi}^{k+1} - \mathbf{\pi}^k \Vert_2< 10^{-2}}, e no caso de 50 a 100 iterações a tolerância é de {10^{-3}} a {10^{-7}}.

Para concluirmos esta seção vão mostrar uma alternativa para escrever essa matriz, uma vez que atordoantes 1 trilhão de páginas indexadas foi reportado pela Google em julho de 2008 . A matriz {P} é esparsa pela natureza da web: páginas com poucos links, 52 em média , e muitos vértices pendentes, a matriz {Q} é mais densa e a matriz {R} é positiva. A matriz {A} pode ser escrita como {\mathbf{u}^\mathtt{T}\mathbf{a}} onde {\mathbf{u}} é o vetor com todas as entradas iguais a {1/n}. De fato, pode ser qualquer vetor de probabilidades, o vetor uniforme foi a escolha original, mas atualmente sabe-se que favorece link spamming e esse parâmetro também não é divulgado pela Google. O vetor {\mathbf{a}^\mathtt{T}} é o transposto do vetor característico dos vértices pendentes. Com essas definições

\displaystyle \begin{array}{rcl} \mathbf{p}^{(t)} =& \mathbf{p}^{(t-1)} R = p\mathbf{p}^{(t-1)}Q +(1-p)\frac 1n \mathbf{p}^{(t-1)} \mathbf{1}= p\mathbf{p}^{(t-1)}Q +(1-p)\frac 1n \mathbf{1}=\\& p\mathbf{p}^{(t-1)}Q + p\mathbf{p}^{(t-1)} \mathbf{u}^\mathtt{T}\mathbf{a} +(1-p) \mathbf{u}^\mathtt{T} \mathbf{e} \end{array}

onde {\mathbf{e}=(1,1,\dots,1)}, portanto só precisamos armazenar a matriz {P} e os vetores {\mathbf{a}}, {\mathbf{e}} e {\mathbf{u}}.

Exercício 114 Mostre que a matriz {R} é irredutível.

Exercício 115 O grafo dirigido com vértices {\{0,1,\dots, n-1\}} e arestas {(i,i+1\mod n)} é um circuito dirigido com {n} vértices. Analise o comportamento de {\mathbf{r}^{(k)}} para {k\in{\mathbb N}} com {\mathbf{r}^{(0)}= (1,0,\dots,0)}.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s