> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter14..md).

# Chapter14. Influence Maximization in Networks

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

## Viral Marketing

![Fig 1.](/files/-M7IHNW9ds_VqrHnzrSi)

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

![Fig 2.](/files/-M7IIhPYWkdU9cHE4vnK)

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

* 영향력있는 고객을 선정한다.
* 그 고객들에게 무료 샘플이나 할인 혜택을 제공한다.
* 사용한 제품을 주변 지인들에게 추천한다.

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

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

![Fig 3.](/files/-M7IJZzGn4BxGAemCXf8)

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

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

우리는 이러한  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이다.&#x20;

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

#### Hill Climbing(Greedy)

$$X\_{u}: u$$가 active할 수 있는 node-set라고 할 때,&#x20;

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

pseudo code는 다음과 같다.

![](/files/-M7IelScULwY6lWDnolB)

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

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

![](/files/-M7IbgAn67dAjtADnCEL)

* f는 단조함수이다. 즉,  줄곧 상승하거나 줄곧 하강한다.
* f는 submodular이다. 즉, large set과 특정 노드를 추가하였을 때 얻는 gain이 small set에 특정 노드를 추가하였을 때 얻는 gain보다 크지 않을 수 있다. **이는 overlap 때문에 발생한다.**

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

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

Basic fact 1:

![](/files/-M7Idj7E7YHEuIqxGs45)

Basic fact 2:

![](/files/-M7Ies3YfzDL11H8Ca51)

![](/files/-M7IevpTnSVXantGpMAx)

우리는 influence maximization을 **set cover problem**으로 정의할 수 있다.&#x20;

#### Principle of deferred decision

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

1. 동시에 모든 edge에 해당하는 확률에 해당하는 coin을 flip하여 deterministic graph를 만든다. (active하지 않은 edge를 drop시키는 것임.)
2. 각각의 노드의 $$X\_u$$를 구한다.&#x20;
3. 위의 과정을 i번 반복한다.

![](/files/-M7IimpNwx_ANrEpzAhF)

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

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

![](/files/-M7IjOq8Tra66aHLYMte)

![](/files/-M7IjSqZQ26VCqcbkJ8X)

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

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

![](/files/-M7IkSczQXPZuu_gWKu_)

## 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를 할당한다.

![](/files/-M7IoKrx9grpX5KlmUe9)

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

![](/files/-M7IoFZ2pZAbcRMCY2gA)

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

#### keep multiple ranks

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

![](/files/-M7IpMTbhbyyDRzN6rg2)

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

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

![](/files/-M7IqB5IjHF2csaeZyhB)

#### Experiments

![](/files/-M7IqOKCOp8GpOa14Fyg)

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

*2020-05-15 투빅스 13기 이예지*&#x20;