Ai tech Day22

Lee·2021년 2월 23일

네이버 커넥트 부스트 캠프

페이지 랭크

페이지랭크의 배경

웹과 그래프

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

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

구글 이전의 검색 엔진

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

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

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

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

Q. 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 어떻게 찾을 수 있을까요?
A. 구글의 창업자인 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)은 The PageRank Citation Ranking: Bringing Order to the Web 라는 제목의 논문을 통해 이 질문에 답합니다.

페이지랭크의 정의

투표 관점

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

투표의 주체는 바로 웹페이지입니다.
웹페이지는 하이퍼링크를 통해 투표를 합니다.

사용자 키워드를 포함한 웹페이지들을 고려합시다. 웹페이지 $u$ 가 $v$ 로의 하이퍼링크를 포함한다면? $u$ 의 작성자가 판단하기에 $v$ 가 관련성이 높고 신뢰할 수 있다는 것을 의미합니다. 즉, $u$ 가 $v$ 에게 투표했다고 할 수 생각할 수 있습니다.

들어오는 간선이 많을 수록 신뢰할 수 있다는 뜻입니다.

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

Q. 그런데 들어오는 간선의 수를 세는 것만으로 충분할까요?
A. 아닙니다. 악용될 소지가 있습니다.

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

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

A. 이런 악용에 의한 효과를 줄이기 위해, 페이지랭크에서는 가중 투표를 합니다. 즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주합니다. 반면 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주합니다. 악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방법입니다.

Q. 잠깐, 관련성과 신뢰성은 저희가 투표를 통해 측정하려는 것 아니었나요? 출력을 입력으로 사용하자는 이야기처럼 들리는데요?
A. 그렇습니다. 재귀(Recursion), 즉 연립방정식 풀이를 통해 가능합니다.

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

각 웹페이지는 각각의 나가는 이웃에게 $\operatorname{\cfrac{자신의 \;페이지랭크 \;점수}{나가는이웃의수}}$ 만큼의 가중치로 투표를 합니다.

오른쪽 예시에서 웹페이지 $j$ 는 웹페이지 $x$ , $y$ , $z$ 에게 각각 가중치 $\cfrac{r_j}{3}$ 으로 투표를 합니다. $r_j$ 는 웹페이지 $j$ 의 페이지랭크 점수를 의미합니다.

각 웹페이지의 페이지랭크 점수는 받은 투표의 가중치 합으로 정의됩니다. 오른쪽 예시에서 웹페이지 $j$ 의 페이지랭크 점수 $r_j$ 는 다음과 같습니다.

r_j = r_i / 3 + r_k / 4

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

