📌 ML With Graphs

---

📄 Page Rank

페이지랭크(PageRank)는 월드 와이드 웹과 같은 하이퍼링크 구조를 가지는 문서에 상대적 중요도에 따라 가중치를 부여하는 방법으로, 웹사이트 페이지의 중요도를 측정하기 위해 구글 검색에 쓰이는 알고리즘이다.

✏️ 이전엔 무엇이 있었을까?

✅ 디렉토리

가장 간단한 방법은 웹을 거대한 디렉토리로 정리하는 것이다. 하지만 이것의 문제점은 웹페이지의 수가 증가함에 따라 카테고리의 수 와 깊이가 무한정 커질 수 있으며 카테고리 구분이 모호한 경우가 많아 저장과 검색에 어려움이 있을 수 있다는 것이다.

✅ 키워드

사용자가 입력한 키워드에 대해 해당 키워드를 여러번 포함한 웹페이지를 반환하는것이다. 하지만 이것의 문제점은 악의적인 페이지에 취약하다는 것이다. 가령 성인사이트에 "축구" 라는 키워드를 보이지 않도록 여러번 포함하게 되면 "축구"를 검색했을 때 해당 성인사이트가 결과로 나올 수 있다.

✏️ 그래서 페이지 랭크가 뭐지?

페이지 랭크 의 핵심 아이디어는 투표(voting) 이다. 가령, 웹페이지 A 가 웹페이지 B로의 하이퍼링크를 포함하고 있는 상황을 생각해보면, A가 판단하기엔 B가 관련성이 높고 신뢰성이 높다고 생각할 수 있다. 즉, 웹페이지가 투표의 주체가 되어 하이퍼링크를 통해 관련성과 신뢰도가 높은지를 투표하는 것이며, "들어오는 링크가 많을 수록 신뢰할수 있다" 라는 것을 의미한다. 하지만 이것의 문제는 웹페이지를 여러개 만들어서 링크의 수를 부풀려 관련성과 신뢰도를 높일수 있다는 것이다. 그래서 이런 악용을 줄이기 위해서 페이지 랭크에서는 단순 투표가 아닌 가중투표를 한다. 즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주하여 가중치를 높게 부여하고 반면 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주하여 가중치를 낮게 부여한다.

✏️ 페이지 랭크 점수는 어떻게 정의할까?

웹페이지 j 의 페이지 랭크 점수 $r_j$ 란 측정하려는 웹페이지의 관련성 및 신뢰도이다. 이때, 두가지 관점 voting,random walk 으로 $r_j$ 를 정의할 수 있다.

✅ Voting

웹페이지 j 는 각각의 나가는 이웃 $N_{out}$ 에게 $\frac{r_j}{|N_{out}|}$ 만큼의 가중치를 부여한다.

위의 예시를 바탕으로 웹페이지 j의 페이지랭크 점수 $r_j$ 는 다음과 같다.

주목할것은 페이지랭크 점수 $r_j$ 를 얻기 위해선 다른 페이지 랭크 점수 $r_i$,$r_k$ 가 필요하다는 것이다. 즉 , 재귀적으로 값을 얻어야 한다는 것인데 구체적인 계산 방법은 다음 에서 살펴보도록 한다.

✅ Random Walk

Random Walk 란 균일한 확률로 한 점에서 임의의 점으로 이동하는 것을 말한다. 즉, 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 이동한다. 이해를 돕기 위해 notation 을 정의 하면,

• $p_i(t)$ : 웹서퍼가 t번째에 웹페이지 i를 방문할 확률
• $p(t)=(p_1(t),p_2(t),\dots,p_n(t))$ : 길이가 웹페이지 수와 같은 확률분포 벡터

이다. 그렇다면 t번째 방문한 웹페이지 i 에서 t+1 번째 웹페이지 j를 방문할 확률은 다음과 같이 정의된다.

이때, t가 무한히 커지면 확률분포 $p(t)$ 는 $p$ (Stationary Distribution) 로 수렴하게 된다.(하지만 어떤 문제에 의해서 수렴하지 못할수도 유일하지 않을수도 있는데, 이 부분에 대해선 다음에서 살펴보도록 한다.) 즉, $p(t)=p(t+1)=p$ 가 성립하게 된다.(수학적 증명은 여기 를 참고하도록 한다.) 그러면 위의 식은 다음과 같이 정의할 수 있다.

따라서 voting 관점에서 정의한 페이지 랭크 점수 $r_j$ 는 random walk 관점에서 정의한 stationary distribution $p$ 와 동일하다.

✏️ 어떻게 계산할까?

