검색 엔진에서는 그래프를 어떻게 활용할까?

검색 엔진에서는 그래프를 어떻게 활용할까?¶

---

✅ 페이지랭크의 배경¶

1️⃣ 웹과 그래프¶

📌웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성 있는 그래프이다.¶

• 웹페이지는 정점에 해당
• 웹페이지가 포함하는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당
• 단, 웹페이지는 추가적으로 키워드 정보를 포함하고 있다.

2️⃣ 구글 이전의 검색 엔진¶

📌 첫번째 시도는 웹을 거대한 디렉토리로 정리하는 것이다.¶

• 웹페이지의 수가 증가함에 따라서 카테고리의 수와 깊이도 무한정 커지는 문제가 있다.
• 참고로 현재는 수십억 ~ 수백억 개의 웹페이지가 있는 것으로 알려져 있다.
• 또한, 카테고리 구분이 모호한 경우가 많아, 저장과 검색에 어려움이 있다.

📌 두번째 시도는 웹페이지에 포함된 키워드에 의존한 검색 엔진¶

• 사용자가 입력한 키워드에 대해, 해당 키워드를 (여러 번) 포함한 웹페이지를 반환한다.
• 하지만, 이 방법은 악의적인 웹페이지에 취약하다는 단점 존재
• 예를 들어, 성인 사이트에 "축구"라는 키워드를 (보이지 않도록) 여러 번 포함하게 되면,"축구"를 검색했을 때 해당 성인 사이트가 결과로 나올 수 있습니다

✅ 페이지랭크의 정의¶

1️⃣ 페이지랭크의 정의: 투표 관점¶

📌 페이지랭크의 핵심 아이디어는 투표이다. 즉, 투표를 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾는다.¶

• 투표의 주체는 웹페이지이다.
• 웹페이지는 하이퍼링크를 통해 투표를 한다.

🔎 사용자 키워드를 포함한 웹페이지들을 고려한다. 웹페이지 A가 B로의 하이퍼링크를 포함한다면?

A의 작성자가 판단하기헤 B가 관련성이 높고 신뢰할 수 있다는 것을 의미한다. 즉, A가 B에게 투표했다고 생각할 수 있다.

📌 즉, 들어오는 간선이 많을 수록 신뢰할 수 있다는 뜻¶

• 논문을 고를 때도 마찬가지입니다
• 사람들은 많이 인용된 논문을 더 많이 신뢰합니다

🔎 그런데 들어오는 간선의 수를 세는 것만으로 충분할까?

악용될 소지가 있다.

웹페이지를 여러 개 만들어서 간선의 수를 부풀릴 수 있다. 즉, 관련성과 신뢰도가 높아 보이도록 조작할 수 있다. 아래 그림을 보면 웹 그래프의 일부이고 완변한 대칭성등, 인위적으로 만들어진 것으로 의심이 된다.

🔎 이런 악용을 막으려면 어떻게 해야 할까?

이런 악용에 의한 효과를 줄이기 위해, 페이지랭크에서는 가중 투표를 한다.

• 즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주한다.
• 반면, 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주한다.
• 악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방법이다.

🔎 관련성과 신뢰성은 저희가 투표를 통해 측정하려는 것 이었고 그러면 출력을 입력으로 사용하게 되는데?

이 문제는 재귀(Recursion), 즉 연립방정식 풀이를 통해 가능하다.

📌 측정하려는 웹페이지는 관련성 및 신뢰도를 페이지랭크 점수라고 부른다.¶

• 각 웹페이지는 각각의 나가는 이웃에게 ${자신의 페이지 랭크 점수 \over 나가는 이웃의 수}$만큼의 가중치로 투표한다.

• 위 예시에서 웹페이지 j는 웹페이지 x,y,z에게 각각 가중치 ${r_{j} \over 3}$으로 투표한다.
• 여기서 $r_{j}$는 웹페이지 j의 페이지랭크 점수를 의미

각 웹페이지의 페이지랭크 점수는 받은 투표의 가중치 합으로 정의된다

• 위 예시에서 웹페이지 𝑗의 페이지랭크 점수 $r_{j}$는 다음과 같습니다 $$r_{j} = r_{i}/3 + r_{k}/4$$

페이지 랭크 점수의 정의는 다음과 같다.

$$r_{j} = \sum_{i∈N_{in}(j)} {r_{i} \over d_{out}(i)}$$

또 다른 예시를 보게 되면, 위 예시에서 정점 별 페이지랭크 식은 다음과 같다.

