🔏
Tobigs Graph Study
  • Tobigs Graph Study
  • Chapter1. Machine Learning with Graphs
    • Python code - graph basic
  • Chapter2. Properties of Networks, Random Graph Models
    • Python code - kronecker product
  • Chapter3. Motifs and Structural Roles in Networks
    • Python code - RoIX & ESU Tree
  • Chapter4. Community Structure in Networks
  • Chapter5. Spectral Clustering
  • Chapter6. Message Passing and Node Classification
  • Chapter7. Graph Representation Learning
  • Chapter8. Graph Neural Networks
  • Chapter9. Graph Neural Networks:Hands-on Session
  • Chapter10. Deep Generative Models for Graphs
  • Chapter11. Link Analysis: PageRank
  • Chapter12. Network Effects and Cascading Behavior
  • Chapter13. Probabilistic Contagion and Models of influnce
  • Chapter14. Influence Maximization in Networks
  • Chapter15. Outbreak Detection in Networks
  • Chapter16. network evolution graph
  • Chapter17. Reasoning over Knowledge Graphs
  • Chapter18. Limitations of Graph Neural Networks
  • Chapter19. Applications of Graph Neural Networks
Powered by GitBook
On this page
  • Viral Marketing
  • Two Classical Propagation Models
  • How hard is influence maximization?
  • Plan: Prove 2 things (1) Our f(S) is submodular
  • Plan: Prove 2 things (2) Hill Climbing gives near optimal solutions
  • Speeding things up: Sketch-based Algorithms

Was this helpful?

Chapter14. Influence Maximization in Networks

투빅스 13기 이예지

PreviousChapter13. Probabilistic Contagion and Models of influnceNextChapter15. Outbreak Detection in Networks

Last updated 5 years ago

Was this helpful?

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

Viral Marketing

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

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

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

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

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

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

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

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 θv\theta_v θv​ ~ U[0,1]U[0,1]U[0,1] 로 초기화 해준다.

  2. node가 각각의 이웃 w로부터 영향을 받는 값을 bv,wb_{v,w}bv,w​ 라고 할 때, 이 값을 모두 더해주면 ∑w  neighbor  of  vbv,w≤1\sum_{w \;neighbor\; of\; v} b_{v,w} \le 1∑wneighborofv​bv,w​≤1 이다.

  3. node의 θv\theta_v θv​보다 ∑w  neighbor  of  vbv,w\sum_{w \;neighbor\; of\; v} b_{v,w} ∑wneighborofv​bv,w​의 값이 더 크다면, 노드는 active하게 된다. 즉, 상품을 사게 되는 것이다.

Independent Cascade Model

  • 각각의 edge (v, w)는 probability pvwp_{vw}pvw​ 를 가지고 있다. 이때, pvwp_{vw}pvw​는 노드 v가 노드 w에게 영향을 줄 확률이다. 즉, 노드 w가 노드 v에게 영향을 받아 상품을 살 확률이다.

  • 노드 v가 active라면, 노드 w를 active하게 만들 단 한 번의 기회(one chance)를 얻게 된다.

  1. 초기에 node의 subset SSS가 active한다.

  2. Subset SSS에 노드 v가 있다고 가정해보자. 노드 v가 pvwp_{vw}pvw​의 확률로 노드 w를 activate한다.

  3. Activation이 active 노드들을 타고 퍼져나가게 된다.

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

How hard is influence maximization?

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

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

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

Hill Climbing(Greedy)

Xu:uX_{u}: uXu​:u가 active할 수 있는 node-set라고 할 때,

Input: XuX_uXu​ Algorithm: 각 반복마다 f(S)f(S)f(S) 를 크게 만드는 노드 u를 찾는다. 즉, max⁡uf(Si−1∪{u})\max_{u} f(S_{i-1}\cup \{u\})maxu​f(Si−1​∪{u}).

pseudo code는 다음과 같다.

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

f(⋅)f(\cdot)f(⋅) 의 두 가지 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. 각각의 노드의 XuX_uXu​를 구한다.

  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)O(m)O(m)이 소요된다.

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

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

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

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

keep multiple ranks

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

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

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

Experiments

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

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

Fig 1.
Fig 2.
Fig 3.