[22-2] PageRank using Networkx

Networkx 모듈을 사용하면 한 줄로 PageRank를 구현할 수 있습니다.

 

1️⃣ 설정

 

필요한 모듈을 import 합니다.

import networkx as nx

import os

import os.path as osp

import numpy as np

import sys

import matplotlib.pyplot as plt

import collections

from google.colab import drive

drive.mount('/content/drive')

np.set_printoptions(threshold=sys.maxsize)

방향이 있는 Graph를 선언합니다.

G = nx.DiGraph()

 

2️⃣ 데이터셋 확인하기

 

PageRank를 사용하기에 앞서 3개의 Dataset이 필요합니다.

 

• Vertex2name.txt : 어떤 문서에 어떤 키워드들이 포함되어있는지 적혀있는 파일

2329042	대문
1368818	지미카터
181172	대문/보존문서1
72767	Xaos
1989085	수학
2116874	수학상수
2572056	도움말
1947896	문서편집도움말
54	BrionVIBBER
1179391	문학
2064690	나라목록
1445253	화학

...

• edges.txt : 하이퍼링크들이 저장된 파일

# (하이퍼링크 나가는 식별자)  (하이퍼링크 들어오는 식별자)   

2169684	852154
2169684	2153393
2169684	2924673
2386025	1307521
1944832	1944832
1684754	2011869
1684754	852154
1684754	2153393
1684754	2844588
1684754	2924673
1993648	1993648
1773250	431258
1773250	1773250

...

• keyword.txt : 찾으려는 키워드들의 정보를 포함한 파일

2052588
2518945
2921587
2566919
2534664
2300273
1986247
2432258
2417705

...

 

 

3️⃣ 데이터셋 읽어오기

 

위의 txt로 저장된 데이터셋을 읽어서 Graph와 dict에 저장합니다.

path_v2n = osp.abspath(osp.join(os.getcwd(), 'vertex2name.txt'))    # 어떤 문서에 어떤 키워드들이 포함되어있는지 적혀있는 파일의 경로

path_edges = osp.abspath(osp.join(os.getcwd(), 'edges.txt'))        # 하이퍼링크들이 저장된 파일의 경로

path_keyword = osp.abspath(osp.join(os.getcwd(), 'keyword.txt'))  # 키워드들의 정보를 포함한 파일의 경로


f = open(path_edges)

for line in f:

    v1, v2 = map(int, line.split()) # v1 : 하이퍼링크 나가는 식별자, v2 : 하이퍼링크 들어오는 식별자
    
    G.add_edge(v1, v2)    # 간선 연결
    

n2v = {}

v2n = {}

f = open(path_v2n)

for line in f:

    v, n = line.split()
    
    v = int(v)
    
    n = n.rstrip()
    
    n2v[n] = v
    
    v2n[v] = n
    

node_key = []

f = open(path_keyword)

for line in f:

    v = line.rstrip()
    
    v = int(v)
    
    node_key.append(v)

 

4️⃣ 부분 그래프 (Subgraph) 그리기

 

키워드를 포함한 문서들로 이루어진 부분 그래프(subgraph) H를 추출합니다.

H는 주어진 keyword만이 포함된 정점들로 구성된 부분 그래프로 반환됩니다.

H = G.subgraph(node_key)

 

5️⃣ PageRank 출력하기

 

Subgraph H에 대해서 pagerank 알고리즘을 시행합니다.

PageRank 알고리즘이 수행되면 문서 별 점수를 계산해서 나타내줍니다. (문서들은 pageRank 점수 역순으로 정렬하여 출력합니다.)

pr = nx.pagerank(H, alpha = 0.9)      # 부분 그래프 H 사용

이미 H에는 edge들이 연결된 G가 들어가 있기 때문에 그 값을 기반으로 node_key에 대해서만 pageRank 계산합니다.

 

 

이후, pageRank를 높은 순으로 정렬하여 list로 만들어서 출력이 가능합니다.

res = [key for (key, value) in sorted(pr.items(), key=lambda x:x[1], reverse=True)]

 

6️⃣ PageRank 함수 구현

 

PageRank는 다음과 같은 수식으로 표현할 수 있습니다.

 

 

• $r_{i}$ : Pagerank score vector
• $N_{in}(j)$ : $j$ 페이지로 들어오는 이웃 페이지들
• $\beta$ : 감폭 비율
• $d_{out}(i)$ : $i$ 페이지의 나가는 이웃 수
• $|V|$ : 전체 웹 페이지 수

의사 코드 (pseudocode)로 표현하면 다음과 같습니다.

 

https://www.edwith.org/bcaitech1

 

코드로 작성하면 다음과 같습니다.

from copy import copy


# Compute the distance between two dictionaries based on L1 norm

def l1_distance(x: DefaultDict[int, float], y: DefaultDict[int, float]) -> float:

    err: float = 0.0
    
    for k in x.keys():
    
        err += abs(x[k] - y[k])
        
    return err
    
    
    
def pagerank(

    graph: Graph_dict,		# 그래프 G(V,E)
    
    damping_factor: float,	# 감폭 비율 beta
    
    maxiters: int,			# 최대 반복수 T
    
    tol: float,				# 입계값
    
) -> Dict[int, float]:

    vec: DefaultDict[int, float] = defaultdict(float)  # Pagerank vector
    
    vec_new : DefaultDict[int, float] = defaultdict(float)  # Pagerank vector
    
    
    itr = 0
    
    vertices = graph.nodes()		# 모든 vertics들
    
    V_SIZE = len(vertices)		# |V|
    
    
    # init pagerank vector
    
    for j in graph.nodes():
    
        vec[j] = float (1/V_SIZE)
        

    for n in range(maxiters):
    
        S = 0
        
        for j in vertices:
        
            vec_new[j] = 0
            
            for i in vertices:
            
                if graph.has_edge(i,j):   # i -> j로 가는 edge를 찾음 (N_in(j)를 나타냄)
                
                    vec_new[j] += damping_factor*(vec[i] / graph.out_degree(i))
                    
            S += vec_new[j]
            
        for j in vertices:
        
            vec_new[j] += (1-S) / V_SIZE
            

        delta: float = 0.0
        
        delta = l1_distance(vec_new, vec)
        
        if delta < tol:
        
            break

        vec = copy(vec_new)
        
        itr +=1


    return dict(vec)