그래프와 추천시스템(4. 전파모델)

의사 결정 기반의 전파 모형

주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에
의사결정 기반의 전파 모형을 사용합니다. 가장 간단한 형태의 의사결정 기반의 전파 모형인 선형 임계치 모형(Linear Threshold Model)을 소개합니다

선형 임계치 모형

p의 비율로 A, 1-p 비율로 B를 선택하였을때 u 는 $pa>(1-p)b$ 를 만족할때 A를 선택할 것이다. 식을 정리하면 $p> {b\over a+b} = q$ 가 되고 이 때 편의상 q를 임계치라고 하자.
이 모형을 선형 임계치 모형(Linear Threshold Model) 라고 한다.


이 모형은 전부 B를 사용하는 상황을 가정합니다.그리고 처음 A를 사용하는 얼리 어답터들을 가정합니다.
시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 A를 고수한다고 가정합시다.

확률적 전파 모형

가장 간단한 형태의 확률적 전파 모형인 독립 전파 모형(Independent Cascade Model)을 소개합니다

독립적 전파 모형

• 방향성이 있 고 가중치가 있는 그래프
• 서로 이웃에게 전파될 확률은 독립적
• 이전 모델과 마찬가지로 최초 전파자를 시드집합이라고 부름
  

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

바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내 게하는 기법입니다. 바이럴 마케팅이 효과적이기 위해서는 소문의 시작점(Seed Set)이 중요합니다. 시작점이 어디인지에 따라서 입소문이 전파되는 범위가 영향을 받기 때문입니다.


그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다


전파 최대화 문제는 굉장히 어려운 문제입니다.
그래프에 |V|개의 정점이 있을 경우, 시드 집합의 크기를 k개로제한하더라도 경우의 수는 ${|V|\choose k}$개 입니다.
정점이 10,000개, 시드 집합의 크기를 10으로 고정합시다. 경우의 수는 무려 2,743,355,077,591,282,538,231,819,720,749,000개입니다. 이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명 되었습니다. 최고의 시드 집합을 찾는 것은 포기합시다. 그 대안으로 휴리스틱으로 정점의 중심성(Node Centrality), 탐욕 알고리즘(Greedy Algorithm)를 소개하려고 합니다.

휴리스틱으로 정점의 중심성(Node Centrality)

• 정점 중심성이 높은 상위 k개의 정점을 선택하는 방법
• 정점 중심성으로는 페이지랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있음
• 합리적인 방법이지만 최고의 시드 집합을 찾는다는 보장은 없음

탐욕 알고리즘(Greedy Algorithm)

• 시드 집합의 원소를 한번에 하나씩 선택하여 목표 시드 집합의 크기에 도달할 때까지 반복
• 역시 최고의 시드 집합을 찾는다는 보장은 없음
• 하지만 독립 전파 모형의 경우, 이론적으로 정확도 일부가 보장됨
  탐욕 알고리즘으로 찾은 전파의 (평균)크기 >
  $(1-{1\over e})$ x 전파의 크기의 최대값의 (평균)크기