Day 21. 그래프 이론 기초 & 패턴

0. Intro

• 정점(Vertex): 노드(Node), 간선: 엣지(Edge) 또는 링크(Link)

 

 

1. 동종(Unpartite) 그래프 vs 이종(Bipartite) 그래프

• 동종 그래프는 단일 종류의 정점을 가짐
• 이종 그래프는 두 종류의 정점을 가짐
  • 예) 영화 출연 그래프(배우, 영화)

 

 

2. 일반 행렬 vs 희소 행렬

• 일반 행렬 <=> 인접 행렬: 전체 원소를 저장하므로 원소 대부분이 0이라면 비효율적
• 희소 행렬: 0이 아닌 원소만 저장함. 간선의 수에 비례하는 저장 공간을 사용
• 예) 정점의 수가 10만, 간선의 수가 100만이라면, 일반 행렬로 저장 시 정점의 수 제곱(100억), 희소 행렬로 저장 시 간선의 수(100만)큼 저장함

 

 

3. 작은 세상 효과

• 여섯 단계 분리(Six Degree of Separation) 실험
  • Q. 오마화와 위치타 지역에서 보스턴에 있는 사람에게 편지를 전달하려면 몇 단계를 거쳐야 할까?
  • A. 25%의 편지만 도착했지만 평균적으로 6단계를 거침
  • 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재함
    • 하지만, 모든 그래프에서 존재하는 것은 아님

 

 

4. 연결성의 두터운 꼬리 분포

• 실제 그래프의 연결성 분포는 두터운 꼬리(heavy tail)임
• 즉, 연결성이 매우 높은 허브(hub)가 존재함을 의미

• 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사함
• 이 경우, 연결성이 매우 높은 허브 정점이 존재할 가능성은 0에 가까움
• 정규분포와 유사한 예시로는 키의 분포가 있음. 키가 10미터를 넘는 극단적인 예외는 존재하지 않음