r_j = \sum_{i\in N_{in}(j)}\cfrac{r_i}{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개이므로 연립방정식을 통해 풀 수 있습니다.

임의 보행 관점

페이지랭크는 임의 보행(RandomYWalk)의 관점에서도 정의할 수 있습니다.

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

웹서퍼가 𝑡번째 방문한 웹페이지가 웹페이지 𝑖일 확률을 $p_i(t)$ 라고 합시다.
그러면 $p(t)$ 는 길이가 웹페이지 수와 같은 확률분포 벡터가 됩니다.

그러면 아래 식이 성립합니다.

p_j(t + 1) = \sum_{i \in N_{in}(j)} \cfrac{p_i(t)}{d_{out}(i)}

웹서퍼가 이 과정을 무한히 반복하고 나면, 즉 $t$ 가 무한히 커지면 확률 분포 $p(t)$ 는 수렴하게 됩니다. 다시 말해 $p(t) = p(t + 1)=p$ 이 성립하게 됩니다.
수렴한 확률 분포 $p$ 는 정상 분포(Stationary Distribution)라고 부릅니다. 그러면 앞서 소개한 수식을 아래와 같이 바꿀 수 있습니다.

p_j(t + 1) = \sum_{i \in N_{in}(j)} \cfrac{p_i(t)}{d_{out} (i)} \; \; \; \rightarrow \; \; \;p_j=\sum_{i \in N_{in}(j)} \cfrac{p_i}{d_{out}(i)}

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

투표 관점에서 정의한 페이지랭크 점수 $r$

r_j = \sum_{i\in N_{in}(j)}\cfrac{r_i}{d_{out}(i)}

임의 보행 관점에서 정의한 정상 분포 $p$

p_j=\sum_{i \in N_{in}(j)} \cfrac{p_i}{d_{out}(i)}

페이지랭크의 계산

반복곱

페이지랭크 점수의 계산에는 반복곱(PowerYIteration)을 사용합니다.

반복곱은 다음 세 단계로 구성됩니다.

(1) 각 웹페이지 $i$ 의 페이지랭크 점수 $r_i^{(0)}$ (0번째 iteration) 를 동일하게 $\operatorname{\cfrac{1}{웹페이지의 수}}$ 로 초기화합니다.

(2) 아래 식을 이용하여 각 웹페이지의 페이지랭크 점수를 갱신합니다.

r_j^{(t+1)} = \sum_{i\in N_{in}(j)}\cfrac{r_i^{(t)}}{d_{out}(i)}

(3) 페이지랭크 점수가 수렴하였으면 종료합니다. 아닌 경우 (2)로 돌아갑니다.

문제점과 해결책

앞선 예시에서는 반복곱이 잘 동작하는 것을 알겠습니다 그런데…

Q1. 반복곱이 항상 수렴하는 것을 보장할 수 있나요?
A1. 정답은 ‘아니오’ 입니다.

아래 예시에서 페이지랭크 점수는 수렴하지 않습니다.

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

Q2. 반복곱이 '합리적인' 점수로 수렴하는 것을 보장할 수 있나요?
A2. 정답은 '아니오' 입니다.

아래 예시에서 페이지랭크 점수는 0으로 수렴합니다.

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

문제 해결을 위해 순간이동(Teleport)을 도입합니다.

임의 보행 관점에서, 웹을 서핑하는 웹서퍼의 행동을 다음과 같이 수정합니다.
(1) 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동 합니다.
(2) 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 $\alpha$ 인 동전을 던집니다.
(3) 앞면이라면, 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭합니다.
(4) 뒷면이라면, 임의의 웹페이지로 순간이동 합니다.

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

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

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

r_j = \sum_{i\in N_{in}(j)}(\alpha \cfrac{r_i}{d_{out}(i)}) + (1 - \alpha) \cfrac{1}{|V|}

$|V|$ 는 전체 웹페이지의 수를 의미합니다.
파란색 부분은 하이퍼링크를 따라 정점 $j$ 에 도착할 확률을 의미합니다.
빨간색 부분은 순간이동을 통해 정점 $j$ 에 도착할 확률을 의미합니다.

그래프와 바이럴 마케팅

그래프를 통한 전파의 예시

그래프를 통한 정보의 전파

온라인 소셜 네트워크를 통해 다양한 정보가 전파됩니다.

2011년 스페인의 15M 운동에 대한 정보는 트위터를 통해 전국적으로 알려졌습니다. 덕분에 주류 언론이 침묵하는 상황에서도, 시민들이 정부의 부정부패에 맞서 연대할 수 있었습니다.

그래프를 통한 행동의 전파
아이스 버킷 챌린지, 펭귄 문제 등이 대표적인 예시입니다.

그래프를 통한 고장의 전파

컴퓨터 네트워크에서의 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수 있습니다. 일부 장비의 고장이 다른장비의 과부화로 이어지기 때문입니다.

그래프를 통한 질병의 전파

사회라는 거대한 소셜 네트워크를 통한 질병의 전파도 빠뜨릴 수 없습니다. 코로나-19, 메르스, 사스 등이 그 예시입니다.

전파 과정은 다양할 뿐 아니라 매우 복잡합니다. 이를 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요합니다.

의사결정 기반의 전파 모형

언제 의사 결정 기반의 전파모형을 사용할까?

1970년 대에는 VHS와 Betamax라는 호환되지 않는 두 종류의 비디오 유형이 있었습니다.

어떤 유형의 비디오 플레이어를 구매하시겠습니까?
의사 결정을 위해 어떤 정보를 참고해야 할까요?

그러면 카카오톡과 라인 중에 어떤것을 사용하시고 있나요? 왜 그런 결정을 하셨나요?

두 경우 모두 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미칩니다.

친구들이 대부분 라인을 쓴다면 카카오톡을 사용하는 것이 불편합니다.
친구들이 대부분 VHS유형을 쓴다면 같은 유형을 써야 서로 비디오를 빌려줄 수 있습니다. 이렇듯 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용합니다.

선형 임계치 모형

이 상황을 수학적으로 추상화 해봅시다.

친구 관계의 두 사람 $u$ 와 $v$ 를 가정합시다.
둘은 두 개의 호환되지 않는 기술 $A$ 와 $B$ 중에서 하나를 선택합니다.

둘 모두 $A$ 기술을 사용할 경우, 행복이 $a$ 만큼 증가합니다.
둘 모두 $B$ 기술을 사용할 경우, 행복이 $b$ 만큼 증가합니다.
하지만 둘이 서로 다른 기술을 사용할 경우 행복이 증가하지 않습니다.

소셜 네트워크를 고려해봅시다.

우리는 동시에 여러 사람과 친구 관계를 맺습니다.
각각 의친구, 즉 소셜 네트워크 상의 이웃 사이에서 발생하는 행복을 고려해야 합니다.

아래 예시에서 $u$ 가 $A$ 를 선택할 경우 행복이 $2a$ 만큼 증가합니다.
아래 예시에서 $u$ 가 $B$ 를 선택할 경우 행복이 $3b$ 만큼 증가합니다.

각자가 행복이 최대화 되는 선택을 한다고 가정해봅시다.

만약 $2a$ > $3b$ 라면 $u$ 는 $A$ 를 택할 것입니다.
반면 $2a$ < $3b$ 라면 $u$ 는 $B$ 를 택할 것입니다.
편의상 $2a$ = $3b$ 라면 $u$ 는 $B$ 를 택한다고 합시다.

좀 더 일반화 해봅시다.

$p$ 비율의 이웃이 $A$ 를 선택했다고 해봅시다.
즉, $1-p$ 비율의 이웃이 $B$ 를 선택했습니다.

언제 $A$ 를 선택할까요?
$ap$ > $b(1-p)$ 일 때입니다.

정리하면 $p$ > $\cfrac{b}{a+b}$ 일 때입니다. 편의상 $\cfrac{b}{a+b}$ 를 임계치 $q$ 라고 합시다.

이 모형을 선형 임계치 모형(Linear Threshold Model)이라고 합니다.

각 정점은 이웃 중 $A$ 를 선택한 비율이 임계치 $q$ 를 넘을 때만 $A$ 를 선택합니다.

이 모형은 전부 $B$ 를 사용하는 상황을 가정합니다.
그리고 처음 $A$ 를 사용하는 얼리 어답터들을 가정합니다.
시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 $A$ 를 고수한다고 가정합시다.

예시를 고려합시다.

임계치 $q$ 는 55%를 가정합시다.

$u$ 와 $v$ 가 시드 집합인 상황입니다.
$u$ 와 $v$ 의 선택을 고려하여 각자 다시 기술을 선택합니다.

추가로 4명이 $A$ 를 선택했습니다.
이웃 중 $A$ 를 선택한 비율이 임계치 55% 를 넘었기 때문입니다.

추가로 1명이 $A$ 를 선택했습니다.
이웃 중 $A$ 를 선택한 비율이 임계치 55% 를 넘었기 때문입니다.

전파가 멈추었습니다.

$A$ 를 택하지 않은 정점 중 이웃 중 $A$ 를 선택한 비율 이 임계치 55%를 넘는 경우가 없기 때문입니다.

확률적 전파 모형

언제 확률적 전파 모형을 사용할까?

코로나의 전파 과정을 수학적으로 추상화해봅시다.

의사결정 기반 모형은 적합하지 않습니다. 누구도 코로나에 걸리기로
‘의사결정’을 내리는 사람은 없기 때문입니다.

코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야합니다.

독립적 전파 모형

방향성이 있고 가중치가 있는 그래프를 가정합시다.
각 간선 $(u,v)$ 의 가중치 $p_{uv}$ 는 $u$ 가 감염되었을 때
(그리고 $v$ 가 감염되지 않았을 때) $u$ 가 $v$ 를 감염시킬 확률 에 해당합니다.
즉, 각 정점 $u$ 가 감염될 때마다, 각 이웃 $v$ 는 $p_{uv}$ 확률로 전염됩니다.

서로 다른 이웃이 전염되는 확률은 독립적입니다.
$u$ 가 감염되었을 때 $u$ 가 $v$ 를 감염시킬 확률은
$u$ 가 감염되었을 때 $u$ 가 $w$ 를 감염시킬 확률과 독립적입니다.

$u$ 가 감염되었을 때 $u$ 가 $v$ 를 감염시킬 확률은
$w$ 가 감염되었을 때 $w$ 가 $v$ 를 감염시킬 확률과 독립적입니다.

모형은 모델은 최초 감염자들로부터 시작합니다.

이전 모형과 마찬가지로 첫 감염자들을 시드집합(Seed Set) 이라고 부릅니다.

각 최초 감염자 $u$ 는, 각 이웃 $v$ 에게 $p_{uv}$ 확률로 병을 전파합니다.
위 과정을 새로운 감염자 각각에게 반복합니다.
위 과정을 새로운 감염자 각각에게 반복합니다.
...
더 이상 새로운 감염자가 없으면 종료합니다.

감염자는 계속 감염자 상태로 남아있는 것을 가정합니다.
감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파모형도 있습니다.

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

바이럴 마케팅이란?

바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법입니다.

바이럴 마케팅이 효과적이기 위해서는 소문의 시작점이 중요합니다.
시작점이 어디인지에 따라서 입소문이 전파되는 범위가 영향을 받기 때문입니다.
소셜인플루언서(Social Influencer)들이 높은 광고비를 받는 이유입니다.

시드 집합의 중요성

대표적인 소셜인플루언서에는 영국 윌리엄 왕자의 부인 케이트 미들턴이 있습니다. ‘미들턴 효과’라는 말이 생겨날 정도입니다.

앞서 소개한 전파 모형들에서도 시드 집합 이 전파 크기에 많은 영향을 미칩니다.

선형 임계치 모형의 예시에서 시드 집합 으로 $u$ 와 $v$ 를 선택했을 때, 총 9 명이 $A$ 를 선택했습니다.

시드 집합 으로 $x$ 와 $y$ 를 선택했다면, 추가 전파는 발생하지 않습니다. 2 명만이 $A$ 를 선택했습니다.

전파 최대화 문제

시드 집합을 우리가 선택할 수 있다면, 누구를 선택하시겠습니까?

그래프, 전파모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다.

전파 모형으로는 앞서 배운 선형 임계치 모형, 독립 전파 모형을 포함 다양한 모형을 고려할 수 있습니다.

전파 최대화 문제는 방대한 그래프, 즉 소셜 네트워크로부터 '케이트 미들턴' 같이 영향력 있는 시드 집합을 찾아내는 문제입니다.

전파 최대화 문제는 굉장히 어려운 문제입니다.

그래프에 $|V|$ 개의 정점이 있을 경우, 시드 집합의 크기를 $k$ 개로 제한하더라도 경우의 수는 ${|V| \choose k}$ 개 입니다.

정점이 10,000개, 시드 집합의 크기를 10으로 고정합시다.
경우의 수는 무려 2,743,355,077,591,282,538,231,819,720,749,000 개 입니다.

이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명되었습니다.

최고의 시드 집합을 찾는 것은 포기합시다.

정점 중심성 휴리스틱

휴리스틱이란 실험적으로는 잘 동작할 수 있지만 이론적으로는 그 정확도에 대해서 어떤 보장도 할 수 없는 알고리즘입니다.

대표적 휴리스틱으로 정점의 중심성(Node Centrality)을 사용합니다.

즉, 시드 집합의 크기가 $k$ 개로 고정되어 있을 때 정점의 중심성이 높은 순으로 $k$ 개 정점을 선택하는 방법입니다.

정점의 중심성으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있습니다.

연결 중심성: 연결성이 높은 정점들이 높은 중심성을 갖는다.
근접 중심성: 다른 정점들로의 평균거리를 측정한 뒤 그 평균거리가 작은 정점들이 높은 근접 중심성을 갖는다.
매개 중심성: 정점간 최단 경로를 고려한다. 그리고 최단 경로에 많이 놓이는 정점일 수록 많은 정점쌍을 연결하는 역할을 해서 매개 중심성이 높다.

합리적인 방법이지만 최고의 시드 집합을 찾는다는 보장은 없습니다.

탐욕 알고리즘

탐욕 알고리즘(Greedy Algorithm) 역시 많이 사용됩니다.

탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택합니다. 정점의 집합을 $\{1,2,\dots,|V|\}$ 라고 할 경우 구체적인 단계는 다음과 같습니다.

집합 $\{1\},\{2\},\dots,\{|V|\}$ 를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다. 이때 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균값을 사용합니다. 뽑힌 집합을 $\{x\}$ 라고 합시다.

집합 $\{x,1\},\{x,2\},…,\{x,|V|\}$ 를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다. 뽑힌 집합을 $\{x,y\}$ 라고 합시다.

집합 $\{x,y,1\},\{x,y,2\},…,\{x,y,|V|\}$ 를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다. 뽑힌 집합을 $\{x,y,z\}$ 라고 합시다.

위 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복합니다.

즉, 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고 근시안적으로 최초 전파자를 선택하는 과정을 반복합니다.

탐욕 알고리즘은 얼마나 정확한가요?
독립 전파 모형의 경우, 이론적으로 정확도가 일부 보장됩니다.
즉 입력 그래프와 무관하게 다음 부등식이 성립합니다.

탐욕 알고리즘으로 찾은 시드 집합에 의한 전파의 (평균) 크기
$\geq (1-\cfrac{1}{e})$ 최고의 시드 집합에 의한 전파의 (평균) 크기
$\approx 0.632$ 최고의 시드 집합에 의한 전파의 (평균) 크기

Lee

초보 개발자입니다

이전 포스트

Ai tech Day21

다음 포스트