강의 복습 내용

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

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

1. 페이지랭크의 배경

1.1 웹과 그래프

• 웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성 있는 그래프입니다
• 웹페이지는 정점에 해당합니다
• 웹페이지가 포함하는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당합니다
• 단, 웹페이지는 추가적으로 키워드 정보를 포함하고 있습니다

1.2 구글 이전의 검색 엔진

• 첫번째 시도는 웹을 거대한 디렉토리로 정리하는 것이었습니다
  • 웹페이지의 수가 증가함에 따라서 카테고리의 수와 깊이도 무한정 커지는 문제가 있습니다
  • 참고로 현재는 수십억 ~ 수백억 개의 웹페이지가 있는 것으로 알려져 있습니다
  • 또한, 카테고리 구분이 모호한 경우가 많아, 저장과 검색에 어려움이 있습니다
• 두번째 시도는 웹페이지에 포함된 키워드에 의존한 검색 엔진입니다
  • 사용자가 입력한 키워드에 대해, 해당 키워드를 (여러 번) 포함한 웹페이지를 반환합니다
  • 하지만, 이 방법은 악의적인 웹페이지에 취약하다는 단점이 있습니다
  • 예를 들어, 성인 사이트에 ‘축구’라는 키워드를 (보이지 않도록) 여러 번 포함하게 되면, ‘축구’를 검색했을 때 해당 성인 사이트가 결과로 나올 수 있습니다
• Q. 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 어떻게 찾을 수 있을까요?
  • A. 구글의 창업자인 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)은 The PageRank Citation Ranking: Bringing Order to the Web 라는 제목의 논문을 통해 이 질문에 답합니다

2. 페이지랭크의 정의

2.1 페이지랭크의 정의: 투표 관점

• 페이지랭크의 핵심 아이디어는 투표입니다
• 즉, 투표를 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾습니다
• 투표의 주체는 바로 웹페이지입니다
• 웹페이지는 하이퍼링크를 통해 투표를 합니다
• 사용자 키워드를 포함한 웹페이지들을 고려합시다
• 웹페이지 𝑢가 𝑣로의 하이퍼링크를 포함한다면?
• 𝑢의 작성자가 판단하기에 𝑣가 관련성이 높고 신뢰할 수 있다는 것을 의미합니다
• 즉, 𝑢가 𝑣에게 투표했다고 할 수 생각할 수 있습니다
• 즉, 들어오는 간선이 많을 수록 신뢰할 수 있다는 뜻입니다
• Q. 그런데 들어오는 간선의 수를 세는 것만으로 충분할까요?
  • A. 아닙니다. 악용될 소지가 있습니다
  • 웹페이지를 여러 개 만들어서 간선의 수를 부풀릴 수 있습니다
  • 즉, 관련성과 신뢰도가 높아 보이도록 조작할 수 있습니다
• Q. 이런 악용을 막으려면 어떻게 해야 할까요?
  • A. 이런 악용에 의한 효과를 줄이기 위해, 페이지랭크에서는 가중 투표를 합니다
  • 즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주합니다
  • 반면, 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주합니다
  • 악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방법입니다
• Q. 잠깐, 관련성과 신뢰성은 저희가 투표를 통해 측정하려는 것 아니었나요?
  출력을 입력으로 사용하자는 이야기처럼 들리는데요?
  • A. 그렇습니다. 재귀(Recursion), 즉 연립방정식 풀이를 통해 가능합니다.
• 측정하려는 웹페이지의 관련성 및 신뢰도를 페이지랭크 점수라고 부릅시다
  • 각 웹페이지는 각각의 나가는 이웃에게 자신의 페이지랭크 점수/나가는 이웃의 수 만큼의 가중치로 투표를 합니다
  • 페이지랭크 점수의 정의는 다음과 같습니다
    

2.2 페이지랭크의 정의: 임의 보행 관점

