MAC323 Algoritmos e estruturas de dados II

Exercício-Programa de Recuperação

Passeios aleatórios, PageRank e matrizes esparsas

Seu EP

Neste EP, você irá se familiarizar com o uso de matrizes esparsas, estimando a distribuição estacionária de certos passeios aleatórios em grafos. Tais distribuições formam a base do algoritmo PageRank, usado na máquina de busca Google.
Estude, inicialmente, a Seção 1.6, Case Study: PageRank, de IntroCS.
Você pode achar interessante recordar alguns conceitos básicos de processos estocásticos de MAC0228.
Note que a Seção 1.6 está escrita "no nível de MAC0110" (por exemplo, os programas não usam OOP). Neste EP, você deve fazer uma implementação mais sofisticada, usando matrizes (e vetores) esparsos e implementando classes que você achar convenientes. Lembre-se de que falamos sobre matrizes e vetores esparsos brevemente na Seção 3.5 de Algs4.
Os grafos nos quais sua implementação será testada serão grafos grandes. Por exemplo, sua implementação deve ser capaz de lidar com alguns dos grafos em
Stanford Large Network Dataset Collection [https://snap.stanford.edu/data/index.html]

Outros grafos nos quais seu programa deve ser testado devem ser extraídos do OpenStreetMap (OSM), como no EP4.
A forma de se especificar um grafo de entrada extraído do OSM deve ser idêntico à forma do EP4.
Para os grafos do OSM, seu programa deverá ser capaz de produzir uma saída gráfica também, para ilustrar a distribuição estacionária encontrada. Veja o Creative Exercise 19 na Seção 1.6, Case Study: PageRank (IntroCS). Este exercício fala em usar o tamanho dos círculos que representam os vértices; use também cores, para melhorar sua representação.

Passeios aleatórios; componentes fortemente conexas

Passeios aleatórios clássicos e com "teleportagem"

O passeio aleatório discutido Case Study: PageRank (IntroCS) tem um componente de "teleportagem", seguindo a regra 90-10. Dado um número real \(0\leq\alpha\leq1\), vamos chamar de \(\alpha\)-passeio aleatório (\(\alpha\)-PA) um passeio em que, com probabilidade \(1-\alpha\), o próximo vértice é escolhido uniformemente ao acaso, dentre todos possíveis vértices. Por exemplo, o passeio aleatório em Case Study: PageRank é um \(\alpha\)-passeio aleatório com \(\alpha=0.9\) (teleportagem acontece com probabilidade \(10\%\)). O passeio aleatório "clássico" é o \(1\)-passeio aleatório (sem teleportagem).

Seu programa deverá estimar a distribuição estacionária do \(\alpha\)-passeio aleatório, com o valor de \(\alpha\) podendo ser dado pelo usuário (use o valor default \(\alpha=0.95\) se o usuário não especificar nenhum um valor).

Componentes fortemente conexas

Lembre que um grafo é fortemente conexo se há um caminho dirigido entre quaisquer dois vértices \(v\) e \(w\) do grafo. Passeios aleatórios com teleportagem (com \(\alpha<1\)) são úteis para lidar com grafos dirigidos que não são fortemente conexos (o que acontece com um \(1\)-passeio aleatório em um grafo que não é fortemente conexo?).

Muitos grafos que ocorrem naturalmente nas aplicações têm componentes fortemente conexas gigantes. Uma componente fortemente conexa em um tal grafo é claramente maior do que todas as outras componentes fortemente conexas daquele grafo.

Seu programa deve ter dois modos de execução:

O \(\alpha\)-PA é sobre o grafo todo
Nesse modo, todo o grafo especificado pelo usuário deverá ser considerado na obtenção da distribuição estacionária do passeio aleatório.
O \(\alpha\)-PA é restrito à componente fortemente conexa gigante do grafo
Nesse modo, seu programa deve inicialmente determinar a componente gigante do grafo. Determinada essa componente, seu programa deve obter a distribuição estacionária do passeio aleatório restrito a essa componente. Equivalentemente, você deve ignorar todos os vértices que não pertencem à componente gigante (você poderia simplesmente remover todos os vértices e arcos que não pertencem à componente gigante e poderia trabalhar com o grafo resultante).

Vértice inicial

Como em Case Study: PageRank, para obter a distribuição estacionária de um \(\alpha\)-passeio, você terá de escolher um vértice inicial para o passeio (na verdade, uma distribuição de probabilidade no conjunto de vértices do grafo em questão concentrada em um único vértice (isto é, um vetor com um único \(1\) e \(0\) nas demais entradas)). Use um valor default em seu programa. Seu programa deverá ser tal que o usuário poderá também especificar esse vértice inicial.

Saídas que seu programa deve produzir

O usuário deverá poder especificar algumas formas de saída para seu programa.

Impressão da distribuição limite toda
Por exemplo, no pequeno exemplo em Case Study: PageRank (tiny.txt), essa saída poderia ser simplesmente
```
0.27245425061352857
0.2651535628838315
0.14668623692407368
0.2476435226257308
0.06806242695283572
```
Impressão da distribuição limite, com os valores ordenados de forma decrescente
No caso de grafos maiores, será conveniente poder escolher como saída os maiores valores do vetor com a distribuição, ordenados de forma decrescente. O usuário deve poder especificar quantos elementos a saída deve ter.

Suponha que, por exemplo, queremos investigar o grafo web-Google.txt em https://snap.stanford.edu/data/web-Google.html. Suponha também que queremos trabalhar apenas com a componente fortemente conexa gigante desse grafo (que tem 434818 vértices). Suponha que usamos \(\alpha=.95\) e que queremos saber os 10 maiores valores da distribuição limite. A saída seria algo como
```
0.0011387166427851692
0.0011300339238504657
0.0011013372463992705
0.0010644137174960773
0.001018506824348466
0.0010121929950123111
0.001008816823621604
9.788624147173766E-4
9.638434645167192E-4
9.318727586462819E-4
```
Interface gráfica
No caso de grafos extraídos do OSM, como já mencionado, é possível representar a distribuição limite calculada com uma figura. Veja o Creative Exercise 19 em Case Study: PageRank. Este exercício fala em usar o tamanho dos círculos que representam os vértices; use também cores, para melhorar sua representação. No caso de grafos do OSM, implemente também uma interface que permite ao usuário clicar em um ponto do mapa para especificar o ponto inicial do passeio sendo simulado.

Documentação

Seu EP deve estar bem documentado. Em particular inclua exemplos de execução completos (entrada e saída), para que o monitor possa facilmente reproduzir os testes que você fez. Você deve executar testes em grafos de grandes proporções e você deve comentar a eficiência de seu sistema (complexidade e tempo de execução em exemplos concretos).

Deve haver documentação específica para cada classe, assim como a relação entre elas deve ser explicada.

Este EP é estritamente individual

Diferentemente do EP4, este EP deve ser feito individualmente.

Observação

Ao usar o "método das potências" (Case Study: PageRank) para obter uma boa aproximação para a distribuição estacionária, será necessário fazer um número razoavelmente grande de produtos entre matrizes e vetores. Caso seu programa seja rápido para \(\alpha=1\) mas marcadamente mais lento para \(\alpha<1\), então é possível que você não esteja explorando a esparsidade de matriz adequadamente.

Alterações, correções e atualizações

Como estou divulgando versões parciais do enunciado, vou manter um log das alterações, correções e atualizações mais importantes.

[2015-07-27 Mon 02:22] Observação da esparsidade adicionada
[2015-07-25 Sat 13:33] Versão basicamente final
[2015-07-25 Sat 13:33] Especificação da saída adicionada
[2015-07-25 Sat 13:33] Discussão sobre componentes fortes adicionada
[2015-07-23 Thu 16:26] Primeira versão do enunciado disponibilizada.