본 게시글은 Finding Effectors in Social Networks, Theodoros Lappas, Dimitrios Gunopulos, Evimaria Terzi, Heikki Mannila를 읽고 작성한 글입니다.
1. Title
Finding Effectors in Social Networks
2. Abstract
이미 일부 노드가 활성화된 네트워크 (V, E)가 있을 때, 이 활성화 상태를 가장 잘 설명하는 k개의 활성 노드 집합(effectors) 선택
다양한 유형의 그래프에 대해 effectors의 복잡성 연구,
임의 그래프에는 최적으로 해결하기 어렵고 근사도 NP-hard이지만,
특수 경우 동적 프로그래밍 알고리즘으로 다항 시간에 최적 해결 가능
3. 목표
SNS에서 정보 전파를 가장 잘 설명하는 핵심 노드 (Effectors) 찾기
다양한 유형의 그래프에서 k-Effectors의 복잡성 분석
4. 방법
- k-Effectors 문제
그래프, 활성화 백터, 정보 전파 모델 하에서 활성화 상태를 가장 잘 설명하는 k개의 노드 집합 탐색
- NP-hard 증명
k-Effectors 최적 해결 및 근사가 NP-hard임을 증명
이미 NP-complete로 알려진 'SET COVER' 문제를 포함하기 때문에 NP-hard가 된다.
*SET COVER : 여러 부분집합 모임에서 몇 개의 부분집합을 선택해 전체 집합을 커버 가능한
- 동적 프로그래밍 알고리즘
트리 구조 그래프에서 k-Effectors 문제를 최적 해결하는 알고리즘 제시
일반적인 트리 구조를 이진트리로 변환하여 알고리즘의 효율을 높인다.
Opt(v, S, k) : 노드 v를 루트로 하는 서브트리에서 최대 k개의 effector를 사용해 얻을 수 있는 최적의 비용. S는 선택된 effector 집합
앞의 경우는 v를 effector로 선택하지 않는 경우, 뒤는 선택하는 경우이다.
r(v)는 노드 v의 오른쪽 자식, l(v)는 왼쪽 자식이며, C(v, S)는 S의 effector들이 활성화됐을 때 노드 v에서 발생하는 비용이다.
이 재귀 관계식을 기반으로 DP가 작동하며,
리프 노드에 도달했을 때 effector 선택 여부에 따라 비용을 계산해 테이블에 저장하고, 루트 노드 방향으로 DP 테이블을 채운다.
여기서 최적 해는 루트 노드에서 계산된 Opt(root, {}, k)값이며, 이때 선택된 effector 집합을 추적해 최적 해를 구할 수 있다.
- 휴리스틱 알고리즘(최적 해 보장은 아니지만 합리적 시간 내에 '충분히 좋은' 해를 찾는 것)
트리 구조가 아닌 그래프에서 k-Effectors 문제 해결
(1) Sort 알고리즘
각 노드 v에 대해 v가 유일한 effector일 때 발생하는 비용 C({v}) 계산
|v로부터 정보전파시 노드x가 활성화될 확률 - 활성화 상태|로 구하는데, 따라서 이 값이 작을수록 잘 맞힌 것이다.
이 값을 기준으로 정렬 후, 비용이 가장 낮은 상위 k개의 활성 노드를 effector로 선택한다.
<구현이 간단하고 트리 구조에서 효율적이지만, 최적해를 보장하지 않으며 네트워크 구조에 따라 성능이 크게 차이남>
(2) OutDegree 알고리즘
각 활성 노드에 대해 가중치가 적용된 outdegreee를 계산 후, 이를 기준으로 활성노드를 정렬
outdegree가 가장 높은 상위 k개의 활성 노드를 effector로 선택한다
<계산이 빠르고 구현이 간단하지만, 최적해를 보장하지 않으며 네트워크 구조에 따라 성능이 크게 차이남>
'최적해를 보장하지 않는다'는 한계를 보완하기 위해, 트리 구조에서는 DP알고리즘으로 최적해를 구하고,
일반 그래프에서 most probable tree를 추출한 후, dp알고리즘을 적용해서 효율성/정확성 증가
5. 결과
- 일반 그래프에서 k-Effectors 문제를 최적 해결하거나 근사하는 것이 NP-hard임
- 동적 프로그래밍 알고리즘 개발
6. 향후계획
- 다양한 유형의 네트워크에서 effectors의 유용성 탐구
- 다양한 정보 전파 모델과의 결합 및 적용
- 실제 데이터셋에 대한 추가 실험 및 분석
