A First Course In Network Science - Chapter2

Chapter 2 : 좁은 세상

동류성(assortativity) : 연결된 노드들이 비슷한 성질을 갖는 경향

• 연결선 수 동류성(degree assortativity) : 연결선 수에 기반한 동류성
  • 연결선 수 상관(degree correlation)이라고도 함.
• 측정하는 방법? → 상관관계(correlation) 이용
  1. 동류성 계수(assortativity coefficent)
     • 연결된 한 쌍의 노드의 연결선 수 사이의 피어슨 상관계수로 정의
  2. 노드 i의 이웃의 평균 연결선 수를 측정하는 것에 기반
     • 노드 i와 j가 이웃일 경우 $a_{ij} = 1$, 아니면 0
     $$ \langle k_{nn}(k) \rangle $$
     • 위 표현은 연결선 수가 k인 모든 노드의 $k_{\text{nn}}(i)$의 평균.
     • 위 표현이 연결선 수 k의 증가 함수라면 연결선 수가 큰 노드들은 연결선 수가 큰 노드들과 연결되는 경향이 있음
       • 네트워크가 동류적임
     • 감소 함수라면 → 이류적
  3. $$ k_{\text{nn}}(i) = \frac{1}{k_i} \Sigma_j a_{ij}k_j $$

원천 노드(source nde)에서 출발해 목표 노드(target node)에 도달 할 수 있다면

• 경로(path)가 있다고 한다.
• 이때 경로를 이루는 링크의 수를 경로 길이(path length)fkrh gksek.
• 사이클(cycle) : source = target
• 단순 경로(simple path) : 같은 링크를 두 번 다시 지나지 않는 경로
• 평균 경로 길이는 다음과 같이 정의한다.(방향, 가중치 없음)

$$ \langle l \rangle = \frac{\Sigma_{i,j}l_{ij}}{\binom{N}{2}} $$

• 이때 $l_{ij}$는 노드 i 와 j 사이의 최단 경로의 길이
• 다음과 같이 정의하기도 한다.
• $$ \langle l \rangle = \Big( \frac{\Sigma_{i,j}\frac{1}{l_{ij}}}{\binom{N}{2}} \Big)^{-1} $$
• 경로가 없을경우에 $\langle l \rangle$가 무한대 이기 때문.

최단 경로 찾기

• 너비 우선 탐색(breadth-first search)
  • 원천 노드에서 시작해 네트워크의 다른 모든 노드 사이의 최단 경로를 찾는 알고리즘
  • 원천에서 멀리 떨어진 곳으로 가기 전에 일정 거리 안에 있는 네트워크의 전체 ‘너비’를 방문하는 것
  • 그림 출처 : https://velog.io/@ekzm8523/깊이우선탐색DFS-너비우선탐색BFS
  • 
  • 알고리듬을 구현하려면…
    • 각 노드는 원천 노드에서의 거리를 저장할 속성을 갖고 있어야 함.
    • 미개척지(frontier)라고 부르는 노드의 대기열을 유지해야 함.
      • 대기열 → 선입 선출
    1. 노드 j는 미개척지
    2. 원천 노드에서 노드 j의 거리를 아래와 같이 설정
    3. $$ l_{s,j} = s_{s,i}+1 $$
    4. 노드 i에서 j로 방향이 있는 링크 하나를 최단 경로 트리에 추가

뭉침 계수(Clustering coefficient)

• 노드의 이웃 노드들의 쌍 중에서 서로 연결된 쌍의 비율
• 현존하는 삼각구조의 수와 최대로 가능한 삼각구조의 수의 비율
• $$ C(i)=\frac{\tau(i)}{\tau_{\text{max}}(i)}=\frac{\tau(i)}{\binom{k_i}{2}} $$
• $\tau(i)$ : 노드 i를 포함하는 삼각구조의 수
• 전체 네트워크의 뭉침 계수 → 개별 노드 뭉침 계수의 평균
  • k<2인 노드들 제외
• $$ C=\frac{\Sigma_{i:k_i>1}C(i)}{N_{k>1}} $$
• 이 수식은 방향이 없는 네트워크에서만 적용
• 소셜 네트워크 → 친구의 친구 삼각구조 덕택에 높은 뭉침 계수를 보임.