[그래프와 추천 시스템] 그래프 패턴 - 실제 그래프와 랜덤 그래프

실제 그래프(Real Graph)란?

다양항 복잡계로부터 얻어진 그래프를 의미

ex) 소셜 네트워크, 전자 상거래 거래 내역 등

 

 

랜덤 그래프(Random Graph)란?

확률적 과정을 통해 생성한 그래프를 의미

ex) 에르되스 - 레니 랜덤 그래프 (Erdos - Renyi Random Graph)

  - 임의의 두 정점 사이 간선의 존재 여부를 동일한 확률 분포로 형성

  - $G(n, p)$ : n개의 정점을 가지고, 임의의 두 점 사이에 p의 확률로 간선 생성 

 

 

그래프의 지름(Diameter)란?

그래프 내에 있는 정점 간 거리의 최댓값

 

 

작은 세상 효과(Small World Effect)란?

여섯 단계 분리 실험 (Six Degrees of Separation)이란 것이 있습니다.

아마 실험 내용은 다들 한 번쯤 들어보셨을겁니다! 

1960년대에 오마하와 위치타에서 500명의 사람을 뽑아 보스턴에 있는 사람에게 "지인을 통해서만" 편지를 전달하도록 시킨 실험입니다.

실험 결과 평균적으로 6단계를 거쳐서 편지가 전달 되었다는 것입니다. 

비슷하게 MSN 메신저 그래프에서도 실험을 진행해보았더니 평균 7번 내로 메신저가 전달이 되었다고합니다!

 

이처럼 아무리 먼 관계도 건너건너 연결되어있다는 것을 작은 세상 효과라고 합니다. 

이러한 작은 세상 효과는 실제 그래프가 아닌 "랜덤 그래프"에서도 존재합니다.

 

작은 세상 효과가 나타나는 이유는 무엇일까요?

모든 사람들이 각자 100명의 지인이 있다고 가정하면 5단계만 거쳐도 100억(100^5)명의 사람들과 연결될 수 있기 때문이죠!

(물론 실제로는 중복되는 지인이 있으니 그보다 훨씬 적을테지만요)

 

 

이처럼 그래프로 데이터를 표현하면 생각보다 더 많은 것을 표현할 수 있고, 더 많은 의미를 담고 찾아낼 수 있습니다!

 

 

 

 

 

본 글은 부스트코스 "그래프와 추천 시스템" 강의를 듣고 공부하며 정리 및 재구성한 글입니다.

 

그래프와 추천 시스템