-
정의
한정된 예산(k명의 초기 시작점)으로 네트워크에서 최대한 많은 사람에게 영향을 미치고 싶을 때, 어떤 사람들을 선택해야 하는지를 찾는 문제입니다. -
실제 예시: 대학교 축제 홍보 상황
상황: 축제 홍보대사 3명을 선발해야 함 (k=3)
목표: 최대한 많은 학생들에게 축제 정보를 전달
네트워크 구조:
학생A: 친구 100명 (but 대부분 같은 과 친구)
학생B: 친구 50명 (다양한 과 친구들)
학생C: 친구 80명 (동아리 임원)
학생D: 친구 30명 (기숙사 자치회장)
학생E: 친구 70명 (총학생회 임원)- 고려해야 할 요소들
- 단순히 친구가 많다고 좋은 것이 아님
- 네트워크의 다양성이 중요
- 중복되는 친구 관계 고려
- 각 관계에서의 영향력 확률
- 실제 선택 과정 예시
잘못된 선택:
- A, C, E 선택 (친구 수가 가장 많은 3명)
- 문제점: 세 학생의 친구들이 많이 겹침
- 실제 도달 가능 학생 수: 150명
좋은 선택:
- B, D, E 선택
- 장점:
- B: 다양한 과 학생들에게 전파
- D: 기숙사 학생들에게 전파
- E: 총학생회 네트워크 활용
- 실제 도달 가능 학생 수: 230명
- 문제의 특징
- NP-hard 문제: 최적의 해를 찾기가 매우 어려움
- 하지만 탐욕(Greedy) 알고리즘으로 근사해를 찾을 수 있음
- (1-1/e) ≈ 63% 이상의 성능 보장
- 실생활 응용
신제품 출시 마케팅:
- 예산으로 3명의 인플루언서 선택 가능
- 단순히 팔로워 수가 많은 top 3를 선택하지 않음
- 서로 다른 분야/지역의 인플루언서 선택이 더 효과적
이처럼 전파 최대화 문제는 단순히 '영향력 있는 사람'을 찾는 것이 아니라, '서로 다른 그룹에 효과적으로 영향을 미칠 수 있는 최적의 조합'을 찾는 것이 핵심입니다.
자세한 예시
- 그래프에 |V|개의 정점이 있을 때 (V는 Vertex의 약자로 정점을 의미)
- 시드 집합의 크기를 k개로 제한하면
- 가능한 경우의 수는 (|V|)를 k개 선택하는 조합의 수: C(|V|,k)개
- 예시:
- 정점(노드)이 10,000개
- 시드 집합의 크기(k)가 10일 때
- 가능한 경우의 수: 2,743,355,077,591,282,538,231,819,720,749,000개
- 이 큰 수가 의미하는 것:
- 모든 가능한 조합을 다 시도해보는 것은 현실적으로 불가능
- 10,000개의 노드 중 10개만 선택하는 단순한 상황에서도 이렇게 많은 경우의 수가 발생
- 현대의 슈퍼컴퓨터로도 모든 경우를 계산하는 데 매우 오랜 시간이 필요
- NP-hard의 의미:
- 이 문제가 매우 어려운 계산 복잡도를 가진다는 것을 수학적으로 증명
- 최적의 해를 찾는 것이 현실적으로 불가능
- 따라서 근사 알고리즘을 사용해야 함
- 실제 활용에서의 시사점:
- 완벽한 해답을 찾으려 하지 말고, 좋은 근사해를 찾는 것이 중요
- Greedy 알고리즘 등의 효율적인 근사 방법 사용 필요
- 실제 상황에서는 휴리스틱이나 도메인 지식을 활용하여 해결
이처럼 이론적으로는 가능한 모든 조합을 확인해야 하지만, 실제로는 그것이 불가능하기 때문에 다른 효율적인 방법을 찾아야 한다는 것이 이 예시의 핵심입니다.
시리즈를 기반으로 작성하였습니다.