전파 모델

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

• 정보의 전파는 어떻게 일어나는 걸까?
• 우리가 살고 있는 복잡계에는 아이스 버킷 챌린지와 같은 행동의 전파나 코로나-19와 같은 질병의 전파 등 다양한 방식의 전파가 있다
• 이번에는 전파(Influence)를 모델링할 수 있는 간단한 수학적 모형들과 주어진 그래프와 규칙에서 전파를 최대화하는 전파 최대화 문제에 대해서 배운다
• 어떤 식으로 전파를 모델링할 수 있는 지, 전파가 단계별로 어떻게 이루어지는 지 집중하면서 보자

Further Question

• 감염병의 전파를 모델링 하기 위해서는 감염과 더불어 감염된 환자의 회복을 고려해야 한다. 감염된 사람이 회복될 수 있고, 한 번 감염이 된 사람은 추가적으로 감염이 되지 않는다고 가정한다면 어떻게 전파 모델을 설계할 수 있을까?
  • Ans : 감염 후보자(S), 감염자(I), 회복자(R)을 모두 고려한 SIR 모델이 있다. 아래의 링크를 참고
  • The SIR Model for Spread of Disease - The Differential Equation Model

Further Reading

• A Survey on Influence Maximization in a Social Network

그래프를 통한 전파의 예시

그래프를 통한 정보의 전파

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

그래프를 통한 행동의 전파

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

그래프를 통한 고장의 전파

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

그래프를 통한 질병의 전파

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

의사결정 기반의 전파 모형

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

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

선형 임계치 모형

• 위 상황을 수학적으로 추상화 해보자
  • 친구 관계의 두 사람 $𝑢𝑢$와 $𝑣𝑣$를 가정하자
  • 둘은 두 개의 호환되지 않는 기술 $𝐴𝐴$와 $𝐵𝐵$ 중에서 하나를 선택한다
  • 둘 모두 $𝐴𝐴$ 기술을 사용할 경우, 행복이 $𝑎𝑎$만큼 증가한다
  • 둘 모두 $𝐵𝐵$ 기술을 사용할 경우, 행복이 $𝑏𝑏$만큼 증가한다
  • 하지만, 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않는다
    
• 여러사람이 동시에 등장하는 소셜 네트워크를 고려해보자
  • 우리는 동시에 여러 사람과 친구 관계를 맺는다
  • 각각의 친구, 즉 소셜 네트워크 상의 이웃과의 사이에서 발생하는 행복을 고려해야한다
  • 아래의 예시에서 $u$ 가 $A$(빨간색)를 선택할 경우 행복이 $2a$ 만큼 증가한다
  • 아래의 예시에서 $u$ 가 $B$(파란색)를 선택할 경우 행복이 $3b$ 만큼 증가한다

• 각자가 행복이 최대화된느 선택을 한다고 가정해보자
  • 만약, $2a$ > $3b$ 라면, $u$는 $A$를 택할 것이다
  • 반면, $2a$ < $3b$ 라면, $u$는 $B$를 택할 것이다
  • 편의상 $2a = 3b$ 라면, $u$는 $B$를 택한다고 가정해보자
• 좀 더 일반화 해보자
  • $p$ 비율의 이웃이 $A$를 선택했다고 해보자
    • $A$ 를 선택함으로써 얻을수 있는 행복의 양은 $a \times p \times N$(이웃의 수) 이다
  • 즉, $1-p$ 비율의 이웃이 $B$를 선택했다
    • $B$ 를 선택함으로써 얻을수 있는 행복의 양은 $b \times (1 - p) \times N$(이웃의 수) 이다
  • 언제 $A$를 선택할까?
    • $ab > b(1-p)$ 일 때이다
  • 정리하면
    • $p > \frac{b}{a+b}$ 일때다
    • 펴의상 $\frac{b}{a+b}$를 임계치 $q$ 라고 하자
    • 즉, $A$를 선택할 비율이 임계치보다 클때 그 정점은 $A$를 선택한다고 할 수 있다
• 이 모형을 선형 임계치 모형(linear threshold model) 이라고 한다
  • 각 정점은 이웃 중 $A$를 선택한 비율 이 임계치 $q$ 를 넘을 때만 $A$를 선택한다
  • 이 모형은 전부 $B$를 사용하는 상황을 가정한다
  • 그리고 처음 $A$를 사용하는 얼리 어답터 들을 가정한다
  • 시드 집합(seed set) 이라고 불리는 얼리 어답터들은 항상 $A$를 고수한다고 가정하자
  • 즉, $B$라는 것은 기존에 사용되고 있는 기술 그리고 $A$는 새로운 기술이라고 생각하면 된다
  • 또한 $B$ 와 $A$는 서로 호환되지 않는다고 생각하자
