그래프 전파 모형3 - 전파 최대화 문제(influence maximization)

1. viral marketing

 

소비자들로 하여금 상품에 대해 긍정적인 입소문을 내게하는 기법

 

효과적으로 상품 정보가 소비자들에게 알려질려면 소문의 시작점이 중요하다.

 

시작점에 따라 입소문이 전파되는 범위가 달라지기 때문이다.

 

 

2. importance of seed set

 

SNS 인플루언서들이 높은 광고비를 받는 이유가 있다.

 

전파 모형에서 첫 시작점을 seed set이라고 부르는데 viral marketing에서는 이 시작점을 잘 선택해야 광고 효과를 극대화할 수 있다.

 

 

 

케이트 미들턴을 광고 모델로 선택했더니 판매량이 급증했다

 

선형 임계치 모형에서도 seed set의 중요성을 볼 수 있는데 처음에 u와 v를 선택했을 때 총 9명(7명 전파)이 A를 선택했다.

 

 

 

 

만약 위 모형에서 다음과 같이 x,y라는 다른 점을 seed set으로 잡는다면? 추가적인 전파가 발생하지 않는다

 

 

 

3. influence maximization

 

그래프, 전파 모형, 시드집합의 크기가 주어졌을 때 전파를 최대화하는 시드집합을 찾는 문제

 

여기서 전파 모형은 선형 임계치 모형, 독립 전파 모형 등등 가능한 여러가지 전파 모형중 하나를 말한다.

 

 

 

 

전파 최대화 문제는 NP-hard 문제임이 증명되었다.

 

NP-hard란 일일이 모든 경우의 수를 확인해보지 않으면 다항시간내에 풀 수 없는 문제를 말한다.

 

심지어 다항시간내에 풀 수 있는지 여부도 알려지지 않은 문제이다.

 

주어진 그래프에서 node가 v개이고 시드 집합의 크기가 k라고 한다면 가능한 시드 집합의 경우의 수는 vCk

 

v=10000이고 k=10이면

 

 

 

이렇듯 너무 많은 시간이 걸려 보통 정확한 방법으로 풀지 않고 근사적인 방법으로 풀고자 한다.

 

4. Heuristic algorithm

 

실험적으로는 합리적으로 잘 작동(심지어 성능도 좋음)하나 이론적으로 그것이 정답임을 보장하지 않는 알고리즘

 

1) node centrality

 

시드 집합의 크기가 k일때 node의 중심성(centrality)이 가장 높은 순서대로 k개를 선택하는 방법

 

node의 중심성으로는 페이지랭크 점수나 연결중심성,근접중심성,매개중심성 등이 있다.

 

https://deepdata.tistory.com/219

그래프에서 중심성(centrality)의 척도들

 

 

연결중심성은 node의 연결성이 큰 정도

 

근접중심성은 한 node에서 다른 node까지 평균거리가 작을수록 높다

 

매개중심성은 그래프의 특정 node를 제외한 나머지 node쌍의 최단경로에 특정 node가 얼마나 놓여있는지 비율로 계산

 

지표의 설명을 보면 합리적으로 좋아보이나 이론적으로 정답이라는 보장은 없다

 

 

2) greedy algorithm

 

시드 집합의 크기가 k일 때 한번에 한명씩 구성하는 방법을 말한다.

 

한 순간에 최선이라고 생각하는 전파자를 구성하면서 k명을 만들어내는 방법이다.

 

당연하지만 순간 순간에는 최선이라고 선택했지만 전체에서 그것이 정답이라는 보장은 없다.

 

그래프의 node의 집합이 {1,2,3,...,v}라고 하면 먼저 크기가 1인 node의 모든 집합 {1},{2},{3},...,{v}를 고려한다.

 

이들 전파 크기를 비교하여 최대 전파를 가지는 집합 {x}를 첫번째 시드로 구성한다.

 

확률적으로 전파되는 경우가 보통이기때문에 시뮬레이션을 통해 각 집합의 전파 능력을 여러번 측정하여 평균을 내

 

그들 중 최댓값을 가지는 집합을 시드 집합으로 선택

 

{x}를 시드 집합으로 구성했으면 v-1개의 크기 2인 집합 {x,1}, {x,2}, {x,3},...{x,x-1},{x,x+1},...,{x,v}으로부터 위와 같은 과정을 반복

 

{x,y}가 전파 최대화 집합이었다면 마찬가지로 크기 3인 집합 {x,y,1},{x,y,2},....{x,y,v}중에서 전파 크기가 최대인 집합을 선택

 

......

 

이런식으로 크기가 k인 집합이 된다면 과정을 종료한다.

 

당연하지만 전파자들간 조합 예를 들어 첫번째 x를 선택할 때 x,y의 조합을 고려하지 않았기 때문에

 

순간 순간에서는 최적이었을지 몰라도 전체로 보면 최적의 집합을 만들어내는 것은 아니다.

 

만약 독립전파모형을 가정한다면, 수학적으로 탐욕 알고리즘으로 선택한 시드 집합의 성능이 60%정도는 보장한다는 사실이 알려져있다.

 

 

 

다른 모형은 최저 성능이 좋냐 생각해봤는데

 

일일이 그걸 다 증명했겠냐

 

최적은 아니더라도 합리적으로 잘 작동하니까 휴리스틱이다