[DAY 22] 전파모형과 전파 최대화 문제
그래프를 통한 정보, 행동, 고장, 질병 등의 전파에 대해서 나타낼 수 있다.
수학적 모형화를 통해서 전파 과정에 대해서 설명한다.
- 두 가지 전파 모형
- 의사결정 기반의 전파모형
- 확률적 전파모형
의사결정 기반의 전파모형
- 언제 의사결정 기반의 전파모형을 사용할까? : 라인 vs 카카오톡?
- 의사결정 기반의 전파 모형의 대표적인 예시, 선형 임계치 모형
전파모형이 필요한 이유
- 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미친다.
- 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용한다.
선형 임계치 모형(Linear Threshold Model)
- 원래 식은 $apN$ 과 $b(1-p)N$을 비교하는 것이지만, 이웃의 수 N은 양 변에서 지워진 것이다.
- p는 A를 선택할 확률이고 q는 임계치이다.
- $p > q$ 일 때, A를 선택한다.
- 위와 같은 모형을 선형 임계치 모형이라고 한다.
- 각 정점은 이웃 중 𝐴를 선택한 비율이 임계치 𝑞를 넘을 때만 𝐴를 선택한다.
- 이 모형은 전부 (기존 기술)𝐵를 사용하는 상황을 가정합니다
- 그리고 처음 (새로운 기술)𝐴를 사용하는 얼리 어답터들을 가정합니다
- 시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 𝐴를 고수한다고 가정하자.
- 임계치 𝑞는 55%를 가정해보자. 𝑢와 𝑣가 시드 집합인 상황이다.
- 이웃 중 A를 선택한 비율이 임계치인 55%를 넘어가는 경우, 자신을 A로 바꾼다.
- (= 연결된 것 중 A와의 연결이 우세한 쪽은 A로 선택을 바꿨다.)
확률적 전파 모형 (Independent Cascade Model)
- 언제 확률적 전파 모형을 사용할까?
코로나의 전파 과정에서, 의사결정 기반 모형은 적합하지 않다. 누구도 코로나에 걸리기로 ‘의사결정’을 내리는 사람은 없기 때문이다. 코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야 한다.
- 확률적 전파 모형의 대표적 예시: 독립적 전파 모형
- 방향성이 있고 가중치가 있는 그래프를 가정하자.
- 각 간선 (𝑢,𝑣)의 가중치 𝑝𝑢𝑣는 𝑢가 감염되었을 때 (그리고 𝑣가 감염되지 않았을 때) 𝑢가 𝑣를 감염시킬 확률에 해당한다.
- 즉, 각 정점 𝑢가 감염될 때마다, 각 이웃 𝑣는 𝑝𝑢𝑣확률로 전염된다.
- 서로 다른 이웃이 전염되는 확률은 독립적
- 𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑢가 감염되었을 때 𝑢가 𝑤를 감염시킬 확률과 독립적이다.
- 𝑢가 감염되었을 때 𝑢가 𝑣를 감염시킬 확률은 𝑤가 감염되었을 때 𝑤가 𝑣를 감염시킬 확률과 독립적이다.
- 모형은 모델은 최초 감염자들로부터 시작한다.
- 이전 모형과 마찬가지로 첫 감염자들을 시드 집합(Seed Set) 이라고 부른다.
- 각 최초 감염자 𝑢는, 각 이웃 𝑣에게 𝑝𝑢𝑣확률로 병을 전파한다.
- 위 과정을 새로운 감염자 각각에게 반복
- …
- 더 이상 새로운 감염자가 없으면 종료
- 이때, 감염자는 계속 감염자 상태로 남아있는 것을 가정한다.
- 감염자의 회복을 가정하는 SIS, SIR 등의 다른 전파 모형도 있음!
전파 최대화 문제 (Influence Maximization - 바이럴 마케팅)
- 바이럴 마케팅: 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법
- 바이럴 마케팅이 효과적이기 위해서는 소문의 시작점이 중요하다. 시작점에 따라 소문이 전파되는 범위가 영향을 받기 때문이다. 소셜 인플루언서들이 높은 광고비를 받는 이유이다.
- 어떤 시드집합(수 외에도 어떤 정점을 고르느냐 또한 중요)인지가 전파 크기에 많은 영향을 미친다.
- 예시
- x, y의 이웃을 보면, 그 이유를 알 수 있다.
🔍 그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부른다.
- 전파 모형으로는 앞서 배운 선형 임계치 모형, 독립 전파 모형을 포함 다양한 모형을 고려할 수 있다.
정점 중심성 휴리스틱
- 전파 최대화 문제는 굉장히 어려운 문제이다! 따라서 최고를 찾는 것을 포기하고 휴리스틱을 사용하자.
- 휴리스틱: 실험적으로는 잘 동작할 수 있지만, 이론적으로는 정확도에 대해서 어떠한 보장도 할 수 없음
정점의 중심성(Node Centrality) (대표적인 방법, 휴리스틱)
- 시드 집합의 크기가 𝑘개로 고정되어 있을 때, 정점의 중심성이 높은 순으로 𝑘개 정점(시드) 선택하는 방법
- 정점의 중심성으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있다.
- 합리적인 방법이지만, 최고의 시드 집합을 찾는다는 보장은 없다.
- 정점의 중심성 방법
- 페이지랭크 점수
- 연결 중심성: 연결성이 높은 정점에 높은 중심성을 부여
- 근접 중심성: 다른 정점들과의 평균거리를 측정해서 평균거리가 작은 쪽이 높은 중심성
- 매개 중심성: 정점간 최단경로 고려, 최단경로에 많이 놓이는 정점일수록 많은 정점 쌍을 연결하니까, 중심성이 크다.
탐욕 알고리즘 (Greedy Algorithm)
- 탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택한다.
즉, 정점의 집합을 {1,2,…, 𝑉 }라고 할 경우 구체적인 단계는 다음과 같다.
집합 {1}, {2}, … s, { 𝑉 }를 비교하여 (크기: $ V $), 전파를 최대화하는 시드 집합을 찾는다. - 이 때, 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균 값을 사용합니다 뽑힌 집합을 {𝑥} 라고 하자. → x는 최초 전파자 중 한 명이 되었다!
집합 {𝑥, 1}, {𝑥, 2}, … , {𝑥, 𝑉 }를 비교하여 (크기: $ V -1$), 전파를 최대화하는 시드 집합을 찾는다. 뽑힌 집합을 {𝑥, 𝑦} 라고 하자. → y가 두번째 최초 전파자로 선정되었다!
집합 {𝑥, 𝑦, 1}, {𝑥, 𝑦, 2}, … , {𝑥, 𝑦, 𝑉 }를 비교하여, 전파를 최대화하는 시드 집합을 찾습니다 뽑힌 집합을 {𝑥, 𝑦, 𝑧} 라고 하자. - 위 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복한다.
- 즉, 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고, 근시안적으로 최초 전파자를 선택하는 과정을 반복한다.
- 최초전파자를 한번에 한 명씩 선택한다는 것이다.
- 한계: 따라서 최고의 seed 집합이라는 보장을 할 수 없다.
- 그러나 독립 전파 모형인 경우, 이론적으로 정확도가 일부 보장된다.
- 항상, 즉 입력 그래프와 무관하게 다음 부등식이 성립한다.
- 다시말해, 항상 최고를 보장하지는 않지만, 최저 성능은 수학적으로 보장되어있다.(어느정도 성능은 보장한다.)
- 항상, 즉 입력 그래프와 무관하게 다음 부등식이 성립한다.
Abstract
- 그래프를 통한 전파의 예시 – 정보,행동,고장,질병등
- 의사결정 기반의 전파 모형 – 각각의 정점이 개인의 행복을 최대화하도록 의사결정하는 상황을 모형화 – 대표예시:선형임계치모형
- 확률적 전파 모형 – 질병의전파등확률적과정을모형화 – 대표예시:독립적전파모형
- 바이럴 마케팅과 전파 최대화 문제 – 전파를 최대화하는 시드 집합을 찾는 문제 – 정점 중심성 휴리스틱, 탐욕 알고리즘 등