$r_{y} = r_{y}/2 + r_{a}/2$
$r_{a} = r_{y}/2 + r_{m}$
$r_{m} = r_{a}/2$

변수 3개 식이 3개이므로 연립방정식을 통해 풀 수 있다.

2️⃣ 페이지랭크의 정의: 임의 보행 관점¶

📌 페이지랭크는 임의 보행(Random Walk)의 관점에서도 정의할 수 있다.¶

• 임의 보행을 통해 웹을 서핑하는 웹서퍼를 가정하자
• 즉, 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑한다.

웹서퍼가 𝑡번째 방문한 웹페이지가 웹페이지 𝑖일 확률을 $p_{i}(t)$라고 하자.
그러면 $p(t)$는 길이가 웹페이지 수와 같은 확률분포 벡터가 되고 아래식이 성립한다.

$$p_{j}(t+1) = \sum_{i∈N_{in}(j)} {p_{i}(t) \over d_{out}(i)}$$

t번째 방문한 웹페이지가 웹페이지 i일 확률은 $p_{i}(t)$이다. 이때 다음 t+1번째에 방문한 웹페이지가 j일 확률은 t번째 방문한 확률에 웹페이지에서 나가는 간선의 개수인 $d_{out}(i)$로 나누게 되면 각각 균등한 나가는 확률이 구해지고 여기서 웹페이지 j에 들어오는 간선들에 각각을 계산해서 더해주게 되면 $p_{j}(t+1)$의 값을 구할 수 있다.

웹서퍼가 이 과정을 무한히 반복하고 나면, 즉 𝑡가 무한히 커지면, 확률 분포 𝒑(𝒕)는 수렴하게 된다.

다시 말해 $p(t) = p(t+1) = p$이 성립하게 된다.
수렴한 확률 분포 𝒑는 정상 분포(Stationary Distribution)이라고 부른다.
그러면 앞서 소개한 수식을 아래와 같이 바꿀 수 있다.

📌 투표 관점에서 정의한 페이지 랭크 점수는 임의 보행 관점에서 정상 분포와 동일하다.¶

✅ 페이지랭크의 계산¶

1️⃣ 페이지랭크의 계산: 반복곱¶

📌 페이지랭크 점수의 계산에는 반복곱(Power Iteration)을 사용한다.¶

반복곱은 다음 3단계로 구성

1. 각 웹페이지 $i$의 페이지랭크 점수 $r_{i}^{(0)}$를 동일하게 ${1 \over 웹페이지의 수}$로 초기화 한다.

2. 아래 식을 이용하여 각 웹페이지의 페이지 랭크 점수를 갱신한다.
   
   $r_{j}^{(t+1)} = \sum_{i∈N_{in}(j)} {r_{i}^{(t)} \over d_{out}(i)}$
   
   

3. 페이지랭크 점수가 수렴하였으면 종료한다. 아닌 경우 2로 돌아간다.(수렴 조건, $r^{(t)} \thickapprox r^{(t+1)}$)

🔎 예시

위와 같이 계속 계산하면 마지막 값으로 수렴한다.

2️⃣ 문제점과 해결책¶

📌 반복곱이 항상 수렴하는 것을 보장하지 않는다.¶

아래 예시로 계산을 하게 되면 수렴하지 않는다는 것을 알 수 있다.

들어오는 간선은 있지만 나가는 간선은 없는 정점 집합인 스파이더 트랩(Spider Trap)에 의한 문제이다.

📌 반복곱이 "합리적인"점수로 수렴하는 것을 보장하지 않는다.¶

들어오는 간선은 있지만 나가는 간선은 없은 막다른 정점(Dead End)에 의한 문제이다.

📖 문제 해결을 위해 순간이동(Teleport)을 도입한다.¶

임의 보행 관점에서, 웹을 서핑하는 웹서퍼의 행동을 다음과 같이 수정한다.

1. 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동
2. 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 𝛼인 동전을 던진다.
3. 앞면이라면, 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭
4. 뒷면이라면, 임의의 웹페이지로 순간이동

1과 4의 임의의 웹페이지는 전체 웹페이지들 중에 하나를 균일확률로 선택한다. 순간이동에 의해서 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어졌다. 𝛼를 감폭 비율(Damping Factor)이라고 부르며 값으로 보통 0.8 정도를 사용합니다

📌 순간이동 도입은 페이지 랭크 점수 계산을 다음과 같이 바꾼다.¶

1. 각 막다른 정점에서 (자신을 포함) 모든 다른 정점으로 가는 간선을 추가한다.
2. 아래 수식을 사용하여 반복곱을 수행한다.

