[U] Day 22 - 페이지 랭크 & 전파 모델

[Graph 3강] 검색 엔진에서는 그래프를 어떻게 활용할까?

페이지랭크의 배경

페이지랭크의 정의

페이지랭크의 계산

실습 코드

[Graph 4강] 그래프를 바이럴 마케팅에 어떻게 활용할까?

그래프를 통한 전파의 예시

의사결정 기반의 전파 모형

확률적 전파 모형

바이럴 마케팅과 전파 최대화 문제

실습 코드

Reference

---

[Graph 3강] 검색 엔진에서는 그래프를 어떻게 활용할까?

💡

구글의 검색 알고리즘인 페이지랭크 알고리즘에 대해 알아본다.

페이지랭크의 배경

웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성이 있는 그래프이다. 웹페이지는 정점에 해당하고, 하이퍼링크는 간선에 해당한다.

웹페이지와 하이퍼링크는 방향성이 있는 그래프이다.

구글 이전에는 이런 웹을 거대한 디렉토리로 정리하려는 시도가 있었다. 이는, 웹페이지의 증가에 따라 카테고리의 수와 깊이가 무한정 커지는 문제가 있었다. 또한, 카테고리의 구분이 모호한 경우가 많아 저장이나 검색에 어려움이 존재했다.

웹을 디렉토리로 정리하려고 했던 시도의 예시

검색에 있어서는, 키워드에 의존한 검색 방법을 사용했었다. 웹페이지 내에 해당 키워드의 빈도를 통해 검색을 하는 방법을 의미한다. 이는, 악의적인 페이지 구성 등에 의해 적절한 검색이 방해될 수 있다. 예를 들면, '축구'라는 키워드를 다수 포함한 성인 사이트는 키워드 검색에 의해 검색될 것이다.

페이지랭크의 정의

페이지랭크는 관련성이 높고 신뢰할 수 있는 웹페이지를 검색할 수 있도록 제시된 알고리즘이다. 페이지랭크의 핵심 아이디어는 투표이다. 투표의 주체는 웹페이지이며, 하이퍼 링크를 통해 투표를 진행한다. 하이퍼 링크를 포함한다는 의미는, 관련성이 높고 신뢰할 수 있다는 의미로 이해될 수 있기 때문이다.

kaist 페이지는 kijung 페이지에 투표한다.

단순히 투표의 수로만 계산을 할 경우, 문제가 생길 수 있다. 의도적으로 한 페이지의 링크를 포함한 여러 웹페이지를 개설하는 등으로 웹페이지를 노출시킬 수 있기 때문이다.

SNS에서 사용되는 웹페이지 치팅의 예시

그래프의 비정상적인 형태의 예시

이러한 악용을 막기 위해서 가중 투표의 개념을 도입한다. 신뢰할 수 있는 페이지의 투표에 가중치를 두는 방식으로, 신뢰성과 관련성 모두를 확보하는 것이다.

투표의 관점으로 보았을 때, 페이지랭크는 다음과 같이 해석할 수 있다. 특정 페이지 $j$는 관련성이 높은 페이지에 대해서 자신의 점수를 나누어 투표한다. 특정 페이지 $j$는 다른 페이지들로부터 투표받은 점수를 갖는다. 즉, 페이지랭크의 점수는 $r_j = \sum_i \frac{r_i}{d_{out}(i)}$와 같다.

$r_j = r_i / 3 + r_k / 4$이다.

$r_y = r_y/2+r_a/2$ $r_a = r_y/2 + r_m$ $r_m=r_a/2$

임의 보행의 관점으로도 동일하게 정의할 수 있다. 한 사용자가 $t$시점에 방문한 웹페이지가 $i$일 확률을 $p_i(t)$라고 하면, 다음번에 $j$로 갈 확률은 $p_j(t+1)=\sum_i \frac{p_i(t)}{d_{out}(i)}$가 된다. 이와 같은 과정을 무한히 반복하면, $p(t) = p(t+1) = p$가 된다. 이렇게 수렴한 확률 $p$는 정상 분포이며, 최종적으로 정리하면 위와 동일한 형태의 수식이 된다.$p_j=\sum_i \frac{p_i}{d_{out}(i)}$

즉, 투표 관점이든 임의 보행 관점이든 동일한 해석의 결과가 나오는 것을 알 수 있다.

페이지랭크의 계산

