Chapter14. Influence Maximization in Networks

투빅스 13기 이예지

오늘은 네트워크에서 가장 많은 사람들을 activate할 수 있는 k명의 Influencer를 찾는 알고리즘에 대해 다룬다.

Viral Marketing

Fig 1.

우리는 익명의 리뷰어보다는 친한 친구 혹은 가족들을 더 신뢰한다. 만약 어떤 제품을 새롭게 추천받았다면 익명의 리뷰어가 쓴 글을 참고하기 보다는 주변 사람들이 추천해주는 제품을 사게 될 것이다.

Fig 2.

Viral Marketing이란, 다음과 같은 순서로 발생한다.

• 영향력있는 고객을 선정한다.

• 그 고객들에게 무료 샘플이나 할인 혜택을 제공한다.

• 사용한 제품을 주변 지인들에게 추천한다.

영향력있는 고객들이 제품에 대해 주변 지인들에게 추천만 잘 해준다면, 순식간에 입소문을 타서 지인의 지인, 지인의 지인의 지인, ... 등 빠르고 쉽게 제품이 팔릴 것이다.

그럼, 이러한 영향력있는 고객(Influencer)을 찾는 것이 쉬울까? 단순하게 생각했을 때, follower가 가장 많은 사람을 선택하면 되는 것 아닐까?

Fig 3.

follower가 많은 사람은 네트워크에서 degree가 높은 node라고 할 수 있다. 그러나, 단순히 degree가 높은 사람을 영향력있는 고객이라고 말할 수는 없다. 그 이유는 매우 강하게 연결되어 있는 집단의 경우, 즉 connectivity가 강한 집단들은 node의 degree가 매우 높다. 이런 사람들에게 viral marketing을 했을 경우 해당 집단에만 퍼질 뿐 더 많은 사람들에게 뻗어나가지 못 할 것이다.

따라서, 단순하게 degree가 높은 사람을 선택하여 viral marketing을 한다면 더 많은 이익을 얻지 못할 것이다. 결론적으로 말하자면, 실제 매우 큰 네트워크에서 영향력있는 고객들에게 영향을 받는 사람들(influenced people)을 가장 크게 만들 수 있는 k명의 사람을 선택하는 것은 쉬운 일이 아니다.

우리는 이러한 k명의 가장 영향력있는 사람들을 찾는 프로세스를 Influence Maximization이라고 한다.

Two Classical Propagation Models

Influence maximization의 두가지 classical models은 다음과 같다.

• Linear Threshold Model

• Independent Cascade Model

Linear Threshold Model

1. node에 random threshold $\theta_v$ ~ $U[0,1]$ 로 초기화 해준다.
2. node가 각각의 이웃 w로부터 영향을 받는 값을 $b_{v,w}$ 라고 할 때, 이 값을 모두 더해주면 $\sum_{w \;neighbor\; of\; v} b_{v,w} \le 1$ 이다.
3. node의 $\theta_v$보다 $\sum_{w \;neighbor\; of\; v} b_{v,w}$의 값이 더 크다면, 노드는 active하게 된다. 즉, 상품을 사게 되는 것이다.

Independent Cascade Model

• 각각의 edge (v, w)는 probability $p_{vw}$ 를 가지고 있다. 이때, $p_{vw}$는 노드 v가 노드 w에게 영향을 줄 확률이다. 즉, 노드 w가 노드 v에게 영향을 받아 상품을 살 확률이다.
• 노드 v가 active라면, 노드 w를 active하게 만들 단 한 번의 기회(one chance)를 얻게 된다.

1. 초기에 node의 subset $S$가 active한다.
2. Subset $S$에 노드 v가 있다고 가정해보자. 노드 v가 $p_{vw}$의 확률로 노드 w를 activate한다.
3. Activation이 active 노드들을 타고 퍼져나가게 된다.

이때 우리가 찾고자 하는 influential set of size k은 $f(S)$를 최대화시켜야한다. 여기서 $f(S)$ 는 subset $S$에 의해 상품을 사게 되는 active node의 수이다. 즉, $f(S)=|\cup_{u\in S} X_{u}|$ 이다.

How hard is influence maximization?

Problem: Most influential set of size k를 찾자.

사실 most influential set of size k를 찾는 것, 즉 $\max_{S\;of\;size\;k}f(S)$ 를 만족시키는 optimal solution을 찾는 것은 NP-Complete problem이다.