$$r_{j} = \sum_{i∈N_{in}(j)} (\alpha{r_{i}^{(t)} \over d_{out}(i)}) + (1-\alpha){1 \over |V|}$$¶

• |𝑉|는 전체 웹페이지의 수를 의미
• $\sum_{i∈N_{in}(j)} (\alpha{r_{i}^{(t)} \over d_{out}(i)})$ 부분은 하이퍼링크를 따라 정점 𝑗에 도착할 확률을 의미
• $(1-\alpha){1 \over |V|}$은 순간이동을 통해 정점 𝑗에 도착할 확률을 의미

📌 실제 논문의 의사 코드(pseudocode)이다.¶

✅ PageRank 알고리즘¶

라이브러리 로드¶

In [1]:

import networkx as nx
import os
import os.path as osp
import numpy as np
import sys
import matplotlib.pyplot as plt

파일에 저장된 데이터 읽어오기¶

In [2]:

G = nx.DiGraph()

# 실습에 필요한 데이터셋을 읽어서 저장합니다.
path_v2n = '../실습코드/data/others/vertex2name.txt'
path_edges = '../실습코드/data/others/edges.txt'

# keyword : deep_learning.txt (딥러닝), lee.txt (이순신), bong.txt(봉준호)
path_keyword = '../실습코드/data/lab/lab3/deep_learning.txt'

# 하이퍼링크의 정보를 저장
f = open(path_edges)
for line in f:
    v1, v2 = map(int, line.split())
    G.add_edge(v1, v2)

n2v = {}
v2n = {}
f = open(path_v2n,encoding='utf-8')
for line in f:
    v, n = line.split()
    v = int(v)
    n = n.rstrip()
    n2v[n] = v
    v2n[v] = n

# keyword로 넣는다.
node_key = []
f = open(path_keyword)
for line in f:
    v = line.rstrip()
    v = int(v)
    node_key.append(v)

주어진 검색어가 포함된 문서들로 구성된 부분 그래프(Subgraph)를 구성한다.¶

In [3]:

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

• node_key에 포함된 노드들만 연결 간선을 나타내는 subgraph로 나타냄

In [4]:

node_key

Out[4]:

[2052588,
 2518945,
 2921587,
 2566919,
 2534664,
 2300273,
 1986247,
 2432258,
 2417705,
 283089,
 2722646,
 2596258,
 1994735]

In [5]:

H.nodes

Out[5]:

NodeView((2518945, 2432258, 2596258, 2566919, 2534664, 1986247, 2417705, 2052588, 1994735, 2300273, 283089, 2722646))

• 전체 graph에 node_key에 해당하지 않는 노드가 1개 있어서 H graph에는 node가 12개 나온다.

In [6]:

H.edges

Out[6]:

OutEdgeView([(2518945, 1994735), (2432258, 2432258), (2596258, 1994735), (2566919, 2566919), (2534664, 2534664), (1994735, 1994735), (283089, 283089)])

In [7]:

print(nx.info(H))

Name: 
Type: DiGraph
Number of nodes: 12
Number of edges: 7
Average in degree:   0.5833
Average out degree:   0.5833

구성된 부분그래프(Subgraph)에서 페이지랭크를 수행하여 문서 별 점수를 계산한다.¶

In [8]:

# subgraph H에 대해서 pagerank 알고리즘을 시행합니다.
print("###### PageRank Algorithm ######")
pr = nx.pagerank(H, alpha = 0.9)                                                              # 페이지랭크 알고리즘을 시행합니다. alpha는 페이지랭크의 damping parameter를 의미합니다.
res = [key for (key, value) in sorted(pr.items(), key=lambda x:x[1], reverse=True)]           # 페이지랭크 알고리즘으로 검색한 결과를 ranking에 따라 sorting하고 출력해줍니다.
for item in res[:10]:
    print(v2n[item])

###### PageRank Algorithm ######
딥러닝
OpenCV
이스트소프트
인공지능인문학
미분기하학
PyTorch
라온피플
자동긴급제동장치
케플러-90i
T2d

In [9]:

pr

Out[9]:

{2518945: 0.013333536337298328,
 2432258: 0.13333318833050117,
 2596258: 0.013333536337298328,
 2566919: 0.13333318833050117,
 2534664: 0.13333318833050117,
 1986247: 0.013333536337298328,
 2417705: 0.013333536337298328,
 2052588: 0.013333536337298328,
 1994735: 0.3733324923169069,
 2300273: 0.013333536337298328,
 283089: 0.13333318833050117,
 2722646: 0.013333536337298328}