Page Rank

O PageRank é um algoritmo que mede a importância relativa de cada nó dentro de um grafo. A importância de um nó é determinada pela quantidade e qualidade dos links que apontam para ele.

Os resultados apresentados na imagem e gerados código a seguir mostram os valores finais de PageRank para os nós A, B, C e D.

graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": ["A", "D"],
    "D": ["C"]
}

Codigo do Page Rank

import numpy as np

# Grafo representado como dicionário: cada nó tem sua lista de links de saída
graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": ["A", "D"],
    "D": ["C"]
}

nodes = list(graph.keys())
n = len(nodes)

# Parâmetros
d = 0.85   # damping factor
epsilon = 1e-6  # critério de convergência

# Inicialização: todos começam com 1/n
pagerank = {node: 1/n for node in nodes}

converged = False

while not converged:
    new_pr = {}

    for node in nodes:
        # Teletransporte
        pr_value = (1 - d) / n

        # Somatório das contribuições
        for other in nodes:
            if node in graph[other]:  # se other aponta para node
                pr_value += d * (pagerank[other] / len(graph[other]))

        new_pr[node] = pr_value

    # Verificar convergência
    diff = sum(abs(new_pr[node] - pagerank[node]) for node in nodes)

    pagerank = new_pr

    if diff < epsilon:
        converged = True

print("PageRank Convergido:")
for node, pr in pagerank.items():
    print(node, round(pr, 4))




print("\nComparação com NetworkX:")




import networkx as nx

G = nx.DiGraph()

for node, links in graph.items():
    for t in links:
        G.add_edge(node, t)

nx_pr = nx.pagerank(G, alpha=0.85)

print("PageRank NetworkX:")
for node, pr in nx_pr.items():
    print(node, round(pr, 4))

Interpretação

Os resultados de PageRank Convergido e PageRank NetworkX são idênticos, o que confirma a correta implementação e convergência do algoritmo manual em relação à biblioteca padrão (NetworkX).

O valor de PageRank de um nó pode ser interpretado como a probabilidade de um "navegador aleatório" (o modelo subjacente ao algoritmo) estar naquele nó em um determinado momento. Quanto maior o valor, mais importante é o nó dentro da estrutura do grafo.

Quais são os nós mais importantes?

• Nó C: O Mais Importante

  • PageRank: 0.4292 (Mais Alto)
  • O nó C possui o maior PageRank, sendo considerado o mais importante da rede.Justificativa no Grafo: O nó C recebe links de todos os outros três nós (A -> C, B -> C, D -> C). Mesmo que os nós A e D recebam a mesma quantidade de PageRank de C, a contribuição de A, B e D para C o torna o centro de influência da rede.

• Nós A e D: Importância Intermediária/Igual

  • PageRank: 0.2199 (Idêntico)
  • Os nós A e D têm a mesma importância no grafo, ocupando a segunda posição.Justificativa no Grafo: Ambos recebem PageRank apenas do nó C (C -> A e C -> D). Como o nó C divide seu PageRank uniformemente entre A e D, e não há outras fontes de entrada para A ou D, eles terminam com o mesmo valor de importância.

• Nó B: O Menos Importante

  • PageRank: 0.131 (Mais Baixo)
  • O nó B tem o valor de PageRank mais baixo.Justificativa no Grafo: O nó B recebe links apenas do nó A (A -> B). Como A também aponta para C, o PageRank de A é dividido. Além disso, B não recebe nenhuma outra fonte de entrada. A baixa entrada de PageRank faz com que ele seja o nó com menor relevância.