A First Course In Network Science - Chapter3

Chapter 3 : 허브

노드 또는 링크의 중요도는 중심도(centrality)를 통해 추정할 수 있다.

허브 → 연결선 수가 많은 노드

근접도(closeness)

• 중심도를 측정하는 또 다른 방법 : 근접 중심도(closeness centrality)
  • 한 노드가 다른 노드와 얼마나 ‘가까운지’ 결정
  • 한 노드에서 다른 모든 노드까지의 거리 합의 역수
  • 노드 i의 근접 중심도는 다음과 같이 정의된다.
  • $$ g_i = \frac{1}{\sum_{i\ne j} l_{ij}} $$
  • 네트워크의 크기에 의한 효과를 없애려면…
    • 이때 분모가 평균 거리이므로, 근접도는 평균 거리의 역수와 같다.
  • $$ \tilde{g_i} = g_i = \frac{1}{\sum_{i\ne j} \ l_{ij}/(N-1)} $$

사이 중심도(betweenness centrality)

• 확산 과정을 기반으로 하여 제안된 중심도
  • 확산의 종류에 따라 사이 중심도는 다르게 정의된다.
• 가장 널리 사용되는 정의는…
  • 최단경로를 따라 한 노드에서 다른 노드로 신호가 전달되는 간단한 과정을 고려
  • 수송 네트워크에서 노드가 처리하는 수송량을 추정하기 위해 많이 사용
  • 해당 노드를 통과하는 최단 경로의 수가 그 노드가 사용되는 빈도를 잘 추정할 것으로 가정
  • 최단 경로가 노드를 통과하는 횟수를 세어서 중심도 추정
    • 분모 : h → j 인 최단 경로 개수
    • 분자 : h → j 인 최단 경로에서 노드 i를 경유하는 경로 개수
  • $$ b_i = \sum_{h\ne j \ne i} \ \frac{\sigma_{hj}(i)}{\sigma_{hj}} $$
  • 네트워크들 간의 노드 또는 링크의 사이 중심도를 비교하려면…
    • 정규화(normalize) 해야 함을 잊지 말자.
    • 위의 사이 중심도에서 구한 경로의 개수가 가질 수 있는 최댓값으로 나눠주자.

중심도 분포

• 많은 자연계의 네트워크, 사람이 만든 네트워크 → 고도로 연결된 허브를 포함하는 두꺼운 꼬리를 가진 연결선 수 분포를 갖고 있음.

Degree distribution of Twitter network and complement cumulative Degree Distribution.

 

• 연결선 수 분포의 너비를 측정할 수 있을까?
  • 불균일도 매개변수(heterogeneity parameter)
  • k는 Chapter2에서 연결선 수라고 정의 했었다.
  • $$ \kappa = \frac{\langle k^2 \rangle}{\langle k \rangle ^2} $$
  • 좁은 분포의 경우 → 1에 가까워 진다.
  • 두꺼운 꼬리를 가진 분포 → 허브에 의해 분자가 매우 커진다.
• 연결선 수 분포가 넓은 네트워크 → 종종 ‘극단적인 좁은 세상(ultra-small world)’의 특징을 갖게 됨

코어 분해

• 네트워크를 분석하거나 시각화 할 때 → 조밀한 부분(코어)에 집중하는 것이 유용하다.
• k 코어 분해(k-core decomposition) 알고리듬
  • k=0부터 시작
  1. 연결선 수가 k인 모든 노드를 연결선 수가 k인 노드가 남아있지 않을 때까지 제거
  2. 제거된 노드들 → k 껍질(k-shell)
     • 남은 노드들 : K+1 코어
  3. 코어에 노드가 더이상 없으면 종료한다. 노드가 남아있다면 k를 증가시켜 1번부터 다시 진행