차수와 차수 분포

핵심 개념

무방향 그래프에서 노드의 차수(degree)는 그 노드에 붙은 엣지 수입니다. 엣지 하나는 양 끝 두 노드의 차수를 하나씩 올리므로, 모든 노드의 차수를 더하면 언제나 엣지 수의 두 배가 됩니다. 악수 한 번에 손이 두 개 필요하다는 뜻에서 이를 악수 정리(handshake lemma)라고 부릅니다. 따라서 차수 합은 항상 짝수이고 평균 차수는 2E÷N입니다.

차수 분포(degree distribution)는 ‘차수가 k인 노드가 몇 개, 또는 전체의 몇 %인가’를 모은 것입니다. 동아리 네트워크는 차수 2가 2명, 차수 3이 6명으로 고르게 퍼져 있습니다. 반대로 한 노드가 거의 모두와 이어진 별 모양 그래프는 차수 하나가 유난히 크고 나머지는 1입니다. 이렇게 연결이 몰린 노드를 허브(hub)라고 합니다.

바라바시와 알버트(Barabási & Albert, 1999)는 웹 같은 큰 네트워크의 차수 분포가 거듭제곱 법칙(power law)을 따른다고 보고하고, 그 원인으로 두 가지를 제시했습니다. 새 노드가 계속 더해지며 네트워크가 자라는 성장(growth)과, 새 노드가 이미 연결이 많은 노드에 더 잘 붙는 선호적 연결(preferential attachment)입니다. 이런 네트워크를 척도 없는(scale-free) 네트워크라 부르며, 소수의 허브와 차수가 작은 다수의 노드가 함께 나타납니다.

다만 실제 데이터가 거듭제곱 법칙에 얼마나 잘 맞는지는 데이터마다 따로 검증해야 합니다. 또 차수가 크다는 것은 연결이 많다는 뜻일 뿐, 그 노드가 가장 중요하다는 결론으로 바로 이어지지는 않습니다. 중요도의 여러 기준은 16회차부터 다룹니다.

작은 예제로 따라가기

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.