페이지랭크 점수는 반봅곱을 사용해 계산하게 된다. 이는 아래와 같은 순서로 이루어진다.

1. 각 웹페이지 $i$의 Score $r_i^{(0)}$를 모두 $\frac{1}{num}$으로 초기화한다. (num은 웹페이지의 갯수)

2. $r_j^{(t+1)} = \sum_i \frac{r_i^{(t)}}{d_{out}(i)}$ 식을 이용해 각 웹페이지의 Score를 갱신한다.

3. 페이지랭크 Score가 수렴했을 경우 종료하고, 아닌 경우 2번으로 돌아간다.

페이지랭크 계산의 예시

위와 같이 페이지랭크를 정의할 경우, 반복곱이 수렴하지 않는 문제가 생길 수 있다. 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합이 있는 경우이며, 이를 스파이더 트랩이라고 한다.

홀수와 짝수가 번갈아가며 같은 값을 지닌다.

스파이더 트랩의 시각화 예시

또한, 합리적이지 않은 점수로 수렴될 가능성이 있다. 들어오는 간선은 있지만 나가는 간선이 없는 경우이며, 이를 막다른 정점의 문제라고 한다.

Score가 0으로 수렴한다.

막다른 정점의 시각화 예시

위와 같은 문제를 방지하기 위해서, Teleport개념을 도입한다. 규칙은 다음 사진과 같다.

Teleport 개념이 추가된 페이지랭크 계산 순서의 예시

수식적으로는 다음과 같이 계산된다.

Teleport 개념이 추가된 페이지랭크의 수식 $\alpha$는 대체로 0.8의 비율로 사용된다.

이를 통해서, 위에서 제시된 문제를 해결할 수 있다.

스파이더 트랩과 막다른 정점이 있지만, 점수가 합리적으로 수렴한다. C는 들어오는 간선이 1개이지만, Score가 높은 B로부터 투표를 받는다.

실습 코드

PageRank

---

[Graph 4강] 그래프를 바이럴 마케팅에 어떻게 활용할까?

💡

전파의 규칙과 모형을 통해 전파 모델링을 하고, 전파 최대화 문제에 대해 알아본다.

그래프를 통한 전파의 예시

전파란 특정한 정보나 증상 등이 여러 정점에 동일하게 나타나도록 하는 현상을 의미한다. 예시를 통해 알아보자.

SNS를 통해서 정보나 행동이 전파될 수 있다.

SNS를 통한 행동 전파의 예시 1

SNS를 통한 행동 전파의 예시 2

SNS를 이용한 정보 전파의 예시

SNS를 통한 정보와 행동 전파의 예시

네트워크 상에서는 일부 장비의 고장으로, 다른 장비에 과부하를 초래하고 고장을 전파할 수 있다.

장비 고장 전파의 예시

정전 전파의 예시

실제 사회에서도 질병과 같은 증상이 전파될 수 있다.

코로나-19, 메르스, 사스 등

질병의 전파 예시

이와 같은 전파를 체계적으로 이해하고 대처하기 위해서 수학적 모형화가 필요하다.

의사결정 기반의 전파 모형

의사결정 모형은 주변 노드의 의사결정을 고려하여 각자의 의사결정을 내리는 형태를 모델링한다. 가장 간단한 형태의 의사결정 모델인 선형 임계치 모형을 알아보자.

노드 $u$와 $v$가 연결되어 있을 때, 동일한 선택을 했을 경우에만 편익이 발생한다. 빨간색을 선택할 경우 a만큼, 파란색을 선택할 경우 b만큼의 편익이 발생한다고 가정해보자.

노드 $u$는 $v$와 같은 것을 선택하고자 하며, $v$도 동일하다.

노드 $u$가 여러 이웃을 가지는 경우에는 각각으로부터 얻는 편익을 계산하게 된다.

$u$는 3b 혹은 2a 중에 하나의 편익만 얻을 수 있다.

노드 $u$를 기준으로, a를 선택한 이웃의 비율을 $p$로 정의하면, b를 선택한 이웃의 비율은 $(1-p)$가 된다. 일반화하여 표현했을 때, $u$가 얻을 수 있는 편익은 $ap$ 혹은 $b(1-p)$이다. $u$가 a를 선택할 합리적인 조건은 $ap > b(1-p)$인 것이다. 이를 정리하면 $p > \frac {b} {a+b}$인 경우에, a를 선택한다고 할 수 있다. 이 $\frac {b} {a+b}$를 임계치라고 칭한다.