• 페이지랭크는 임의 보행(Random Walk)의 관점에서도 정의할 수 있습니다
  • 임의 보행을 통해 웹을 서핑하는 웹서퍼를 가정합시다
  • 즉, 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑합니다
  • 웹서퍼가 𝑡번째 방문한 웹페이지가 웹페이지 𝑖일 확률을 𝒑𝒊(𝒕)라고 합시다
  • 그러면 𝒑(𝒕)는 길이가 웹페이지 수와 같은 확률분포 벡터가 됩니다
  • 그러면 아래 식이 성립합니다
    

3. 페이지랭크의 계산

3.1 페이지랭크의 계산: 반복곱

• 이지랭크 점수의 계산에는 반복곱(Power Iteration)을 사용합니다
• 반복곱은 다음 세 단계로 구성됩니다
  • (1) 각 웹페이지 𝑖의 페이지랭크 점수 𝒓𝒊(𝟎)를 동일하게 1/웹페이지의 수로 초기화합니다
  • (2) 아래 식을 이용하여 각 웹페이지의 페이지랭크 점수를 갱신합니다
    
  • (3) 페이지랭크 점수가 수렴하였으면 종료합니다. 아닌 경우 (2)로 돌아갑니다

3.2 문제점과 해결책

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

• Q1. 반복곱이 항상 수렴하는 것을 보장할 수 있나요?

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

• Q2. 반복곱이 “합리적인” 점수로 수렴하는 것을 보장할 수 있나요?

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

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

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

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

• (1)과 (4)의 임의의 웹페이지는 전체 웹페이지들 중에 하나를 균일확률로 선택합니다

• 순간이동에 의해서 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어졌습니다

• 𝛼를 감폭 비율(Damping Factor)이라고 부르며 값으로 보통 0.8 정도를 사용합니다

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

  • (1) 각 막다른 정점에서 (자신을 포함) 모든 다른 정점으로 가는 간선을 추가합니다
  • (2) 아래 수식을 사용하여 반복곱을 수행합니다
    
  • |𝑉|는 전체 웹페이지의 수를 의미합니다
  • 파란색 부분은 하이퍼링크를 따라 정점 𝑗에 도착할 확률을 의미합니다
  • 빨간색 부분은 순간이동을 통해 정점 𝑗에 도착할 확률을 의미합니다

• 3강 정리

  • 1. 페이지랭크의 배경
    • 디렉토리, 키워드 기반 검색 엔진의 한계
  • 2. 페이지랭크의 정의
    • 투표 관점 : 하이퍼링크를 통한 가중 투표
    • 임의 보행 관점 : 웹서퍼가 각 웹페이지를 방문할 확률
  • 3. 페이지랭크의 계산
    • 반복곱
    • 스파이더 트랩 및 막다른 정점 문제를 해결하기 위한 순간 이동

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

1. 그래프를 통한 전파의 예시

1.1 그래프를 통한 정보의 전파

• 온라인 소셜 네트워크를 통해 다양한 정보가 전파됩니다
• 2011년 스페인의 15M 운동에 대한 정보는 트위터를 통해 전국적으로 알려졌습니다
• 덕분에 주류 언론이 침묵하는 상황에서도, 시민들이 정부의 부정부패에 맞서 연대할 수 있었습니다
• 유용한 과학적 정보가 전파되기도 합니다

1.2 그래프를 통한 행동의 전파

• 아이스 버킷 챌린지, 펭귄 문제 등이 대표적인 예시입니다

1.3 그래프를 통한 고장의 전파

• 컴퓨터 네트워크에서의 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수 있습니다
• 일부 장비의 고장이, 다른 장비의 과부화로 이어지기 때문입니다
• 파워 그리드에서의 정전이 전파되는 과정도 유사합니다

1.4 그래프를 통한 질병의 전파

