개요

Maximizing the Spread of Influence through a Social
Network
논문을 요약하여 정리한다.

소개

Social network plays a fundamental role as a medium for the spread of INFLUENCE among its members
* Opinions, ideas, information, innovation…

Direct Marketing takes the “word-of-mouth” effects to significantly increase profits (Gmail, Tupperware popularization, Microsoft Origami …)

문제 설정

  • Given
    • a limited budget B for initial advertising (e.g. give away free samples of product)
    • estimates for influence between individuals
    • 즉, 구전광고를 위해 쓸 돈 Budget이 있다고 가정
  • Goal
    • trigger a large cascade of influence (e.g. further adoptions of a product)
    • 즉, 개인들간의 영향력을 최대화 하는것이 목표
  • Question
    • Which set of individuals should B target at?
    • 즉, 어떤 개인에게 돈을 태워야 할까?
  • Application besides product marketing
    • spread an innovation
    • detect stories in blogs

Influence Model

  • 다른사람이 나로 인해 물건을 구매하게끔 될 정도의 영향력을 수치 개념으로 도입
  • 개인마다 Threshold가 있어 귀가 얇은 사람도 있고 귀가 얇지 않은 사람도 있다고 가정
  • 사람을 노드로 표현
  • 노드는 active/inactive로 표현(영향을 받았는지 안받았는지)
  • 활성화 노드는 다른 이웃 노드를 활성화 할 가능성이 있다.
  • 활성화 노드는 다시 비할성화 되지 않는다.

논문의 모델 해석

Word Of Mouth 마케팅을 위해 전세계 연예인중 10명에서 아이폰을 지급해서 가장 영향력을 크게 마케팅을 하고 싶다고 치자. 이 논문에서 얘기하는 기법은 아래와 같다.

  1. 레이디 가가(가장 영향력이 큰 연예인이라고 가정하면)에서 아이폰을 주고 여기에 영향을 받은 사람들을 네트워크에서 지운다.
  2. 그다음으로 영향력이 큰사람에게 아이폰을 주고 마찬가지로 영향 받은 사람을 지운다.
  3. 마찬가지로 반복하여 총 10명에게 아이폰을 지급한다.

그러면 이 10명이 가장 영향력이 큰 1~10위의 사람이 되기 보다는 1위, 10위 등등으로 뽑힐 수 있다.

위의 방법은 Greedy 알고리즘으로써 Optimal한 알고리즘은 아니지만 (예를 들어) 70% 정도의 최적의 결과를 도출할 수 있다라는 의미이다. 즉 전혀 의미없는 동떨어진 성능을 보이지는 않는다는 것이 핵심이다.

예제 보기

아래와 같은 그래프가 있다고 가정해보자.
각각의 그래프는 아래와 같은 가중치를 가진다.

각각의 노드는 파란색의 임계치를 가지고 있다. 이웃노드의 활성도인 빨간색이 파란색을 넘으면 해당 노드가 활성화 된다.

v(레이디가가)가 W와 U에 영향도를 전달했다(아이폰을 샀다). 임계치가 낮은 W는 임계치가 높은 U보다 더 크게 영향을 받아 Active neighbors가 더 높게 증가했다.

여기에 영향을 받은 W가 임계치보다 active neighbors가 높아지면서 활성화 되었다.(따라서 아이폰을 샀다.) 노드 활성화는 Active neighbors가 임계치 보다 커지면 노드 자신이 활성화 된다.

다시 W가 영향력을 X와 U에 전달했다.

이에 따라 이웃을 활성화 하는 지수가 더 증가했다.
결국 Active neighbors가 임계치를 넘어 U가 active 되었다.(추상적 해석인 주위에서 사는 사람이 늘어나니까 결국은 영향을 받아 아이폰을 샀다.)

또한 U는 영향도를 X와 제일 위의 노드에 전달했다.

이에 따라 다시 Active neighbors가 임계치를 넘어 X가 활성화 되었다.

X가 다시 영향도를 제일 위쪽 노드에 전달한다. 이후 더이상은 영향도를 전달할 노드가 없으므로 끝이 난다.