PageRank

Uma página Web pode ser considerada relevante por uma máquina de busca se várias páginas apontam para ela e/ou se ela é referenciada por outras páginas relevantes. Este é o princípio por trás da métrica PageRank, desenvolvida pela universidade de Stanford e utilizada, com variações, pelo Google. Nesta tarefa, trabalharemos com uma estrutura simplificada da Web em que teremos apenas informações sobre identificadores de páginas e links. As páginas serão identificadas por letras e um link de uma página A para uma página B será indicado por A → B. Os cálculos dos valores de PageRank serão feitos de maneira iterativa.

• Valor inicial: O valor inicial PR0(id_pag) é 1/N, onde N é o número de identificadores das páginas da rede.
• Fator de amortecimento: o algoritmo estabelece um valor d para indicar a probabilidade de um usuário seguir um link a partir da página atual ao invés de digitar um novo endereço Web no navegador. O fator de amortecimento garante que páginas sem nenhum link para elas possam ter uma probabilidade mínima (1−d)/N de acesso. Nesta tarefa, adotaremos d = 0.875 para todos os exemplos e testes.
• Número de links: O número de links de saída uma página N_Links(id_pag) reflete o número de páginas distintas apontadas por id_pag. Para o cálculo do PageRank, links de uma página para ela mesma serão desconsiderados. Em caso de múltiplos links de uma página para outra, apenas o primeiro será considerado.
• Passo: O valor de PageRank de uma página no passo i(PRi(id_pag)) será calculado a partir dos valores PRi−1 das páginas id_pag_link que apontam para id_pag de acordo com a fórmula abaixo:

Entrada

A primeira linha conterá a lista de identificadores de páginas, separados por espaços em
branco. As linhas seguintes conterão zero ou mais links no formato indicado e a última linha
conterá o número de passos a serem calculados.

Saída

A primeira parte da saída descreverá as ligações entre as páginas de maneira resumida. Para
cada página com identificador < id_pag >, em ordem alfabética, será gerado um par de linhas
no formato abaixo. A primeira linha contém o identificador < id_pag >, o símbolo → e a lista
de páginas para as quais < id_pag > aponta. A segunda linha contém a lista de páginas que
apontam para < id_pag >, o símbolo → e o identificador < id_pag >. Note que na apresentação
destas listas não devem aparecer múliplos links nem links de uma página para ela mesma.

<id_pag> -> [ ]
[ ] -> <id_pag>

A segunda parte conterá os valores de PageRank calculados para cada passo do algoritmo.
As páginas deverão aparecer em ordem alfabética e os valores de PageRank formatados com três
casas decimais.

PageRank (passo )
<id_pag1>: <PRi(<id_pag1)>
<id_pag2>: <PRi(<id_pag2)>
...