[Graph] Node importance의 종류

그래프 네트워크 이론에서 node importance는 

 

그래프 내의 특정 노드가 얼마나 중요한지를 측정하는 방법입니다. 

 

노드의 중요성은 다양한 지표로 측정될 수 있죠

 

그 중에서 주요하게 쓰이는 지표 8가지를 정리해보겠습니다.

---

1. Degree centrality

• 한 node에 직접 연결된 edge에 갯수를 의미합니다
• Degree centrality가 높은 node는 그래프 내에서 많은 다른 노드들과 직접적인 연결이 많이 되어 있으므로 중요한 node라고 할 수 있습니다.
• 예시: 소셜 네트워크(SNS)에서 한 사용자가 얼마나 많은 친구를 가지고 있는지 측정할 때 사용 

 

2. Closeness Centrality

• 특정 node와 그래프 내의 모든 다른 node 사이의 최단 경로의 평균으로 정의
• Closeness 값이 높을수록 다른 노드들과 거리상으로 근접하다는 것을 의미합니다.
• 예시: 전력 그리드에서 중요한 전력 교환 지점을 찾을 때 사용될 수 있다.

 

3. Betweenness Centrality

• 그래프 내의 모든 node 쌍 사이의 최단 경로 중, 특정 노드를 통과하는 경로의 비율을 기반으로 함
• 다른 노드들 간의 정보나 자원 전달에서 중요한 역할을 하는 노드를 찾을 때 유용
• 예시: 전송 네트워크에서 중요한 트래픽 교환 지점을 찾을 때 사용될 수 있음

 

4. Load Centrality

• Load Centrality는 각 node에 연결된 edge에 부여된 가중치 합을 나타냄, 이 가중치 합은 해당 node를 통해 흐르는 정보나 자원의 양을 표현
• Node의 Load Centrality가 높을수록 해당 node를 통해 많은 양의 정보나 자원이 흐르는 것을 나타냄, 따라서 Load Centrality가 높은 node는 네트워크 내에서 중요한 역할을 할 가능성이 큽니다.
• 예시: 전력 그리드에서 전력 공급이나 통신 네트워크에서 정보 전달의 핵심 경로를 찾는 데 활용될 수 있음 

 

5. Page Rank

• PageRank는 구글의 창업자 래리 페이지와 세르게이 브린에 의해 개발된 알고리즘으로, 웹 페이지의 상대적 중요도를 결정하는 데 사용
• PageRank는 다른 중요한 페이지로 링크되는 페이지가 더 중요하다고 가정, 따라서 많은 다른 페이지로부터 링크를 받는 페이지일수록 높은 PageRank를 가짐, 이를 재귀적으로 계산하여 모든 페이지의 중요도를 결정
• PageRank는 주로 검색 엔진에서 사용되며, 검색 결과의 순위를 결정하는 데 활용, 더 중요한 페이지가 상위에 나타나도록 하여 검색 결과의 품질을 향상시키는 데 기여함, 또한 네트워크 분석이나 연결성 분석에도 활용될 수 있습니다.

 

6. Katz Centrality 

• Katz Centrality는 노드 간의 연결 길이와 중요도를 동시에 고려하여 노드의 중요도를 평가하는 척도입니다. 직접 연결된 node보다 먼 node와의 연결에 대해 가중치를 감소시켜 반영하며, 중요한 노드로부터의 영향을 반영합니다.
• Katz Centrality는 정보 전달이 네트워크에서 먼 노드를 통해 이루어지는 경우에 중요한 노드를 찾을 때 유용, 예를 들어, 네트워크의 효율적인 정보 전달 경로를 찾거나, 중요한 노드 간의 영향력을 분석하고자 할 때 사용될 수 있음
• 예시: 도로, 철도, 통신 등의 인프라 구축 및 관리에서도 Katz Centrality를 활용할 수 있습니다. 인프라의 연결성과 중요도를 고려하여 중심지점을 판단하고, 여러 지역 간의 효율적인 연결을 돕는 데 사용될 수 있습니다.

 

7. Percolation Centrality

• Percolation Centrality는 네트워크 내에서 특정 노드를 제거했을 때, 네트워크의 연결성이 어떻게 변화하는지를 측정하여 노드의 중요도를 평가하는 척도입니다.
• 이 척도는 노드를 하나씩 제거하면서 네트워크 내에서 어떤 노드의 제거가 가장 큰 영향을 미치는지를 측정합니다. 중요한 노드일수록 제거될 때 네트워크의 연결성이 크게 변화하게 됩니다
• Percolation Centrality는 네트워크 내에서 핵심 노드나 잠재적인 고장 지점을 찾고자 할 때 사용됩니다. 네트워크의 강건성과 신뢰성을 평가하며, 비상 상황에서 네트워크의 연결성을 최대한 유지하기 위해 어떤 노드를 보호해야 하는지 판단하는 데 활용될 수 있습니다.
• 예시: 전력 그리드 네트워크에서의 비상상황 대비 

 

8. Eigenvector Centrality

• node의 중요성이 그 node와 연결된 이웃의 중요성에 의존하는 경우에 사용된다.
• node가 높은 중요성의 이웃들과 연결되어 있으면, 그 node 또한 높은 중요성을 가진다.
• 예시: 웹 페이지의 중요성을 측정하는 Google의 PageRank 알고리즘에 사용되는 원리.

---

많이 쓰이는 8가지 node importance를 알아봤습니다

 

기회가 되는 대로 중요한 node importance에 대해 

 

자세히 정리해보겠습니다.