앞에서 각 페이지 랭크 점수를 구하기 위해선 다른 페이지 랭크 점수가 필요하기 때문에 재귀적으로 값을 구해야한다고 언급했었다. 위의 예시를 바탕으로 그 과정을 살펴보면, 웹페이지 a,y,m 3개가 존재하기 때문에 식이 3개인 연립방정식을 통해 다음과 같이 구할수 있다.

좀 더 구체적으로 살펴보면 페이지랭크점수 계산에는 power iteration을 사용한다. power iteration 은 다음 세 단계로 분류할 수 있다.

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

2. $r_j^{(t+1)}=\sum_{i\in N_{in}(j)}\frac{r_i^{(t)}}{d_{out}(i)}$ 를 이용하여 각 웹페이지의 페이지랭크 점수를 갱신한다.

3. 페이지 랭크 점수가 수렴 하였으면 종료하고 아닌 경우 (2)의 과정을 반복한다.

위의 과정을 예시를 통해 순차적으로 살펴보면, 처음에는 각 페이지 랭크 점수를 $\frac{1}{3}$ 으로 초기화 한다.

반복	0
$r_y$	$\frac{1}{3}$
$r_a$	$\frac{1}{3}$
$r_m$	$\frac{1}{3}$

이후 페이지 랭크 점수가 수렴할때 까지 페이지 랭크점수를 갱신한다.

반복	0	1	2	3	$\dots$	t	t+1
$r_y$	$\frac{1}{3}$	$\frac{1}{6}+\frac{1}{6}=\frac{1}{3}$	$\frac{5}{12}$	$\frac{9}{24}$	$\dots$	$\textcolor{red}{\frac{6}{15}}$	$\textcolor{red}{\frac{6}{15}}$
$r_a$	$\frac{1}{3}$	$\frac{1}{6}+\frac{1}{3}=\frac{3}{6}$	$\frac{1}{3}$	$\frac{11}{24}$	$\dots$	$\textcolor{red}{\frac{6}{15}}$	$\textcolor{red}{\frac{6}{15}}$
$r_m$	$\frac{1}{3}$	$\frac{1}{6}$	$\frac{3}{12}$	$\frac{1}{6}$	$\dots$	$\textcolor{red}{\frac{3}{15}}$	$\textcolor{red}{\frac{3}{15}}$

✏️ 문제점은 무엇일까?

앞서 페이지 랭크 점수를 power iteration을 통해 계산해 봤다. 하지만 두가지의 의문점이 존재하는데,

1. 항상 수렴하는가?

2. 합리적인 점수로 수렴하는가?

이다.

✅ 항상 수렴하는가?

위의 예시와 같이 들어오는 링크는 있지만 나가는 링크가 없는 정점 집합인 스파이더 트랩(Spider Trap) 이 존재한다면 페이지 랭크 점수는 수렴하지 않게 된다.

✅ 합리적인 점수로 수렴하는가?

위의 예시와 같이 들어오는 링크는 있지만 나가는 링크가 없는 막다른 정점(Dead End) 가 존재한다면 0 수렴하게 된다.

✏️ 해결방법은 무엇일까?

Random Walk 관점에서의 페이지랭크 점수를 다시 한번 살펴보면, 웹서퍼는 현재 있는 페이지에서 다른 페이지로 이동할때 확률적으로 움직인다. 이때, 현재 페이지에서 다른 웹페이지로 이동하는 확률은 각 페이지마다 다를것이다. 여기서, 현 시점의 페이지에서 다음 시점의 페이지로 이동하게 될 확률을 transition probability라 부른다. 그래서 각 시점의 transition probability를 곱해나가면서 시간이 충분히 흐르게 되면 어떠한 확률 분포 $p$ 즉 stationary distribution 에 수렴하게 된다. 하지만 위에서 살펴본 spider trap, dead end 와 같은 상황들이 $p$ 가 존재하지 않을수도 혹은 유일하지 않을수도 있는 문제를 만들게 된다. 따라서 이러한 문제를 해결하기 위해 Teleport 개념을 도입하여, 웹서퍼의 행동을 다음과 같이 수정한다.

1. 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 teleport 한다.

2. 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 $\alpha$(Damping Factor) 인 동전을 던진다.

3. 앞면 이라면, 하이퍼링크중 하나를 균일한 확률로 선택해 클릭한다.

4. 뒷면 이라면, 임의의 웹페이지로 teleport 한다.

위의 수정사항을 통해 페이지 랭크 점수 계산은 다음과 같이 정의 된다.

1. 자신을 포함한 각 dead end 에서 모든 다른 정점으로 가는 링크를 추가한다.

2. 아래 수식을 이용하여 power iteration 을 수행한다.

