[CS224W] PageRank

 

1️⃣  PageRank Citation Ranking 논문 

---

 

🔹 Summary 

 

The PageRank Citation Ranking.pdf

0.76MB

 

 

•  자신의 검색어와 가장 잘 어울리는 페이지를 찾기위한 PageRank 

•  얼마나 많은 사이트들이 참조했는지 + 참조한 사이트들의 영향력은 어떻게 되는지 = Relative importance of Web pages 

 

•  PageRank : 웹 페이지들의 순위를 매기는 알고리즘 from link structure (backlinks)

↪  helps search engines and users quickly make sense of the vast heterogeneity of the WWW

↪  Applications : Search, browsing, traffic estimation 

 

 

rank 계산 공식

 

 

 

↪  각 페이지의 rank 는 고르게 분배된다. 

 

 

•  Random surfer model : 웹페이지를 탐방하는 유저의 행동을 random 하게 보는 것으로, loop 에 빠지거나 더 이상 살펴볼 페이지가 없으면 랜덤하게 다른 페이지를 찾아나서는 행동을 모델에 반영 

 

 

 

• Personalized PageRank : PageRank를 개인화하기 위해 임의의 서퍼 모델에서 teleport 확률과 transition 확률을 결정하는 노드 가중치 또는 엣지 가중치를 조정 (노드 근접성을 이용) 

 

 

 

 

 

 

2️⃣  코드 리뷰 

---

 

https://colab.research.google.com/drive/1g6DStJfwq_IhTROWX2zZPTafeuSofJaX?usp=sharing 

4주차 복습과제.ipynb

 

 

 

 

🔹 넘파이 구현 

 

(1) 고유값 분해를 통해 구하는 방법

 

 각 사이트에서 다른 사이트로 이동할 확률값을 가진 행렬에 대해 고유값과 고유벡터를 구하고 첫번째로 큰 고유값에 대응하는 고유벡터를 정규화하여 각 사이트의 중요도를 구한다. 

 

import numpy as np 
L = np.array([
    [0,1/2,1/3,0,0,0], 
    [1/3,0,0,0,1/2,0], 
    [1/3,1/2,0,1,0,1/2],
    [1/3,0,1/3,0,1/2,1/2],
    [0,0,0,0,0,0],
    [0,0,1/3,0,0,0]
]) # 6개의 사이트만 존재하는 네트워크망이라 가정 

# L 에 대한 eigenvalue, eigenvector 계산 
eigen_value , eigen_vector = np.linalg.eig(L)

# eigen value 내림차순 정렬 
order = np.absolute(eigen_value).argsort()[::-1] 

# 정렬 순서에 따라 재정렬 
eigen_value = eigen_value[order] 
eigen_vector = eigen_vector[:,order] 

# 첫번째 eigen value 에 대한 eigenvector 추출 및 비중확인 
r = eigen_vector[:,0]  # 0번째 열 
print(100*np.real(r/np.sum(r))) ## np.real : 복소수 인수의 실수부를 반환

# 세번째 사이트의 중요도가 가장 높게 나옴

 

 

 

(2) Power iteration 으로 구하는 방법 

 

임의 접속자들이 사이트를 무작위로 접속한다 가정하고 주어진 경로로 이동할 확률 행렬을 통해 재귀적으로 업데이트를 수행하여 각 사이트의 접속자 수가 특정 임계치 이하로 수렴할때까지 반복해 사이트별 중요도를 근사한다.

 

• r' = L*r

 

# 100명 접속 가정, 초기 접속률은 모두 동일하게 구성 

r = 100*np.ones(6)/6 
lastR = r 
r = L@r

i = 0 
while np.linalg.norm(lastR - r) > 0.01 : # 임계점까지 수행 
  lastR = r 
  r = L@r 
  i+=1 

print(f'{str(i)} iterations to convergence') 
print(r)

 

 

 

 

※ 참고 : https://big-dream-world.tistory.com/49 

 

 

🔹 networkX 라이브러리 구현 

 

 

pagerank(G, alpha = 0.85, personalization = None, max_iter = 100,tol=1e-06, nstart=None, weight='weight', dangling=None)

 

•  G : 그래프 

•  alpha : Damping parameter (for teleport) 

•  max_iter : Maximum number of iterations in power method eigenvalue solver

•  Personalization : personalized pagerank 

 

 

(1) 그래프 생성하기 

 

G = nx.DiGraph() 

[G.add_node(k) for k in ["A", "B", "C", "D", "E", "F", "G"]]  

G.add_edges_from([
    ('G','A'), ('A','G'),('B','A'),
    ('C','A'),('A','C'),('A','D'),
    ('E','A'),('F','A'),('B','D'),
    ('D','F')
])

 

 

 

(2) pagerank 실행 

 

pr1 = nx.pagerank(G) 
print(pr1)

 

{'A': 0.40001520046189115, 'B': 0.021428571428571432, 'C': 0.1347663991011727, 'D': 0.14387354195831553, 'E': 0.021428571428571432, 'F': 0.1437213165203047, 'G': 0.134766399101172}

 

 

 

 

 

(3) dampening 조정하기 (teleports) 

 

•  alpha

 

pr_09 = nx.pagerank(G, alpha = 0.9) 
pr_08 = nx.pagerank(G, alpha = 0.8) 
res = pd.DataFrame({"alpha=0.9": pr_09, "alpha=0.8": pr_08}) 
res

 

 

 

 

(4) Personal pagerank 

 

•  personalization 

 

pr_e = nx.pagerank(G, alpha = 0.9, personalization = {'E' : 1})  
print(pr_e)

 

{'A': 0.4147475495142858, 'B': 0.0, 'C': 0.12442358835485172, 'D': 0.12442358835485172, 'E': 0.09999999999999998, 'F': 0.11198168542115904, 'G': 0.1244235883548517}

 

 

 

👉 노드 E 로부터 노드 B 는 접근이 아예 불가능하기 때문에 E의 관점에서 중요도가 0이 됨

 

 

 

(5) 영화 추천시스템 구현 프로젝트 

 

•  Movielens data 사용 (불러오기는 생략) 

 

 

 

 

•  그래프 생성 및 노드추가 (사용자, 영화) , 엣지 가중치 (평점) 추가 

 

# 그래프 생성하기 

G = nx.Graph() 

# 노드 추가하기 
G.add_nodes_from(rdata.userId, bipartite = 0) 
G.add_nodes_from(rdata.movieId, bipartite = 1) 

# 엣지 가중치 추가하기 
G.add_weighted_edges_from([(uId, mId, rating) for (uId, mId, rating) in rdata[['userId', 'movieId', 'rating']].to_numpy()])

 

 

•  페이지랭크 실행 및 상위 영화 출력 

 

# 페이지랭크 실행 
movie_rank = nx.pagerank(G, alpha=0.85)

# 상위 영화 출력 

def return_top_movies(movie_rank) : 
  movie_rank = dict(sorted(movie_rank.items(), key = lambda item : item[1], reverse = True)) 
  top_10_movies = [] 
  for key, value in movie_rank.items() : 
    if 'i' in key : 
      top_10_movies.append(key) 
      if len(top_10_movies) == 10 : 
        break 
  return item_data.loc[top_10_movies]


return_top_movies(movie_rank)

인기영화들이 출력

 

 

•  Personalized Recommend : 196번 유저의 관점에서 중요도를 다시 선정함 

 

user_query = 'u196' # 196번 유저의 관점에서 중요도를 다시 산정 
recommendation = nx.pagerank(G, alpha=0.85, personalization={user_query:1})
return_top_movies(recommendation)