따라서, 우리는 approximation algorithm을 사용하게 된다. 다행히도 greedy approximation algorithm을 활용하여 찾은 subset $S$ 는 $f(S)\ge0.63\;*\;f(OPT)$ 를 보장한다.

Hill Climbing(Greedy)

$X_{u}: u$가 active할 수 있는 node-set라고 할 때,

Input: $X_u$ Algorithm: 각 반복마다 $f(S)$ 를 크게 만드는 노드 u를 찾는다. 즉, $\max_{u} f(S_{i-1}\cup \{u\})$.

pseudo code는 다음과 같다.

각 iter마다 $f(S)$를 최대로 만드는 노드 u를 subset에 추가하므로, greedy한 것을 알 수 있다.

$f(\cdot)$ 의 두 가지 properties

• f는 단조함수이다. 즉, 줄곧 상승하거나 줄곧 하강한다.

• f는 submodular이다. 즉, large set과 특정 노드를 추가하였을 때 얻는 gain이 small set에 특정 노드를 추가하였을 때 얻는 gain보다 크지 않을 수 있다. 이는 overlap 때문에 발생한다.

Plan: Prove 2 things (1) Our f(S) is submodular

submodular는 다음과 같은 특징이 있다.

Basic fact 1:

Basic fact 2:

우리는 influence maximization을 set cover problem으로 정의할 수 있다.

Principle of deferred decision

f(S)를 확률적으로 접근했기 때문에 우리는 f(S)에 해당하는 parallel possible worlds를 만들 수 있고, 이걸 average함으로써 우리의 알고리즘(무작위 알고리즘)에 신뢰를 줄 수 있다.

1. 동시에 모든 edge에 해당하는 확률에 해당하는 coin을 flip하여 deterministic graph를 만든다. (active하지 않은 edge를 drop시키는 것임.)

2. 각각의 노드의 $X_u$를 구한다.
3. 위의 과정을 i번 반복한다.

우리의 알고리즘을 돌려 approximated most influential set of size k을 찾는다.

Plan: Prove 2 things (2) Hill Climbing gives near optimal solutions

Greedy 알고리즘을 사용했을 때 Principle of deferred decision을 이용하여, 위를 guarantee할 수 있었다. 자세한 내용은 cs224w에서 제공하는 handout을 참고하면 된다.

많은 iter를 할수록 알고리즘의 신뢰도는 높아질 것이다. 그렇다면, greedy 알고리즘의 시간복잡도는 어떻게 될까?

Speeding things up: Sketch-based Algorithms

지금까지 다룬 알고리즘은 possible worlds R개를 만들고, 각각의 world에서 influential set of size k를 찾았다. 만약 node set이 주어진다면, 그 set의 influence를 평가하는 것만 해도 $O(m)$이 소요된다.

따라서, 이 시간을 sketches를 활용해서 $O(m)\;to\;O(1)$ 으로 줄여보자.

1. 각각의 노드에 uniform random number를 할당한다.

2. 각각의 노드마다 도달할 수 있는 노드들 중 가장 작은 수를 가진 노드의 값으로 업데이트 해준다.

가정) 여기서 이 값이 작을수록 influence일 것이다. 직관적으로 내가 도달할 수 있는 노드가 많다면 더 작은 값을 작을 수 있을 것이고, 도달할 수 있는 노드가 많다는 것은 influence라는 것이다.

keep multiple ranks

그러나, 한 번의 iter는 신뢰할 수 없으므로 결국 위의 과정을 여러 번 반복하여(world를 여러 개 생성하여) 각 노드마다 특정 vector값을 할당하게 된다.

이 후 greedy 알고리즘 사용하여 influence maximization 문제를 풀게 된다.

Sketch-based Greedy 알고리즘도 마찬가지로 $(1-{1\over e}-\epsilon)$을 보장하지만, 이 때 중요한 것은 "1"이 optimal solution에 해당하는 것이 아니라, greedy 알고리즘을 기준으로 하는 것을 명심하자.

Experiments

당연하게도 SK-dim에서 dim이 클수록 running time이 증가하지만, 더 좋은 결과를 보여줌을 알 수 있다. 이 때 SK 알고리즘이 greedy 알고리즘보다 running time이 훨씬 적음에도 불구하고 비슷한 성능을 낸다는 것에 집중해보자.

2020-05-15 투빅스 13기 이예지