선형 임계치 모형에서의 전파를 알아보자. 주변과 관계 없이 a를 택하는 시드집합이 있다고 가정하고, 임계치는 55%를 가정할 경우 모형의 전파는 다음과 같다.

2개의 시드집합을 가정한다.

주변 노드중 4개는 임계치에 따라 a를 선택한다.

추가로 1개의 노드가 임계치에 따라 a를 선택한다.

두 단계 이후 모든 전파가 완료된다.

확률적 전파 모형

질병과 같은 전파 과정은 의사결정과 무관하게 이루어진다. 이는 확률적 과정으로 위와는 다른 모델링이 필요하다. 확률적 전파 모형 중 가장 간단한 형태의 독립 전파 모형에 대해 알아보자.

독립 전파 모형은 노드 $u$가 감염되었을 때, $v$를 감염시킬 확률을 간선의 가중치 형태로 표현한다. 즉, 각 정점 $u$가 감염될 때마다 각 이웃 $v$는 $p_{uv}$확률로 전염된다. 최초 감염자에 해당하는 시드 집합으로부터 전염이 시작되고, 전염된 노드로부터 다시 전염이 일어나는 형태로 반복 수행된다.

확률적 전파모형의 시각화 예시

이때, 서로 다른 이웃의 전염 확률은 각각 독립적이라고 가정한다. $p_{uv}$와 $p_{uw}$는 서로 독립적이며, $p_{uv}$와 $p_{wv}$는 독립적이라고 가정하는 것이다. 또한, 감염자는 지속적으로 감염상태임을 가정한다. 감염자의 회복까지 고려한 SIS나 SIR과 같은 다른 전파모형도 존재한다.

바이럴 마케팅과 전파 최대화 문제

바이럴 마케팅이란, 상품에 대한 소비자들의 긍정적 소문을 기대하는 마케팅 기법이다. 바이럴 마케팅은 이 소문의 시작점에 큰 영향을 받기 때문에, 어디서부터 마케팅을 시작할지에 큰 관심을 가진다.

앞서 의사결정 모형에서 살펴보았듯, 2개의 시드집합으로부터 총 9개의 노드가 변경되는 것을 볼 수 있었다. 하지만, 다른 시드집합을 설정할 경우 완전히 다른 결과를 얻을 수 있다.

위 시각화 예시와 같이, 바이럴 마케팅에서 시드 집합의 설정은 매우 중요하다.

위와 같이 그래프, 전파 모형, 시드 집합의 크기가 주어졌을 때 전파를 가장 크게 만드는 문제를 전파 최대화 문제라고 부른다. 전파 최대화 문제를 해결할 가장 기본적인 아이디어는 모든 경우의 수를 계산하는 것이다. 하지만, 이와 같은 모든 경우의 수 계산은 Np-hard의 문제이다. 예를 들어, 정점이 10000개, 시드 집합이 10개인 경우만 고려하더라도, $_{10000}C_{10}$으로 매우 큰 경우의 수가 되는 것을 알 수 있다.

10000개의 정점과 10개의 시드 집합은 비교적 작은 조건임에도, 계산이 불가능하다.

모든 경우의 수를 계산하는 대신, 정점 중심성을 이용할 수 있다. 즉, 시드 집합의 크기가 $k$로 고정되어 있을 때, 정점의 중심성이 높은 순으로 $k$개를 고르는 간단한 방법이다. 정점 중심성의 기준으로 사용할 수 있는 것으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있다. 간단한 방법인만큼, 최고의 시드 집합을 찾는다는 보장은 없다.

연결성이 가장 높은 노드를 선별한다.

탐욕 알고리즘을 이용해 조금 더 안정적으로 문제를 해결할 수 있다. 탐욕 알고리즘은 다음과 같이 동작한다.

이와 같은 과정을 $k$번 수행하여, $k$개의 시드 집합을 구성한다.

탐욕 알고리즘의 장점은, 독립 전파 모형의 경우 최저 성능이 수학적으로 보장되어 있다.

탐욕 알고리즘의 최저 성능은 수학적으로 보장되어 있다.

실습 코드

Influence Model

---

Reference

Explain Page Rank I

Explain Page Rank II

Maximization of Cascade Paper

Uploaded by Notion2Tistory v1.1.0