Social Network 을 Network 이나 Grpah 로 표현하기

복잡한 구조의 소셜네트웍을 그래프(Graph)나 네트웍(Network)의 형태로 표현하는 것은 소셜네트웍의구조를 이해하는데 유용한 방법입니다.

특별히 계층적인 조직이나 여러단계를 거쳐서 인맥관계를 형성하는 구조가 존재하는 경우, 이를 계층형 구조라고 하고, 계층형 구조(Hierarachical Structure)는 다시 여러가지 가능한 덴드로그램(dendrogram)으로 재표현 할 수 있습니다.

이전 포스트(http://blog.paran.com/sunghoon/29622411)에서계보적/계층적 클러스터링을 설명 드릴때 예시를 들었었습니다만, 덴드로그램은계층형 바이너리트리의 형태를 띄고 있습니다.

예컨데 다음과 같은 노드와 링크를 가지고 있는 작은 네트웍을 가능한 하나의 계층형 구조의 덴드로그램으로 표현하면 다음과 같이 그릴 수 있을 겁니다.

[1] 간단한 네트웍을 덴드로그램으로 그리기

인터넷의 링크구조나 소셜 네트웍과 같은복잡계에서는 이러한 비 규칙적 네트웍을 이해하는데, 계층적 랜덤그래프 Hierarchical Random Graph Model 을 많이 사용합니다.

랜덤 그래프는 G(n,p) 와 같이 표현하며, n개이 노드를 가지고 각각의 링크에 n번째 노드로 갈 확률 p 를 가진 랜덤그래프라고 정의 합니다.

꽤 규모가 있는 랜덤 그래프라면 이를 재표현하기 위한 덴드로그램은 무수히 많을 수 있습니다.

예컨데간단한 3개의 노드로 이루어진 네트웍을 덴드로그램으로 표현하려고 하더라도, 가능한덴드로그램은 3가지나 되게 됩니다.

[2] a b c 세개의 노드로 이루어진 네트웍의 가능한 덴드로그램

사실 요즘 제 관심사는 지속적으로 규모가 커지는 네트웍에서 끊어진 연결고리를 찾는 방법입니다.

그 방법은 직관적인 방법부터 복잡한 최적화방법까지 다양하게 존재하고 있습니다만,제가 공부를 안한지 너무 오래되었고, 또 머리도 나빠서 요즘은 끙끙 앓고 있답니다. TT

* [1][2] Aaron Clauset, Cristopher Moore, Mark Newman (2006)