Uma CMH é importante para a obtenção da distribuição estacionária. Podemos dizer que uma distribuição estacionária é um conjunto de probabilidades de se passar por cada vértice do grafo durante a caminhada. Ela é muito utilizada em diversas áreas, como por exemplo na computação ao se fazer rankings, como um page rank, pois com esta distribuição estacionária é possível descobrir em um grafo quais são os vértices mais "populares" ou no caso do pagerank, quais são os sites que recebem um maior número de visitas.
Para se obter uma distribuição estacionária única é necessário que a CMH seja irredutível e aperiódica. Para isso, é necessário que o grafo G utilizado para a caminhada aleatória seja conexo, não-direcionado e não-bipartido.
Para se obter tal distribuição estacionária foram usados três métodos:
- Solução Analítica (Teórica)
- Power Method
- Andar do Bêbado
O grafo utilizado para a demonstração foi o Dolphin Social Network (DSN), que representa uma rede social de golfinhos:
Esta é a solução considerada ideal. É obtida através do seguinte cálculo:
w(i) = d(vi) / 2|E|
Onde w(i) é a probabilidade de estar no estado i, d(vi) é o grau do vértice vi e |E| é o número de arestas do grafo. Ou seja, basta dividir o grau de cada vértice por 2 vezes o número de arestas do grafo. Cada valor w(i) que for obtido é armazenado em um vetor de probabilidades W, tendo um elemento para cada vértice:
W = [d(v1) / 2|E|, d(v2) / 2|E|, ... , d(vi) / 2|E|]
Usando o seguinte código em Python
Obtivemos o seguinte vetor de probabilidades, que descreve a distribuição estacionária do grafo DSN:
Power Method
Agora utilizaremos outro método para aprender a distribuição estacionária chamado Power Method, ou Lei da Caminhada Aleatória. Para usar este método devemos primeiramente escolher um número N de passos. Também devemos fazer um "chute" das probabilidades iniciais de se iniciar a caminhada em cada vértice do grafo para obter o vetor de probablidades iniciais w(0).
Vamos usar um exemplo simples para deixar o conceito mais claro. Tomemos o grafo abaixo:
Figura 1
Podemos escolher valores aleatórios para montar w(0), desde que a soma de todas as probabilidades seja igual a 1. Por exemplo, temos 6 vértices no grafo acima, podemos colocar probabilidades iniciais iguais para todo vértice, sendo portanto 1/6 para cada um, ou seja:
v1 v2 v3 v4 v5 v6
w(0) = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]
Então devemos multiplicar w(0), nosso passo 0, por uma matriz P para encontrar o valor de w(1), nosso próximo passo. P é o resultado da seguinte multiplicação:
P = Δ-1 * A
Onde A é a matriz de adjacência do grafo, demonstrando quais vértices estão ligados com quais vértices. No exemplo acima A seria igual a:
Δ-1 é igual a uma matriz preenchida com 0 e apenas em sua diagonal com valores correspondentes a 1/d(vi). Em nosso exemplo Δ-1 seria igual a:
Com esses dados agora seria possível realizar o Power Method para o grafo do exemplo realizando os cálculos:
w(1) = w(0) * P
w(2) = w(1) * P
w(3) = w(2) * P
...
w(N) = w(N-1) * P
Sendo N o número de passos escolhidos inicialmente. Desta forma a cada passo saberemos qual é a probabilidade de se passar por cada vértice.
Agora que já entendemos os conceitos utilizaremos o Power Method no grafo DSN.
O código em Python utilizado para o Power Method é o seguinte:
O resultado para N = 5 foi:
O resultado para N = 100 foi:
Note as diferenças de valores nas duas tentativas. Se continuarmos a aumentar o número de passos N os valores obtidos serão cada vez mais próximos aos obtidos na solução analítica.
Andar do Bêbado
Figura 2
O andar do bêbado é um método que pode ser ilustrado, como o nome já diz, por um bêbado caminhando. Inicialmente selecionamos aleatóriamente um vértice inicial. É necssário decidir também um número máximo de passos N.
Então, após dar todos os passos, é feito o seguinte cálculo para cada vértice:
w(i) ≈ n(i)/N
Os valores de cada vértice são armazenados, então, em um vetor que descreverá a distribuição estacionária do grafo analisado. Quanto maior o número de passos N mais próximos serão os valores da distribuição estacionária obtidos aqui com os obtidos na solução analítica.
Utilizando o grafo DSN podemos verificar o funcionamento do método.
O código utilizado foi:
Tomemos dois exemplos, um com um número relativamente baixo de passos e outro com mais passos. Após chegar aos resultados comparemos com os obtidos na solução analítica.
Primeiramente com N = 100 passos obtemos os seguintes resultados:
Com N = 1000000 temos:
Comparemos com o resultado da solução analítica:
Agora podemos ver na prática que quanto maior o N mais próximo da solução ideal (solução analítica) será o nosso resultado, ou seja, neste caso o resultado mais próximo do ideal foi com N = 1000000.
Entendendo estes conceitos e métodos podemos agora descobrir quais são os 10 golfinhos mais populares do DSN. O código usado para descobrir isto foi:
E aqui temos o TOP 10 dos Golfinhos:
Isto ilustra de forma simplificada como buscadores, como Google, fazem para rankear as páginas da internet.
Referências
Figura 1
http://danielamaral.wikidot.com/introducao-a-teoria-dos-grafos
Figura 2
https://en.wikipedia.org/wiki/Barney_Gumble
Nenhum comentário:
Postar um comentário