Maximizing the Spread of Influence through a Social Network

본 게시물은 Maximizing the Spread of Influence through a Social Network, David Kempe, Jon Kleinberg, Ev´ a Tardos를 읽고 작성한 글입니다.

 

1. Title

Maximizing the Spread of Influence through a Social Network

 

2. Abstract

알고리즘의 근본 문제, 만약 개인이 새로운 제품을 사도록 설득하고, 연쇄 반응을 촉발하고 싶다면 어떤 개인 집합을 대상으로 할까.

'가장 영향력 있는 노드' 선택 문제는 NP-난해, 하위 모듈러 함수 기반 분석 프레임워크 사용으로 접근할 것

'근사 알고리즘'이 증명 가능한 것 외에도 성능이 좋다는 점이 있다.

 

3. 목표

SNS 영향력 최대화를 위한 타겟 탐색

 

4. 방법

[모델]

(1) 두 단계 시딩 모델

- 1단계 : 초기 접근 가능 사용자에게 할인 제공으로 에이전트 모집

- 2단계 : 새로운 접근 가능 사용자들에게 할인 제공으로 더 큰 영향력 확산 유도

(2) 독립 캐스케이드 모델

- 각 엣지마다 독립적 확률로 영향력 전파

- 한 번 활성화된 노드의 상태는 불변

(3) 선형 임계값 모델

-  각 노드는 임계값이 있고, 활성화된 이웃 노드들의 가중치 합이 임계값 초과시 활성화

- 노드 활성화가 이웃 노드들의 집합적 효과에 의해 결정되기에 노드 수준 피드백 모델링에 적합

(4) 트리거링 모델

- 독립 캐스케이드 모델과 선형 임계값 모델을 일반화한 모델

- 특징 :

각 노드가 자신의 이웃 노드 중 일부를 '트리거 집합'으로 선택

활성화 노드 집합 A가 주어지고, 만약 vi의 트리거 집합에 속한 이웃 노드 중 하나가 활성화되면 그 다음 시점에 vi가 활성화된다.

행렬 B의 원소 bij는 엣지(i, j)가 live(node i가 node j를 트리거 집합에 포함시킨 경우)일 확률을 나타낸다.

 

[알고리즘]

Greedy Hill-Climbing

(1) 하위 모듈성 활용

- 목표 : 영향력 함수가 하위 모듈성을 가진다는 것을 증명

- 하위 모듈성이란 : '어떤 집합에 요소 추가시 얻는 이득'은 그 집단이 이미 클수록 줄어든다.

- 이를 이용해 성능 보장 가능

(2) 탐욕적 알고리즘

- 내용 : 각 단계에서 영향력을 가장 증가시키는 노드를 집합에 추가하는 과정을 k만큼 반복해 k개의 노드를 찾는다.

(3) 근사 보장

- 최적해에 비해 63% 이상의 영향력을 갖는 해를 찾을 수 있다.

 

5. 결과

두 모델 모두 영향력 최대화 문제는 NP-hard

두 모델 모두 탐욕적 언덕 오르기 알고리즘은 약 63%의 근사 보장 -> 영향력 함수가 하위 모듈성을 가짐을 증명

탐욕적 언덕 오르기 알고리즘이 연결/거리 중심성 기반 노드 선택 휴리스틱보다 뛰어남

 

6. 향후 계획

으음?