소셜 네트워크같이 실제로 존재하는 네트워크들에서 노드들 사이의 연결이 랜덤하게 생성된 네트워크에 비해서 상대적으로 연결의 밀도가 높다고 알려져 있습니다. 이렇게 노드들 사이 연결의 밀도가 높다는 것은, 노드들이 서로 잘 뭉친다는 것을 의미하는데요, 그래프 이론에서 각각의 노드들이 서로 뭉치는 경향을 알 수 있는 한 척도로 집단화 계수(Clustering coefficient)가 사용됩니다.

간단하게 말해서 어떤 노드에서의 집단화 계수(clustering coefficient)는 특정 노드와 이웃한 노드들이 서로 연결되어 있을 확률입니다. 일종의 확률이기 때문에 0부터 1사이의 값을 가질 수 있습니다.

집단화 계수를 측정하는 방법은 두 가지가 있습니다. 바로 전체 집단화 계수(global clustering coefficient)를 측정하는 방법과 부분 집단화 계수(local clustering coefficient)를 측정하는 방법입니다. 전체 집단화 계수는 네트워크의 전체적인 뭉치는 성질을 보여주는 반면 부분 집단화 계수는 각각의 노드들에 좀 더 초점이 맞춰진 것입니다.

먼저, 전체 집단화 계수(Global clustering coefficient)는 노드 3개쌍(triplet)를 기본 단위로 합니다. 3개의 노드 사이에는 방향성이 없는 엣지가 2개(open triplet) 혹은 3개(closed triplet)가 있을 수 있습니다. 전체 집단화 계수는 전체 네트워크에 있는 닫힌 세 노드쌍(closed triplet)의 개수를 네트워크에서 만들 수 있는 모든 세 노드쌍(triplet)의 개수로 나눈 것입니다.
CC이 그림에서 A 네트워크와 B 네트워크 모두 3개의 노드로 이루어진 세 노드쌍(triplet)을 하나씩 가지고 있습니다. 여기서, A 네트워크는 엣지가 2개이기 때문에 열린 노드쌍(open triplet)이고, B 네트워크는 엣지가 3개이기 때문에 닫힌 노드쌍(closed triplet)이라고 할 수 있습니다.집단화 계수는 전체 네트워크에서 찾을 수 있는 모든 세 노드쌍(triplet; A형태 + B형태) 중에 닫힌 노드쌍(closed triplet; B형태)가 얼마나 있느냐로 결정되는 것입니다.

기본적인 관점에서 화살표가 가리키는 노드를 중심으로 봤을 때 이웃한 두 노드가 연결되어 있을 확률이라고 볼 수 있는 것이지요.

위의 전체 집단화 계수가 네트워크 전체에 대한 값이라면, 부분 집단화 계수는 노드별로 가지는 값입니다. 어떤 노드의 부분 집단화 계수는 ‘그 노드와 이웃한 노드 사이에서 생길 수 있는 가능한 모든 엣지 수 중 실제로 존재하는 엣지의 수’가 됩니다.

CCLocal

그림을 보면, A와 B 모두 화살표가 가리키는 노드와 이웃한 노드가 3개씩 있습니다. 이웃한 세 노드 사이에 생길 수 있는 모든 엣지는 3개인데, A 네트워크는 3개의 엣지가 있으므로 부분 집단화 계수는 1(3/3)이고, B 네트워크는 1개의 엣지가 있기 때문에 1/3이 되는 것입니다.

네트워크 전체의 집단화 계수를 부분 집단화 계수로 구할 때는 모든 노드의 부분 집단화 계수의 평균을 내서 사용합니다.

지금까지 네트워크의 집단화 계수에 대해 알아보았습니다. 실제 네트워크를 분석할 때는 컴퓨터가 해주기 때문에 실제로 식을 쓰거나 직접 엣지 수를 세어가며 하는 것은 아니지만, 그 의미를 알고 있어야 수월하게 결과를 해석할 수 있을 것 같습니다. ==★

Amygdala_black

 

광고