• 사회라는 거대한 소셜 네트워크를 통한 질병의 전파도 빠뜨릴 수 없습니다
• 코로나-19, 메르스, 사스 등이 그 예시입니다
• 전파 과정은 다양할 뿐 아니라 매우 복잡합니다
• 이를 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요합니다
• 본 수업에서는 전파 과정을 위한 수 많은 모형 중 두 가지를 소개합니다

2. 의사결정 기반의 전파 모형

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

• 1970년대에는 VHS와 Betamax라는 호환되지 않는 두 종류의 비디오 유형이 있었습니다
• 어떤 유형의 비디오 플레이어를 구매하시겠습니까?
• 의사 결정을 위해 어떤 정보를 참고해야 할까요?
• 그러면 카카오톡과 라인 중에 어떤 것을 사용하시고 있나요? 왜 그런 결정을 하셨나요?
• 두 경우 모두 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미칩니다
• 친구들이 대부분 라인을 쓴다면, 카카오톡을 사용하는 것이 불편합니다
• 친구들이 대부분 VHS 유형을 쓴다면, 같은 유형을 써야 서로 비디오를 빌려줄 수 있습니다
• 이렇듯 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용합니다
• 본 수업에서는 가장 간단한 형태의 의사결정 기반의 전파 모형인 선형 임계치 모형(Linear Threshold Model)을 소개합니다

2.2 선형 임계치 모형

• 이 상황을 수학적으로 추상화 해봅시다
  • 친구 관계의 두 사람 𝑢와 𝑣를 가정합시다
  • 둘은 두 개의 호환되지 않는 기술 𝐴와 𝐵 중에서 하나를 선택합니다
  • 둘 모두 𝐴 기술을 사용할 경우, 행복이 𝑎만큼 증가합니다
  • 둘 모두 𝐵 기술을 사용할 경우, 행복이 𝑏만큼 증가합니다
  • 하지만, 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않습니다
• 소셜 네트워크를 고려해봅시다
  • 우리는 동시에 여러 사람과 친구 관계를 맺습니다
  • 각각의 친구, 즉 소셜 네트워크 상의 이웃과의 사이에서 발생하는 행복을 고려해야합니다
  • 오른쪽 예시에서 𝑢가 𝐴를 선택할 경우 행복이 2𝑎 만큼 증가합니다
  • 오른쪽 예시에서 𝑢가 𝐵를 선택할 경우 행복이 3𝑏 만큼 증가합니다
  • 각자가 행복이 최대화되는 선택을 한다고 가정해봅시다
  • 만약, 2𝑎 > 3𝑏 라면 𝑢는 𝐴를 택할 것입니다
  • 반면, 2𝑎 < 3𝑏 라면 𝑢는 𝐵를 택할 것입니다
  • 편의상 2𝑎 = 3𝑏 라면 𝑢는 𝐵를 택한다고 합시다
• 좀 더 일반화 해봅시다
  • 𝑝 비율의 이웃이 𝐴를 선택했다고 해봅시다
  • 즉, 1−𝑝 비율의 이웃이 𝐵를 선택했습니다
  • 언제 𝐴를 선택할까요?
  • 𝑎𝑝 > 𝑏(1−𝑝) 일 때입니다
  • 정리하면 𝑝 > 𝑏/(𝑎+𝑏) 일 때입니다
  • 편의상 𝑏/(𝑎+𝑏)를 임계치 𝑞라고 합시다
• 이 모형을 선형 임계치 모형(Linear Threshold Model)이라고 합니다
  • 각 정점은 이웃 중 𝐴를 선택한 비율이 임계치 𝑞를 넘을 때만 𝐴를 선택합니다
  • 이 모형은 전부 𝐵를 사용하는 상황을 가정합니다
  • 그리고 처음 𝐴를 사용하는 얼리 어답터들을 가정합니다
  • 시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 𝐴를 고수한다고 가정합시다

3. 확률적 전파 모형

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

