본 게시물은 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. 향후 계획
으음?
