[ Day 22 ]

2021 부스트캠프 Day 22.

[Day 22] Graph

---

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

페이지랭크의 배경

웹과 그래프

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

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

구글 이전의 검색 엔진

• 첫번째 시도는 웹을 거대한 디렉토리로 정리하는 것

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

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

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

• 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페에지를 어떻게 찾을 수 있을까?

  • 구글의 창업자인 래리 페이지(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), 즉 연립방정식 풀이를 통해 가능하다.

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

• 각 웹페이지는 각각의 나가는 이웃에게 (자신의 페이지랭크 점수) / (나가는 이웃의 수) 만큼의 가중치로 투표를 한다.

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

• 위 예시에서 웹페이지 $j$는 웹페이지 $x$,$y$,$z$에게 각각 가중치 $r$$j$/$3$ 으로 투표를 한다.

• $r$$j$는 웹페이지 $j$의 페이지랭크 점수를 의미한다.

• $r$$j$는 다음과 같다.
  

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

• 조금 더 간단한 예시를 보겠다.
  

• 위 예시에서의 정점 별 페이지랭크 식은 다음과 같다.
  

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

임의 보행 관점

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

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

• 웹서퍼가 𝑡번째 방문한 웹페이지가 웹페이지 𝑖일 확률을 𝒑𝒊(𝒕)라고 하면,
  𝒑(𝒕)는 길이가 웹페이지 수와 같은 확률분포 벡터가 되고 아래 식이 성립한다.
  

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

• 다시 말해 𝒑(𝒕) = 𝒑(𝒕 + 𝟏) = 𝒑이 성립하게 된다.
  수렴한 확률 분포 𝒑는 정상 분포(Stationary Distribution)이라고 부르며 수식을 아래와 같이 바꿀 수 있다.
  

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

페이지랭크의 계산

반복곱

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

• 반복곱은 다음 세 단계로 구성된다.

  • (1) 각 웹페이지 𝑖의 페이지랭크 점수 𝒓𝒊(𝟎) 를 동일하게 1/(웹페이지의 수) 로 초기화
  • (2) 아래 식을 이용하여 각 웹페이지의 페이지랭크 점수를 갱신
  • (3) 페이지랭크 점수가 수렴하였으면 종료합니다. 아닌 경우 (2)로 돌아간다.

문제점

• Q : 반복곱이 항상 수렴하는 것을 보장 할 수 있나?
  

• Q : 반복곱이 "합리적인" 점수로 수렴하는 것을 보장할 수 있나?
  

해결책 : 순간이동(Teleport) 도입

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

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

• 순간이동에 의해서 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어진다.
  𝛼를 감폭 비율(Damping Factor)이라고 부르며 값으로 보통 0.8 정도를 사용한다.

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

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

• 수정된 페이지랭크 점수 예시
  

---

그래프를 바이럴 마케팅에 어떻게 활용할까?

그래프를 통한 전파의 예시

그래프를 통한 정보의 전파

• 온라인 소셜 네트워크를 통해 다양한 정보가 전파
• 유용한 과학적 정보 등

그래프를 통한 행동의 전파

• 온라인 소셜 네트워크를 통해 다양한 행동이 전파
• 아이스 버킷 챌린지, 펭귄 문제 등

그래프를 통한 고장의 전파

• 컴퓨터 네트워크에서의 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수 있다.

• 일부 장비의 고장이, 다른 장비의 과부화로 이어지기 때문
  

• 파워 그리드에서의 정전이 전파되는 과정도 유사
  

그래프를 통한 질병의 전파

• 사회라는 거대한 소셜 네트워크를 통한 질병의 전파

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

결론

• 전파 과정은 다양할 뿐 아니라, 매우 복잡하다.

• 이를 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요

의사결정 기반의 전파 모형

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

• 1970년대에는 VHS와 Betamax라는 호환되지 않는 두 종류의 비디오 유형이 있었다.
  어떤 유형의 비디오 플레이어를 구매해야 할까?
  의사 결정을 위해 어떤 정보를 참고해야 할까?

• 카카오톡과 라인 중에 어떤 것을 사용하고 있는가?
  왜 그런 결정을 하였는가?

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

• 친구들이 대부분 라인을 쓴다면, 카카오톡을 사용하는 것이 불편하다.
  친구들이 대부분 VHS 유형을 쓴다면, 같은 유형을 써야 서로 비디오를 빌려 줄 수 있다.

• 이렇듯 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용

선형 임계치 모형(Linear Threshold Model)

• 가장 간단한 형태의 의사결정 기반의 전파 모형

• 수학적인 추상화

• 친구 관계의 두 사람 𝑢 와 𝑣
  둘은 두 개의 호환되지 않는 기술 𝐴와 𝐵중에서 하나를 선택
  둘 모두 𝐴 기술을 사용할 경우, 행복이 𝑎만큼 증가
  둘 모두 𝐵 기술을 사용할 경우, 행복이 𝑏만큼 증가
  하지만, 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않는다.
  

• 소셜 네트워크를 고려해보자