• 코로나의 전파 과정을 수학적으로 추상화해봅시다
• 의사결정 기반 모형은 적합하지 않습니다
• 누구도 코로나에 걸리기로 ‘의사결정’을 내리는 사람은 없기 때문입니다 코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야합니다
• 본 수업에서는 가장 간단한 형태의 확률적 전파 모형인
• 독립 전파 모형(Independent Cascade Model)을 소개합니다

3.2 독립적 전파 모형

• 방향성이 있고 가중치가 있는 그래프를 가정합시다
• 각 간선 (𝑢,𝑣)의 가중치 𝑝𝑢𝑣는 𝑢가 감염되었을 때 (그리고 𝑣가 감염되지 않았을 때) 𝑢가 𝑣를 감염시킬 확률에 해당합니다
• 즉, 각 정점 𝑢가 감염될 때마다, 각 이웃 𝑣는 𝑝𝑢𝑣확률로 전염됩니다
• 𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑢가 감염되었을 때 𝑢가 𝑤를 감염시킬 확률과 독립적입니다
• 𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑤가 감염되었을 때 𝑤가 𝑣를 감염시킬 확률과 독립적입니다
• 모형은 모델은 최초 감염자들로부터 시작합니다
• 이전 모형과 마찬가지로 첫 감염자들을 시드 집합(Seed Set)이라고 부릅니다
• 각 최초 감염자 𝑢는, 각 이웃 𝑣에게 𝑝𝑢𝑣확률로 병을 전파합니다 위 과정을 새로운 감염자 각각에게 반복합니다
• 위 과정을 새로운 감염자 각각에게 반복합니다
• 위 과정을 새로운 감염자 각각에게 반복합니다
• ...
• 더 이상 새로운 감염자가 없으면 종료합니다
• 감염자는 계속 감염자 상태로 남아있는 것을 가정합니다
• 감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파 모형도 있습니다

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

4.1 바이럴 마케팅이란?

• 바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법입니다
• 바이럴 마케팅이 효과적이기 위해서는 소문의 시작점이 중요합니다
• 시작점이 어디인지에 따라서 입소문이 전파되는 범위가 영향을 받기 때문입니다
• 소셜 인플루언서(Social Influencer)들이 높은 광고비를 받는 이유입니다

4.2 시드 집합의 중요성

• 대표적인 소셜 인플루언서에는 영국 윌리엄 왕자의 부인 케이트 미들턴이 있습니다
• ‘미들턴 효과’라는 말이 생겨날 정도입니다
• 앞서 소개한 전파 모형들에서도 시드 집합이 전파 크기에 많은 영향을 미칩니다
• 선형 임계치 모형의 예시에서 시드 집합으로 𝑢와 𝑣를 선택했을 때, 총 9명이 𝐴를 선택했습니다
• 시드 집합으로 𝑥와 𝑦를 선택했다면, 추가 전파는 발생하지 않습니다. 2명만이 𝐴를 선택했습니다

4.3 전파 최대화 문제

• 시드 집합을 우리가 선택할 수 있다면, 누구를 선택하시겠습니까?
• 그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 - 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다
• 전파 모형으로는 앞서 배운 선형 임계치 모형, 독립 전파 모형을 포함 다양한 모형을 고려할 수 있습니다
• 전파 최대화 문제는 방대한 그래프, 즉 소셜 네트워크로부터, ‘케이트 미들턴’, 즉 영향력 있는 - - 시드 집합을 찾아내는 문제입니다
• 전파 최대화 문제는 굉장히 어려운 문제입니다
• 그래프에 |𝑉|개의 정점이 있을 경우, 시드 집합의 크기를 𝑘개로 제한하더라도 경우의 수는 |𝑉|C𝑘개 입니다.
• 정점이 10,000개, 시드 집합의 크기를 10으로 고정합시다
• 경우의 수는 무려 2,743,355,077,591,282,538,231,819,720,749,000개입니다
• 이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명 되었습니다
• 최고의 시드 집합을 찾는 것은 포기합시다

4.4 정점 중심성 휴리스틱

