[Python] PageRank

모듈 불러오기

사용할 모듈을 import 합니다.

import matplotlib.pyplot as plt
import numpy as np
import requests

 

데이터 불러오기

본 실습에서는 하이퍼링크 그래프 데이터를 requests를 활용하여 불러오겠습니다. example_index는 노드 정보이고, example_arc는 엣지 정보입니다.

with open("example_index", "wb") as f:
  r = requests.get("http://webdatacommons.org/hyperlinkgraph/data/example_index")
  f.write(r.content)

with open("example_arcs", "wb") as f:
  r = requests.get("http://webdatacommons.org/hyperlinkgraph/data/example_arcs")
  f.write(r.content)

 

자료 링크입니다.

WDC - Hyperlink Graphs

 

데이터 준비

데이터를 사용하기 편하도록 전처리해줍니다. 위에서 가져온 노드 정보에는 각 사이트 주소와 인덱스 정보가 담겨있습니다. 그중에서 사이트 주소만 분리하여 저장합니다. 이때 기존 인덱스 순서대로 저장하기 때문에 인덱스 정보를 제거해도 활용이 가능합니다.

nodes = np.loadtxt("example_index", dtype=object)[:, 0]
edges = np.loadtxt("example_arcs", dtype=int)

 

데이터 살펴보기

파이썬의 networkx 라이브러리를 활용하여 시각화해봅시다. nodes와 edges를 활용하여 그래프에 새로운 엣지들을 추가해주면 됩니다. 시각화하면 페이지들 간의 연관성을 대략적으로 파악할 수 있습니다.

import networkx as nx

G = nx.DiGraph()

for n1, n2 in edges:
  G.add_edge(nodes[n1], nodes[n2])

pos = nx.spring_layout(G, k=1, iterations=200)

plt.figure(dpi=200)
nx.draw(G, pos, with_labels=True, node_size=10, font_size=5, width=0.1)
plt.show()

 

pagerank

이제 pagerank를 구현해보겠습니다. 우선 Adjacenct List 형식으로 데이터를 구성하고, 각 노드마다 그 노드의 점수를 다른 이웃들에게 골고루 나누어 줍니다. 이후 각 노드마다 받은 점수를 모두 합산합니다. 이 과정을 반복하면 됩니다.

 

함수 인자는 총 4가지를 받습니다. 엣지 목록인 edges, teleport할 확률인 beta, r벡터 변화량이 특정값보다 작을 경우 계산을 중단시키는데, 이 특정값을 threshold로 설정합니다. 마지막으로 반복 계산 횟수인 epoch을 설정해줍니다. 각 코드 문장은 주석을 보며 이해하시면 됩니다. 여기서 teleport란, Spider trap이나 Dead end(dangling node) 문제를 해결하기 위해 다른 노드로 랜덤하게 teleport 해줄 확률을 의미합니다.

num_nodes = nodes.shape[0]


def pagerank(edges, beta, threshold=10^-20, epochs=100):
 # Adjacency List 만들기
 neighbors = [[] for _ in range(num_nodes)]
 for e in edges:
  neighbors[e[0]].append(e[1])
 
 # 벡터 초기화: 모든 값을 (1/n)으로 설정
 r = [1/num_nodes] * num_nodes

 for epoch in range(epochs): 
  # 업데이트된 값을 저장할 벡터 초기화
  r_next = [0] * num_nodes

  # 모든 노드에서
  for u in range(num_nodes):
  # 그 노드가 가리키는 이웃 노드에게
    for v in neighbors[u]:
      # 현재 자신의 점수 r[u]에 (1-beta)을 곱하고, 등분하여 나눠줌
      r_next[v] += (1 - beta) * r[u] / len(neighbors[u])
  
  # r_next의 합을 1로 맞춤
  r_sum = sum(r_next)
  for u in range(num_nodes):
    r_next[u] /= r_sum
  
  # 이전 벡터 r과 새로운 벡터 r_next 사이의 변화량을 합산
  delta = sum(abs(a-b) for a, b in zip(r, r_next))

  # 원래 벡터를 새로 계산한 벡터로 교체
  r = r_next

  if delta < threshold:
    break
 
 return r

 

결과 확인

불러온 데이터를 pagerank 함수에 넣고 결과를 확인해봅니다. 점수가 높은 상위 10개의 페이지만을 출력해보았습니다.

r = pagerank(edges, beta=0.2)
s = sorted(((r_n, n) for r_n, n in zip(r, nodes)), reverse=True)[:10]

for a in s:
  print(a)

(0.11971571923114015, 'blogspot.com')

(0.07960149118604974, 'rea-group.com')

(0.04723222503656371, 'canalblog.com')

(0.04051197935893999, 'creativecommons.org')

(0.036622172789321554, 'yahoo.com')

(0.03143847116990241, 'wordpress.com')

(0.03117252831421998, 'yahoo.com.au')

(0.03117252831421998, 'rivals.com')

(0.03117252831421998, 'realestate.com.au')

(0.027409441325730685, 'flickr.com')