• 우리는 동시에 여러 사람과 친구 관계를 맺는다.
  각각의 친구, 즉 소셜 네트워크 상의 이웃과의 사이에서 발생하는 행복을 고려해야한다.
  아래 예시에서 𝑢가 𝐴를 선택할 경우 행복이 2𝑎 만큼 증가
  아래 예시에서 𝑢가 𝐵를 선택할 경우 행복이 3𝑏 만큼 증가
  

• 각자 행복이 최대화되는 선택을 한다고 가정

• 만약, 2𝑎 > 3𝑏 라면 𝑢는 𝐴를 택할 것이다
  반면, 2𝑎 < 3𝑏 라면 𝑢는 𝐵를 택할 것이다
  편의상 2𝑎 = 3𝑏 라면 𝑢는 𝐵를 택한다고 가정

• 좀더 일반화를 해보자.

• 비율의 이웃이 𝐴를 선택했다고 가정
  즉, 1 − 𝑝 비율의 이웃이 𝐵를 선택한다.

• 언제 𝐴를 선택할까?
  𝑎𝑝 > 𝑏(1 − p) 일 때이다.
  정리하면 𝑝 > 𝑏 / 𝑎+𝑏 일 때이다.
  편의상 𝑏 / 𝑎+𝑏 를 임계치 𝑞라고 하자.
  

• 이 모형을 선형 임계치 모형(Linear threshold Model)이라 한다.

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

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

• 예시를 고려해보자.
  

• 임계치 𝑞는 55%를 가정, 𝑢와 𝑣가 시드 집합인 상황

• 𝑢와 𝑣의 선택을 고려하여, 각자 다시 기술을 선택한다.

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

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

• 추가로 1명이 A를 선택한다.
  이웃중 A를 선택한 비율이 임게치 55%를 넘었기 때문이다.
  

• 추가로 1명이 A를 선택한다.
  이웃중 A를 선택한 비율이 임게치 55%를 넘었기 때문이다.
  

• 전파가 멈추었다.
  A를 택하지 않은 정점 중, 이웃 중 A를 선택한 비율이 임계치 55%를 넘는 경우가 없기 때문이다.
  

확률적 전파 모형

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

• 코로나의 전파 과정을 수학적으로 추상화해보자

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

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

독립적 전파 모형(Independent Cascade Model)

• 가장 간단한 형태의 확률적 전파 모형

• 방향성이 있고 가중치가 있는 그래프를 가정.

• 각 간선 (𝑢, 𝑣)의 가중치 𝑝𝑢𝑣는 𝑢가 감염되었을 때 (그리고 𝑣가 감염되지 않았을 때) 𝑢가 𝑣를 감염시킬 확률에 해당한다.

• 즉, 각 정점 𝑢가 감염될 때마다, 각 이웃 𝑣는 𝑝𝑢𝑣확률로 전염된다.
  

• 서로 다른 이웃이 전염되는 확률은 독립적
  𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑢가 감염되었을 때, 𝑢가 𝑤를 감염시킬 확률과 독립적
  𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑤가 감염되었을 때, 𝑤가 𝑣를 감염시킬 확률과 독립적

• 모형은 모델의 최초 감염자들로부터 시작된다.

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

• 각 최초 감염자 𝑢는, 각 이웃 𝑣에게 𝑝𝑢𝑣확률로 병을 전파합니다
  위 과정을 새로운 감염자 각각에게 반복
  위 과정을 새로운 감염자 각각에게 반복
  …
  더 이상 새로운 감염자가 없으면 종료
  감염자는 계속 감염자 상태로 남아있는 것을 가정
  감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파 모형도 있다.

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

바이럴 마케팅이란?

• 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법

• 바이럴 마케팅이 효과적이기 위해서는 소문의 시작점이 중요하다.

• 시작점이 어디인지에 따라서 입소문이 전파되는 범위가 영향을 받기 때문
  소셜 인플루언서(Social Influencer)들이 높은 광고비를 받는 이유

시드 집합의 중요성

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

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

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

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

전파 최대화 문제

• 시드 집합을 우리가 선택할수 있다면, 누구를 선택해야 할까?

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

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

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

• 그래프에 |𝑉|개의 정점이 있을 경우, 시드 집합의 크기를 𝑘개로 제한하더라도
  경우의 수는 |𝑉|C𝑘개 이다.

• 정점이 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, … , |𝑉|}라고 할 경우 구체적인 단계는 다음과 같다.

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

• 집합 {𝑥, 1},{𝑥, 2}, … ,{𝑥, |𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾는다.
  뽑힌 집합을 {𝑥, 𝑦} 라고 하자.

• 집합 {𝑥, 𝑦, 1},{𝑥, 𝑦, 2}, … ,{𝑥, 𝑦, |𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾는다.
  뽑힌 집합을 {𝑥, 𝑦, 𝑧} 라고 하자

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

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

• Q : 탑욕 알고리즘은 얼마나 정확한가?

  • A : 독립 전파 모형의 경우, 이론적으로 정확도가 일부 보장
  • 항상, 즉 입력 그래프와 무관하게 다음 부등식이 성립한다.
    
  • 다시 말해, 탐욕 알고리즘의 최저 성능은 수학적으로 보장되어 있다.