• 대표적 휴리스틱으로 정점의 중심성(Node Centrality)을 사용합니다
• 즉, 시드 집합의 크기가 𝑘𝑘개로 고정되어 있을 때,
• 정점의 중심성이 높은 순으로 𝑘𝑘개 정점 선택하는 방법입니다
• 정점의 중심성으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있습니다
• 합리적인 방법이지만, 최고의 시드 집합을 찾는다는 보장은 없습니다

4.5 탐욕 알고리즘

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

• 탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택합니다

• 즉, 정점의 집합을 {1,2,...,|𝑉|}라고 할 경우 구체적인 단계는 다음과 같습니다

• 집합 {1}, {2}, ... , {|𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다

• 이 때, 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균 값을 사용합니다 뽑힌 집합을 {𝑥} 라고 합시다

• 집합 {𝑥, 1}, {𝑥, 2}, ... , {𝑥, |𝑉|}를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다

• 뽑힌 집합을 {𝑥, 𝑦} 라고 합시다

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

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

• 즉, 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고

• 근시안적으로 최초 전파자를 선택하는 과정을 반복합니다

• 탐욕 알고리즘은 얼마나 정확한가요?

• 독립 전파 모형에 경우, 이론적으로 정확도가 일부 보장됩니다

• 항상, 즉 입력 그래프와 무관하게 다음 부등식이 성립합니다

• 탐욕 알고리즘으로 찾은 시드 집합의 의한 전파의 (평균) 크기 ≥ 1−1/e ≈ 0.632 (최고의 시드 집합에 의한 전파의 (평균) 크기)

• 다시 말해, 탐욕 알고리즘의 최저 성능은 수학적으로 보장되어 있습니다

• 4강 정리

  • 1. 그래프를 통한 전파의 예시
    • 정보, 행동, 고장, 질병 등
  • 2. 의사결정 기반의 전파 모형
    • 각각의 정점이 개인의 행복을 최대화하도록 의사결정하는 상황을 모형화
    • 대표 예시 : 선형 임계치 모형
  • 3. 확률적 전파 모형
    • 질병의 전파 등 확률적 과정을 모형화
    • 대표 예시 : 독립적 전파 모형
  • 4. 바이럴 마케팅과 전파 최대화 문제
    • 전파를 최대화하는 시드 집합을 찾는 문제
    • 정점 중심성 휴리스틱, 탐욕 알고리즘 등

Further Question

감염병의 전파를 모델링 하기 위해서는 감염과 더불어 감염된 환자의 회복을 고려해야 합니다. 감염된 사람이 회복될 수 있고, 한 번 감염이 된 사람은 추가적으로 감염이 되지 않는다고 가정한다면 어떻게 전파 모델을 설계할 수 있을까요?

• 링크 참고

피어 세션 정리

강의 리뷰 및 Q&A

• [Graph 3강] 검색 엔진에서는 그래프를 어떻게 활용할까?
• [Graph 4강] 그래프를 바이럴 마케팅에 어떻게 활용할까?

스터디 발표

과제 진행 상황 정리 & 과제 결과물에 대한 정리

[과제 1] 그래프를 컴퓨터 언어로 표현하기 & 페이지랭크 알고리즘 구현하기

• 페이지랭크 알고리즘에 대한 것으로, 어렵지 않게 해결했습니다.

총평

이제까지 병행해왔던 일들이 하나씩 정리되고 있습니다.
물론 또 다른 일들이 하나씩 쌓이고는 있지만, 앞으로는 부스트캠프에 조금 더 집중할 수 있을 것 같습니다.
그리고 U Stage도 슬슬 끝나가고 P Stage가 점점 다가오고 있습니다.
프로젝트로 진행되는 P Stage인 만큼 기대가 되고 얼른 시작했으면 좋겠습니다.

오늘보다 더 성장한 내일의 저를 기대하며, 내일 뵙도록 하겠습니다.

읽어주셔서 감사합니다!