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

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

1) 그래프를 통한 정보/행동의 전파

온라인 소셜 네트워크를 통해 다양한 정보가 전파된다. 사회 운동이 트위터를 통해 전국적으로 알려져 시민들이 정부의 부정부패에 맞서 연대할 수 있고, 유용한 과학적 정보가 전파되기도 한다.

온라인 소셜 네트워크를 통해 다양한 행동도 전파된다. 흔히 알고 있는 아이스 버킷 챌린지, 펭귄 문제 등이 그것이다.

2) 그래프를 통한 고장의 전파

컴퓨터 네트워크에서 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수도 있다. 일부 장비의 고장이 다른 장비의 과부하로 이어지며 이것이 전체 네트워크의 마비를 불러오기 때문이다. 파워 그리드에서 정전이 전파되는 과정도 컴퓨터 네트워크의 고장이 전파되는 과정과 유사하다.

(3) 그래프를 통한 질병의 전파

최근에는 거대한 소셜 네트워크인 사회를 통해 질병이 전세계적으로 전파된다. 코로나19, 메르스, 사스 등이 있다.

➡ 매우 복잡하고 다양한 전파 과정을 이해하고, 체계적으로 대처하기 위해서는 수학적 모형화가 필요하다. 해당 수업에서는 의사결정 기반의 전파 모형과 확률적 전파 모형이라는 크게 두 가지 수학적 모형을 다룬다.

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

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

주변 사람들의 의사결정이 본인의 의사결정에 영향을 미친다. 일례로, 우리는 다른 사람들이 라인 대신 카카오톡을 쓰기 때문에 카카오톡을 쓰는 것이 편해 카카오톡을 쓰고, 다른 사람들이 CD 대신 USB를 쓰기 때문에 서로 빌려줄 수 있는 USB를 사용한다. 이처럼 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용한다. 그리고 이 의사결정 기반의 전파 모형의 가장 간단한 형태로 선형 임계치 모형이 있다.

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

u와 v라는 사람이 있다고 가정하자. 이 둘은 두 개의 호환되지 않는 기술 A와 B 중에서 하나를 선택하여 활용한다. 둘 모두 A 기술을 사용할 경우, 각각의 행복이 a만큼 증가한다. 둘 모두 B 기술을 사용할 경우, 각각의 행복이 b만큼 증가한다. 하지만 둘이 서로 다른 기술을 사용할 경우에는 행복이 증가하지 않는다. 이를 모형으로 나타내면 다음과 같다.

이번에는 u가 소셜 네트워크 상에 있다고 가정해보자. u는 동시에 여러 사람과 친구 관계를 맺기 때문에, 소셜 네트워크 상의 이웃과의 사이에서 발생하는 행복을 모두 고려해야 한다. 위의 예시와 마찬가지로 생각해보면, u가 A를 선택할 경우 행복이 2a만큼 증가하고, u가 B를 선택할 경우 행복이 3b만큼 증가한다. 이때, 2a>3b라면 u는 A를 선택할 것이고, 2a<3b라면 u는 B를 선택할 것이다.

이를 일반화하면 임계치 q를 구할 수 있다. 비율 p의 이웃이 A를 선택했다고 가정하고, 비율 (1-p)의 이웃이 B를 선택했다고 가정하면 ap>b(1-p)일 때 A를 선택할 것이다. 이를 p에 대해서 정리하면 p>b/(a+b)이며, 이 b/(a+b)를 임계치 q라고 한다.

이 모형을 선형 임계치 모형이라고 한다. 즉, 각 정점은 이웃 중에서 A를 선택한 비율이 임계치 q를 넘을 때만 A를 선택한다.

그 다음 모형에서는 전부 B를 사용하는 상황을 가정해보자. 처음 A를 사용하는 얼리 어답터들이 존재하며, 시드 집합인 얼리 어답터들은 항상 A를 고수한다. 임계치 q가 55%이고 u와 v가 시드 집합이라면, 처음에는 이웃들 모두가 B를 사용하다가, 이웃 중 A를 선택한 비율이 임계치 55%를 넘는 이웃 4명이 추가적으로 A를 선택한다. 그리고 같은 방법으로 1명의 이웃이, 그리고 또 1명의 이웃이, 마지막으로 또 1명의 이웃이 추가로 A를 선택한다. 이 과정을 거치면 A를 택하지 않은 정점 중에서 이웃 중 A를 선택한 비율이 임계치 55%를 넘지 않는 사람을 제외하고는 모두 A를 선택하는 선형 임계치 모형이 나타난다. 이를 그림으로 나타내면 다음과 같다.

[ 이웃 중 A를 선택한 비율이 임계치를 넘지 않는 사람을 제외하고 모두 A를 선택한 상황]

3. 확률적 전파 모형

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

질병이 전파되는 전파 과정을 수학적으로 추상화해보면, 의사결정 기반 모형은 적합하지 않다. 대부분의 사람은 질병에 걸리기로 의사결정을 내리지 않기 때문이다. 즉, 질병이 전파되는 것은 확률적 과정이기 때문에 확률적 전파 모형을 고려해야 한다. 그리고 이 확률적 전파 모형의 가장 간단한 형태로 독립 전파 모형이 있다.

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

방향성과 가중치가 모두 있는 그래프를 가정해보자. 해당 그림에서 각 간선 (u, v)의 가중치 Puv는 u가 감염되었을 때, 감염되지 않은 v에게 u가 감염시킬 확률을 의미한다. 즉, 각 정점 u가 감염될 때마다 각 이웃 v는 Puv의 확률로 전염된다. 물론 여기에서 서로 다른 이웃이 전염되는 확률은 독립적으로 시행된다.

모형은 모델의 최초 감염자들로부터 시작한다. 첫 감염자들을 시드 집합이라고 하면, 최초 감염자 u는 각 이웃 v에게 Puv의 확률로 질병을 전파한다. 위의 그림에서는 a가 첫 감염자인 시드 집합이다. 감염자들이 이웃에게 Puv의 확률로 질병을 전파하는 과정을 계속 반복하다가 새로운 감염자가 더 이상 없으면 해당 모형의 반복을 종료한다.

확률적 전파 모형을 통한 질병의 전파 외에도 감염자의 회복을 가정하는 SIS, SIR 등의 전파 모형도 있다.

4강 - 전파 모델

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

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

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

3. 확률적 전파 모형