정점의 중심성(Node Centrality)을 이용한 휴리스틱 접근 방법
- 기본 개념
- 휴리스틱: 최적해를 보장하지는 않지만, 실용적이고 효율적인 해결책을 찾는 방법
- k개 시드 선택: 주어진 제한된 수(k)만큼 초기 전파자를 선택하는 문제
- 주요 중심성 지표들
각각의 중심성을 실제 예시로 설명드리겠습니다:
A) 페이지랭크 점수 (PageRank)
- 구글의 웹페이지 순위 알고리즘과 동일한 원리
- 예시: 인스타그램 인플루언서
- 단순히 팔로워 수가 아닌, 팔로워의 영향력도 고려
- 영향력 있는 사람이 팔로우하는 계정이 더 높은 점수를 받음
B) 연결 중심성 (Degree Centrality)
- 직접적인 이웃 노드의 수
- 예시: 학교 학생회장
- 직접적으로 아는 학생 수가 많음
- 가장 계산하기 쉽지만, 깊이 있는 영향력은 측정 못함
C) 근접 중심성 (Closeness Centrality)
- 다른 모든 노드까지의 평균 거리가 가까운 정도
- 예시: 회사 중간 관리자
- 윗선과 아랫선 모두와 가까움
- 정보 전달이 빠르고 효율적
D) 매개 중심성 (Betweenness Centrality)
- 서로 다른 그룹을 연결하는 다리 역할
- 예시: 여러 동아리에 속한 학생
- 서로 다른 집단 간 정보 전달자
- 정보 흐름의 통제력이 큼
- 실제 적용 예시
카카오톡 그룹채팅방 정보 전파:
학생A: 연결 중심성 높음 (친구 많음)
학생B: 매개 중심성 높음 (여러 과 친구)
학생C: 페이지랭크 높음 (영향력있는 친구들)이 중 k=2명을 선택해야 한다면:
- 단순히 하나의 중심성만 보지 않음
- 여러 중심성 지표를 종합적으로 고려
- 네트워크의 특성에 따라 가중치 조정
- 한계점
- "합리적인 방법이지만, 최고의 시드 집합을 찾는다는 보장은 없습니다"
- 네트워크 구조가 복잡할수록 정확도 떨어짐
- 동적인 네트워크 변화를 반영하기 어려움
- 서로 다른 중심성 지표들 간의 상충관계 존재
이러한 휴리스틱 방법은 완벽한 해결책은 아니지만, 실제 현실에서 충분히 좋은 결과를 빠르게 얻을 수 있다는 장점이 있습니다.
시리즈를 기반으로 작성하였습니다.