주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에
의사결정 기반의 전파 모형을 사용합니다. 가장 간단한 형태의 의사결정 기반의 전파 모형인 선형 임계치 모형(Linear Threshold Model)을 소개합니다
p의 비율로 A, 1-p 비율로 B를 선택하였을때 u 는 를 만족할때 A를 선택할 것이다. 식을 정리하면 가 되고 이 때 편의상 q를 임계치라고 하자.
이 모형을 선형 임계치 모형(Linear Threshold Model) 라고 한다.
이 모형은 전부 B를 사용하는 상황을 가정합니다.그리고 처음 A를 사용하는 얼리 어답터들을 가정합니다.
시드 집합(Seed Set)이라고 불리는 얼리 어답터들은 항상 A를 고수한다고 가정합시다.
가장 간단한 형태의 확률적 전파 모형인 독립 전파 모형(Independent Cascade Model)을 소개합니다
바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내 게하는 기법입니다. 바이럴 마케팅이 효과적이기 위해서는 소문의 시작점(Seed Set)이 중요합니다. 시작점이 어디인지에 따라서 입소문이 전파되는 범위가 영향을 받기 때문입니다.
그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다
전파 최대화 문제는 굉장히 어려운 문제입니다.
그래프에 |V|개의 정점이 있을 경우, 시드 집합의 크기를 k개로제한하더라도 경우의 수는 개 입니다.
정점이 10,000개, 시드 집합의 크기를 10으로 고정합시다. 경우의 수는 무려 2,743,355,077,591,282,538,231,819,720,749,000개입니다. 이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명 되었습니다. 최고의 시드 집합을 찾는 것은 포기합시다. 그 대안으로 휴리스틱으로 정점의 중심성(Node Centrality), 탐욕 알고리즘(Greedy Algorithm)를 소개하려고 합니다.