Small World

2021.12.06 - [Graph Mining] - Random Graph

Random Graph

 

앞서 Random하게 생성한 G_np는 실제 세계와 틀리다는 점을 알아봤다. 따라서 실제 세계와 비슷한 random graph를 생성하기 위해 다른 방법을 찾아본다

## Edge Locality

G_np를 사용했을 때 clustering coefficient가 낮은 이유는 local structure를 고려하지 못함이라고 설명을 하였다. 따라서 local structure를 판단하기 위한 edge locality를 알아보자

Triadic Closure 는 친구의 친구가 내 친구인 경우를 말한다. 이를 그래프로 보면 다음과 같다.

traidic closure

이 경우는 clustering coefficient 가 매우 높은 경우이다. 하지만 diameter가 매우 크다.

따라서 실제 세계와 비슷한 랜덤 그래프를 생성하기 위해선 cluster coef를 높이고 diameter는 낮춰야한다

 

## Small World

따라서 링 형태의 High Cluster coef - High diameter에서 시작하여 Low Cluster coef - Low diameter 로 가는 중간이 가장 이상적인 random graph라고 생각하여 시작되는 연구이다.

여기서 Rewire라는 작업을 통해 diamter를 작게 만든다. Rewire는 연결된 edge 중 하날 끊어서 다른 노드로 연결을 하는 것이다. 이렇게 되면 각 노드의 degree가 변화된다.(shortcut) rewire는 random한 값 p의 확률을 통해서 edge를 rewire할지 결정한다. 이 때, p=0.01이 가장 좋다는 것을 증명하였다.

p에 따른 clustering coefficient 변화

따라서 이러한 작업을 거친 graph들을 small world라고 불리우고, 이러한 작업을 통해 high clustering coefficient low diameter가 이뤄지게 된다.