이때,$|V|$ 는 전체 웹페이지의 수 / 파란색 부분은 하이퍼링크를 따라 웹페이지 j 에 도착할 확률 / 빨간색 부분은 teleport를 통해 웹페이지 j에 도착할 확률 을 의미한다.

위의 수식을 자세히 살펴보면, 하이퍼링크가 없는 경우 파란색 은 0이되어 빨간색 부분만 남게되고 이것은 teleport 를 의미한다. 만약 하이퍼링크가 있는 경우, 파란색 + 빨간색을 이용하여 페이지 랭크를 계산한다. 이때 하이퍼링크가 있음에도 빨간색 부분이 더해진것을 확인할 수 있는데, 구글에선 이 영향력을 줄이기 위해 $\alpha=0.85$ 의 값을 사용했다.

결론적으론 teleport 개념을 도입함으로써 웹서퍼가 시간이 충분히 흘러 어느위치에 존재하건 어느 위치로든 반드시 도달할수 있게 하여 stationary distribution $p$ 가 하나의 유일한 확률분포로 수렴하도록 하였다.

위의 그림을 통해 결과를 살펴보면 보라색 노드들은 자신에게 들어오는 링크가 없지만 teleport를 통해 0 이 아닌 값이 할당되었고, C 노드의 경우 들어오는 링크가 하나뿐이지만 영향력있는 B의 노드가 연결되어 높은 값을 가지고 있는것을 확인할수 있다.

---

📄 Viral Marketing

우리가 살고 있는 복잡계에는 아이스 버킷 챌린지와 같은 행동의 전파나 코로나-19와 같은 질병의 전파 등 다양한 방식의 전파가 있다. 이번에는 전파(Influence)를 모델링할 수 있는 간단한 수학적 모형들과 주어진 그래프와 규칙에서 전파를 최대화하는 전파 최대화 문제에 대해서 살펴보도록 한다.

✏️ 의사결정 기반의 전파 모형

우리의 의사결정은 주변 사람들의 의사결정을 고려하여 판단된다. 가령, 메신저로 카카오톡 과 라인 중 어떤 것을 선택할지는 주변 사람들의 의사결정, 즉 어떤 메신저를 더 많이 사용하고 있을지에 따라 결정된다. 따라서 의사결정 과정을 가장 간단한 형태의 선형 임계치 모형(Linear Threshold Model) 을 통해 살펴보도록 한다.

친구관계의 두사람 u와 v가 두개의 호환되지 않는 기술 A와 B 중 하나를 선택한다고 가정한다. 이때, 다음과 같이 영향력을 정의한다.

• 둘 모두 A 기술을 사용할 경우 행복이 a 만큼 증가한다.

• 둘 모두 B 기술을 사용할 경우 행복이 b 만큼 증가한다.

• 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않는다.

위의 정의를 바탕으로 다음 예시를 살펴보면,

만약 u가 A 를 선택할 경우 행복은 2a 만큼 증가하고 B 를 선택할 경우 행복이 3b 만큼 증가한다. 이때,

• 2a > 3b 라면 u는 A를 택할것이다.

• 2a < 3b 라면 u는 B를 택할것이다.

• 2a = 3b 라면 편의상 u는 B를 택한다고 한다.

한층 더 나아가 위의 상황을 일반화 해보면

u는 $\textcolor{red}{ap}>\textcolor{blue}{b(1-p)}$ 일때 A 를 택하게 될 것이다. 즉 $p>\frac{\textcolor{blue}{b}}{\textcolor{red}{a}+\textcolor{blue}{b}}$ 일때 A 를 택하게 되며 선택의 기준이 되는 $\frac{b}{a+b}$를 임계치 라고 한다.

이제 선형 임계치 모형 정의를 바탕으로 의사결정의 과정이 어떻게 전파되는지 다음의 예시를 통해 살펴보도록 한다. 우선 쉬운 이해를 위해 다음과 같은 가정을 한다.

• 각 정점은 이웃 중 A를 선택한 비율 $p$ 가 임계치 $q=55\%$ 를 넘을 때만 A를 선택한다.

• 처음 A를 사용하는 시드 집합(Seed Set)을 정의하고 이 집합은 항상 A를 고수한다.

• 이 모형은 시드집합 이외에 전부 B를 사용하는 상황을 가정한다.

위의 그림은 전파 되기전의 상황이다. 이때 각 노드들의 이웃 중 A를 선택한 비율 $p_i$를 계산한 후 임계치 $q$ 를 넘었을 경우에만 A를 선택하는 과정은 다음과 같다.

즉 추가적으로 4명이 A를 선택했으며, 이후에도 위의 과정을 반복하면 다음 그림의 순서대로 전파가 된다.

