소셜 네트워크(social network)는 그래프(graph)로 표현되는 이질적이고 다중 관계적인 정보 집합입니다. 이 그래프는 일반적으로 매우 방대한 규모를 가지며, 노드(node)는 객체에 해당하고 엣지(edge)는 객체 사이의 관계나 연결을 나타냅니다. 노드와 연결은 모두 속성(attribute)을 가질 수 있으며, 객체에는 클래스 레이블이 부여될 수도 있습니다. 또한 링크는 단방향일 수 있고, 반드시 이진(binary) 형태일 필요는 없습니다.
소셜 네트워크의 주요 특징
소셜 네트워크는 다음과 같은 세 가지 특징적인 성질을 보입니다.
밀도화 멱법칙(Densification Power Law) – 예전에는 네트워크가 진화할수록 노드 수가 늘어나는 만큼 엣지 수도 선형적으로 증가하여 평균 차수가 일정하게 유지된다고 믿었으며, 이를 '상수 평균 차수 가설'이라고 불렀습니다. 그러나 광범위한 실험 결과는 정반대의 사실을 보여주었습니다. 시간이 지날수록 네트워크는 오히려 더 조밀해지며(densify), 평균 차수가 증가하고 엣지 수는 노드 수보다 초선형(super-linear)으로 늘어납니다.
이러한 밀도화 현상은 다음과 같은 밀도화 멱법칙(또는 성장 멱법칙)으로 설명됩니다.
$$e(t)\propto n(t)^{a}$$
여기서 e(t)와 n(t)는 각각 시점 t에서 그래프의 엣지 수와 노드 수를 의미하며, 지수 a는 일반적으로 1과 2 사이의 값을 가집니다. a = 1이면 시간이 흘러도 평균 차수가 고정된 경우에 해당하고, a = 2이면 모든 노드가 전체 노드 중 일정 비율만큼 서로 연결된 완전 밀집 그래프에 해당합니다.
축소되는 지름(Shrinking Diameter) – 실험 결과에 따르면 네트워크가 커질수록 유효 지름(effective diameter)은 오히려 감소하는 경향을 보입니다. 이는 네트워크 규모가 커짐에 따라 지름이 서서히 증가한다는 기존의 통념과 상반되는 발견입니다.
예를 들어 논문 인용 네트워크를 살펴봅시다. 이 네트워크에서 노드는 논문이며, 한 논문이 다른 논문을 인용하는 관계는 유향 엣지로 표현됩니다. 어떤 노드 v의 아웃링크(v가 인용한 논문들)는 해당 논문이 그래프에 추가되는 순간 '동결(frozen)'됩니다. 그럼에도 노드 쌍 간의 거리가 줄어드는 이유는, 이후에 발표된 논문들이 여러 분야의 기존 논문들을 동시에 인용함으로써 '다리(bridge)' 역할을 하기 때문입니다.
무거운 꼬리를 가진 차수 분포(Heavy-tailed Degree Distributions) – 노드의 아웃디그리(out-degree) 분포는 멱법칙(power law), 즉 1/na 형태를 따르는 무거운 꼬리(heavy-tailed) 분포를 보이는 경향이 있습니다. 여기서 n은 아웃디그리가 감소하는 순서로 정렬했을 때의 노드 순위이며, 일반적으로 0 < a < 2입니다. a 값이 작을수록 꼬리는 더 두꺼워집니다.
이러한 현상은 우선적 연결(preferential attachment) 모델로 설명할 수 있습니다. 이 모델에서 새로운 노드는 고정된 수의 아웃링크를 통해 기존 네트워크에 연결되며, '부자는 더 부유해진다(rich-get-richer)'는 규칙을 따릅니다. 인디그리(in-degree) 역시 무거운 꼬리 분포를 따르지만, 그 편중 정도는 아웃디그리 분포보다 더 심하게 나타납니다.