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 é

$\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)}$ .

Notas de aula

Jair Donadelli

bc1414 Passeio aleatório em grafos

Deixe um comentário Cancelar resposta

Compartilhe isso:

Relacionado

Deixe um comentário Cancelar resposta