• 예시를 고려하자
  • 아래 그림에서 파란색 정점들은 $B$를 선택했고, 빨간색 정점들은 $A$를 선택했다
    
  • 임계치 $q$ 는 55% 를 가정하자
  • $A$를 선택한 $u$와 $v$가 시드 집합인 상황이다 즉, $u,v$는 얼리 어답터로써 주변의 선택과 상관없이 $A$라는 기술을 고수하는 상황이다
  • 얼리 어답터 $u,v$의 등장이 다른 정점들의 행동에 어떻게 영향을 미치는지 살펴보자
    
  • 얼리 어답터의 등장으로 __추가로 4명이 $A$를 선택했다
  • 새로 $A$를 선택한 4명 각 이웃의 $A$를 선택한 비율이 임계치 55%를 넘었기 때문이다
  • 4명의 정점이 추가로 $A$를 선택한 행동이 다른 정점들의 결정에 어떻게 영향을 미치는지, 즉 행동이 어떻게 전파되는지를 살펴보자
    
  • 추가로 1명이 $A$를 선택했다
  • 추가로 바꾼 1명의 이웃 중 4A$를 선택한 비율이 임계치 55%를 넘었기 때문이다
  • 위 과정을 반복하여 $A$를 택하지 않은 정점 중, 이웃 중 $A$를 선택한 비율이 임계치 55%를 넘는 경우가 없을 때 전파가 멈춘다
  • 전파가 멈추고 최종적으로 나오는 그래프의 모형은 아래와 같다
    
  • 정리해보면 $u, v$ 라는 얼리 어답터에서 시작된 $A$라는 기술이 그래프의 전반에 퍼지게 되었다
  • 전파의 결과 두개의 정점을 제외한 모든 정점들이 $A$라는 기술을 사용하게 되었다

확률적 전파 모형

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

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

독립적 전파 모형

• 방향성이 있고 가중치가 있는 그래프를 가정
• 각 간선 ($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) 이라고 부른다
  • 각 최초 감염자 $𝑢$는, 각 이웃 $𝑣$에게 $𝑝_{𝑢v}$확률로 병을 전파한다
  • 위 과정을 새로운 감염자 각각에게 반복
  • 더 이상 새로운 감염자가 없으면 종료
    
  • 감염자는 계속 감염자 상태로 남아있는 것을 가정한다
  • 감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파 모형도 있다

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

바이럴 마케팅이란?

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

시드 집합의 중요성

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

전파 최대화 문제

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

정점 중심성 휴리스틱

• 대표적 휴리스틱으로 정점의 중심성(Node Centrality)을 사용한다
  • 휴리스틱이란 것은 실험적으로는 잘 동작할수 있지만 이론적으로는 정확도에 대해서 어떠한 보장도 할수 없는 알고리즘을 의미한다
  • 즉, 시드 집합의 크기가 $k$개로 고정되어 있을 때, 정점의 중심성이 높은 순으로 $𝑘$개 정점 선택하는 방법이다
  • 정점의 중심성을 측정하는 방법에는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있다
  • 합리적인 방법이지만, 최고의 시드 집합을 찾는다는 보장은 없다

탐욕 알고리즘

• 전파 최대화 문제를 푸는 알고리즘으로써 탐욕 알고리즘(Greedy Algorithm) 역시 많이 사용된다
  • 탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택 한다
  • 즉, 정점의 집합을 {1, 2, … , $|𝑉|$}라고 할 경우 구체적인 단계는 다음과 같다
    • 집합 {1},{2}, … ,{$|𝑉|$}를 비교하여, 전파를 최대화하는 시드 집합을 찾는다
    • 이 때, 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균 값을 사용한다
    • 뽑힌 집합을 {$𝑥$} 라고 하자
    • 집합 {$𝑥$, 1},{$𝑥$, 2}, … ,{$𝑥$, $|𝑉|$}를 비교하여, 전파를 최대화하는 시드 집합을 찾는다
    • 뽑힌 집합을 {$𝑥, 𝑦$} 라고 하자
    • 집합 {$𝑥, 𝑦$, 1},{$𝑥,𝑦$, 2}, … ,{$𝑥, 𝑦$, $|𝑉|$}를 비교하여, 전파를 최대화하는 시드 집합을 찾는다
    • 뽑힌 집합을 {$𝑥, 𝑦, 𝑧$} 라고 하자
    • 위 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복 한다
    • 즉, 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고 근시안적으로 최초 전파자를 선택하는 과정을 반복한다
• 탐욕 알고리즘은 얼마나 정확한가?
  • 독립 전파 모형에 탐욕 알고리즘을 사용할 경우, 이론적으로 정확도가 일부 보장된다
  • 항상, 즉 입력 그래프와 무관하게 다음 부등식이 성립한다
    • 탐욕 알고리즘으로 찾은 시드 집합의 의한 전파의 (평균) 크기 ≥ $(1 − \frac{1}{e}) \times$ 최고의 시드 집합에 의한 전파의(평균) 크기 $\approx 0.632 \times$ 최고의 시드 집합에 의한 전파의 (평균) 크기
    • 즉, 탐욕 알고리즘으로 시드 집합의 평균 전파 크기가 최고의 시드 집합에 의한 평균 전파 크기보다 적어도 0.632배 된다는것이 수학적으로 증명되있다
  • 다시 말해, 탐욕 알고리즘의 최저 성능은 수학적으로 보장되어 있다