마지막으로 더이상 임계치를 넘는 노드가 없으므로 전파가 멈춘것을 확인할 수 있다.

✏️ 확률적 전파 모형

코로나의 전파과정을 의사결정 기반 모형으로 적합하지 않는데, 그 어느 누구도 코로나에 걸리기로 의사결정 을 내리는 사람은 없기 때문이다. 따라서 코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야한다. 여기선 가장 간단한 형태의 확률적 전파 모형인 독립 전파 모형(Independent Cascade Model) 을 살펴보도록 한다.

위와 같이 방향성이 있고 가중치가 있는 그래프를 가정하면 각 edge $(u,v)$ 의 가중치 $w_{uv}$ 는 $u$가 감염되었을때 $u$가 $v$를 감염시킬 확률이다.(v는 감염되지 않은 상황) 즉, 각 정점 $u$가 감염될 때마다 각 이웃 $v$는 $p_{uv}$ 확률로 전염된다. 이때 독립 전파 모형은 서로 다른 이웃이 전염되는 확률은 독립적이다. 즉,

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

선형 임계치 모형과 마찬가지로 시드 집합이 존재하는데 여기선 첫 감염자들을 시드집합으로 볼 수 있다. 각 최초 감염자 $u$ 는 각 이웃 $v$ 에게 $p_{uv}$확률로 병을 전파하고 이 과정을 새로운 감염자가 없을때까지 반복한다. (이때, 감염자는 계속 감염자 상태로 남아있는것을 가정한다.물론 감염자의 회복을 가정하는 SIS,SIR 등의 다른 전파 모형도 있다.)

✏️ 전파 최대화(Influence Maximization)

바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법이다. 따라서 마케팅이 효과적이기 위해서는 소문의 시작점(시드 집합)이 중요하다.그 이유는 앞서 소개한 전파 모형에서도 확인할 수 있지만 시드집합을 어떻게 잡느냐에 따라 전파 크기가 달라지기 때문이다.

그렇다면 만약 시드집합을 선택할수 있다면 어떻게 선택할것인가?"

바로 이것에 대한 답을 찾는 방법이 전파 최대화(Influence Maximization) 문제이다. 즉, 그래프,전파모형,시드집합의 크기 가 주어졌을때, 전파를 최대화 하는 시드 집합을 찾는 문제이다. 하지만 이것은 쉬운 문제가 아니다. 간단하게 그래프에 정점이 10,000개, 시드집합의 크기가 10이라고 생각해본다면 고려해야 할 경우의 수는 $\binom{10000}{10}$ 이고 무려 2,743,355,077,591,282,538,231,819,720,749,000개 이다. 따라서 최고의 시드집합을 찾는 것은 힘들지만 대안으로 다음 두가지의 방법이 사용된다.

1. Heuristc Search
   해결법이 정확히 해결되는가에 대한 문제를 배제하고, 경험과 직관을 통해 일반적으로 좋은 해결법이나 근사하는 값을 찾고자 하는 방법이다. 따라서 합리적인 방법이지만 최고의 시드 집합을 찾는다는 보장은 없다.
   대표적 휴리스틱으로 정점의 중심성(Node Centrality) 를 사용한다. 따라서 시드집합의 크기가 k개로 고정되어있을때, 정점의 중심성이 높은 순으로 k개의 정점을 선택한다. 이때 정점의 중심성으로는 페이지랭크 점수,연결 중심성,근접 중심성,매개 중심성 등이 있다.

2. Greedy Search
   근시안적으로 매 순간 최적이라고 생각되는 시드 집합을 찾아가는 방법이다.예를 들어 정점의 집합이 $\{1,2,\dots,|V|\}$ 라면 첫 단계에서는 $\{1\}$,$\{2\}$,$\dots$,$\{|V|\}$ 를 비교하여 전파를 최대화하는 시드집합을 찾는다. 여기서 뽑힌 집합을 $\{x\}$ 라고 한다면 그 다음 단계에서는 $\{x,1\}$,$\{x,2\}$,$\dots$,$\{x,|V|\}$ 를 비교하여 전파를 최대화하는 시드집합을 찾는다. 이 과정을 목표하는 크기의 시드 집합에 도달할때까지 반복한다.
   물론 매순간의 최적이 전체에서의 최적을 보장할 수는 없지만 독립 전파 모형의 경우 이론적으로 정확도가 일부 보장된다. 이때 이론적으로 항상 입력 그래프와 무관하게 greedy search로 찾은 시드 집합의 의한 전파의 평균 크기 $G$ 는 최적의 시드집합에 의한 전파의 평균크기 $B$ 의 0.63 이상임을 보장한다.
   $G\ge B\ast(1-\frac{1}{e})\approx B*0.632$