[그래프]4-3. 그래프를 통한 전파 : 바이럴 마케팅과 전파 최대화 문제

728x90

1. 바이럴 마케팅이란

시드 집합(소문의 시작점)이 전파 크기에 많은 영향을 미침. 즉, 시드 집합을 어떤 정점으로 구성하느냐에 따라 결과가 크게 달라질 수 있음.

이전 포스트에서 다뤘던 확률적 전파 모형에서 u, v를 시드 집합을 했을 경우 총 9명이 A를 선택하게 되었지만, 아래와 같이 x, y를 선택하는 경우 추가적인 전파가 이뤄지지 않아 총 2명만 A를 선택하게 됨

전파 최대화(Influence Maximization) 문제 : 그래프, 전파 모형, 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제
전파 모형으로는 선형 임계치 모형, 독립 전파 모형을 포함하여 다양한 모형을 고려할 수 있음
전파 최대화 문제는 매우 어려운 문제임
- 그래프에 |V|개의 정점, 시드 집합 크기가 k인 경우 : 경우의 수는 ${|V| \choose k} = _{|V|}C_{k} = \frac{|V|!}{k!(|V|-k)!}$
- 최고의 시드 집합을 찾는 것은 현실적으로 적용하기 불가능함. 정확하게 푸는 것보다 휴리스틱 또는 근사 알고리즘을 사용하여 최적의 시드 집합을 찾는 것이 좋음

대표적인 휴리스틱 방법
시드 집합의 크기가 k개로 고정 → 정점의 중심성이 높은 순으로 k개 정점을 선택하는 방법
합리적이지만 최고의 시드 집합을 찾을 수 있다거나 정확도에 대해 보장을 할 수는 없음
정점 중심성으로 다음의 방법을 사용할 수 있음
- 페이지 랭크 점수
- 연결 중심성: 연결성이 높은 중심성
- 근접 중심성: 다른 정점들과 평균 거리가 짧음
- 매개 중심성: 정점 간 최단경로 안에 많이 놓인 경우

최초 전파자를 한 번에 한 명씩 선택
정점의 집합을 {1, 2,..., |V|}라고 할 경우 단계는 다음과 같음
1. 크기가 1인 집합 {1}, {2},..., {|V|}를 비교하여 전파를 최대화하는 시드 집합을 찾음
  이때, 전파 크기 비교를 위해 반복의 평균값을 사용
  뽑힌 집합을 {x} (최초 전파자 중 1인)
2. 크기가 2인 집합 {x, 1}, {x, 2},..., {x, |V|}를 비교하여 전파를 최대화하는 시드 집합을 찾음
  뽑힌 집합을 {x, y}
3. 위 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복
독립 전파 모형의 경우 이론적으로 정확도가 일부 보장됨. 즉 탐욕 알고리즘의 최저 성능은 수항적으로 보장되어 있음
- 탐욕 알고리즘으로 찾은 시드 집합에 의한 전파의 (평균) 크기
  $\geq (1-\frac{1}{e}) \times$ 최고의 시드 집합에 의한 전파의 (평균) 크기
  $ \approx 0.632 \times$ 최고의 시드 집합에 의한 전파의 (평균) 크기
- 즉 최고 시드 집합보다 적어도 0.632배 이상 성능이 보장

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

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

- 부스트코스

www.edwith.org

728x90