[그래프] 4-1. 그래프를 통한 전파 : 의사결정 기반의 전파모형

그래프를 통해 다양한 것들이 전파되고 상호작용한다.
온라인 소셜 네트워크를 통해 정치 상황, 과학 정보, 챌린지 등 다양한 정보, 행동이 전파되고, 컴퓨터 네트워크 장비 고장의 전파, 파워 그리드의 정전 등의 고장이 전파될 수도 있다. 또한 코로나19, 사스, 메르스 등의 질병 전파도 그래프를 통한 전파로 설명될 수 있다. 

전파 과정은 다양하고 매우 복잡한데 이를 이해하고 대처하기 위한 많은 수학 모형 중 두 가지를 살펴보려 한다. 

---

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

• 주변 사람들의 의사 결정이 본인의 의사결정에 영향을 미치는 경우 사용
• 예를 들어 어떤 메신저(e.g., 카카오톡, 라인 메신저)를 사용할지, 어떤 충전기 포트를 도입할지 등은 주변 상황이 의사결정에 영향을 미친다
• 가장 간단한 형태로 선형 임계치 모형(Linear Threshold Model)이 있다

 

---

 2. 선형 임계치 모형

1. 상황 추상화

두 사람 u, v는 서로 호환되지 않는 기술 A, B를 선택해야 한다.
둘 모두 A 기술을 사용할 경우 행복이 a 만큼 증가하고, 둘 모두 B 기술을 선택할 경우 행복은 b 만큼 증가한다.
하지만, 서로 다른 기술을 사용하는 경우 행복이 증가하지 않는다.

 

2. 소셜 네트워크의 경우

소셜 네트워크에서 친구를 맺을 때 이웃을 맺음으로써 발생하는 행복을 고려해야 한다.
u가 A를 선택 시 행복이 2a만큼 증가하고, B를 선택 시 행복이 3b만큼 증가한다고 가정해보자.

행복이 최대화 되는 선택을 해야 한다면 아래와 같이 선택한다고 하자.
if 2a > 3b, then select A
if 2a < 3b, then select B
if 2a = 3b, then select B

3. 일반화 : 선형 임계치 모형

여기서 좀 더 일반화 해서 p비율의 이웃이 A를 선택하고 (1-p) 비율의 이웃이 B를 선택한다고 해 보자. 
이 때는 언제 A를 선택해야 할까?
바로 ap > b(1-p)일 때 A를 선택할 것이다. 
정리하면 $p > \frac{b}{a+b}$이고 이때, $\frac{b}{a+b}$를 임계치 q라고 하자.

각 정점이 이웃 중 A를 선택할 확률은 A를 선택한 비율이 임계치 q를 넘을 때만 A를 선택한다.

이 모형을 선형 임계치 모형이라고 한다. 
이 모형은 전부 B를 사용하는 상황을 가정하고 있고, 처음 A를 사용하는 얼리 어답터들을 가정한다. 이 얼리 어답터의 집합을 시드집합(Seed Set, 주변의 선택과 상관없이 항상 A를 고수)이라고 한다.

 

4. 예제

• 임계치 q = 55%
• u, v : A를 선택한 얼리어답터
• 아래와 같은 과정으로 A를 선택한 이웃의 비율이 임계치를 초과하면 본인의 선택도 A로 바꿈. 

 

 

---

edwith의 그래프와 추천 시스템 강의를 듣고 정리 한 내용입니다.

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith