Centrality Algorithms
중심성이란, 모든 네트워크에서 어떤 노드가 더 중요한 지를 이해하는 것이다. 중심성 알고리즘은 정보를 신속하게 퍼뜨리는 능력을 가진 것을 중요하게 여기는 유형과 별개의 그룹을 결합하는 것을 중요하게 여기는 유형 등으로 나뉜다.
1. PageRank
(pageRank는 랜덤 서퍼 등의 개념과 함께 공식 계산 따로 정리 예정)
정의 및 적용
-
노드들의 전이적 영향(transitiveinfluence)이나 연결성을 측정하는 알고리즘
-
현재 노드의 중요성을 그 노드의 관계와 해당 노드로 링크되어 있는 이웃들로 평가함
사용 가능 그래프
Dircted/Undirected, Weighted/Unweighted 모두 지원함
사용 예시
-
팔로우할 만한 사람들을 추천해줄 때
-
공공 장소와 거리에서 교통 흐름과 이동 방향 예측
2. ArticleRank
정의 및 적용
-
PageRank의 변형으로 인용 네트워크에서 사용
-
PageRank를 기반으로 동작하며 인용 횟수로 해당 노드의 중요성을 평가함
사용 가능 그래프
Directed/ Undirected, Unweighted 지원
3. Betweenness Centrality
정의 및 적용
-
해당 노드가 그래프 내에서 얼마큼의 영향력을 가지는 지 측정하며 주로 한 그래프와 다른 그래프의 연결 부분을 찾을 때 사용함
-
BFS(breadth-first search)를 이용하여 각 노드 pair들의 최단경로를 계산
- 각 노드들은 shortest path가 많이 통과할수록 높은 score 부여 받음
- 시간 복잡도가 O(nm)이라서 큰 그래프에서는 근사 알고리즘(*RA-Brandes algorithm)을 사용
*전체 노드가 아닌 subset만 random 하게, 또는 차수 기준으로 추려내어 계산
사용 가능 그래프
Directed/Undirected, Unweighted 지원
사용 예시
-
네트워크의 주요 전송 지점 탐지
-
다양한 집단에서 인플루언서를 찾을 때
-
트위터 같은 곳에서 microblogger들에게 인플루언서를 추천할 때
4. Closeness Centrality
정의 및 적용
-
그래프 내의 어떤 노드가 정보를 효율적으로 퍼뜨릴 수 있는지 감지함
-
모든 노드 pair 간의 최단 경로를 계산하여 다른 모든 노드까지의 거리의 합계를 계산. 그 후 합계에 역을 취하여 해당 노드들의 score를 결정
-
높은 closeness centrality를 가진 노드들은 모든 다른 노드들에 가까이 위치함
사용 가능 그래프
Directed/Undirected, Unweighted 지원
사용 예시
-
기관에서 가장 closeness centrality가 높은 사람은 중요한 정보를 가지고 있거나 통제력이 있음
-
통신/택배 도착시간 예측
-
문서 내 단어들의 중요성 측정
5. Degree Centrality
정의 및 적용
-
해당 노드로 들어오고 나가는 관계들의 수를 계산
-
그래프 내에서 가장 선호되는 노드를 찾을 수 있음
사용 가능 그래프
Directed/Undirected,Unweighted 지원
사용 예시
-
가장 영향력 있는 개개인을 찾을 때
-
온라인 경매 사이트에서 사기꾼을 구별할 때
