[그래프] 2-1. 그래프 패턴

1. 실제 그래프 VS 랜덤 그래프

• 실제 그래프(Real Graph)란 다양한 복잡계로부터 얻어진 그래프
  • 소셜 네트워크, 전자 상거래 구매 내역, 인터넷, 웹 그래프..
• 랜덤 그래프 (Random Graph)란 확률적 과정을 통해 생성한 그래프
  • ex: 에르되스-레니 랜덤 그래프 (Erdos-Renyi Random Graph)
    • 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됨
    • G(n, p)
    • n개의 정점
    • 임의의 두 정점 사이에 간선이 존재할 확률은 p
    • 정점 간의 연결은 서로 독립적(Independent)
  • Q : G(3, 0.3)에 의해 생성될 수 있는 그래프와 각각의 확률은?
    정점 3개, 간선이 존재할 확률 0.3 ( = 간선이 존재하기 않을 확률 0.7)

$0.3^3$	$0.3^2 \times 0.7$	$0.3^2 \times 0.7$	$0.3^2 \times 0.7$
$0.3 \times 0.7^2$	$0.3 \times 0.7^2$	$0.3 \times 0.7^2$	$0.7^3$

 

---

2. 작은 세상 효과

---

필수 개념 : 경로, 거리 및 지름

경로 (Path)

• 다음 조건을 만족하는 정점들의 순열(Sequence)
  1. u에서 시작해서 v에서 끝나야 함
  2. 순열에서 연속된 정점은 간선으로 연결되어 있어야 함
     (이 조건만 만족하면 순열에 같은 정점을 여러 번 지날 수 있음 ≒경로임에는 변함이 없음)
• 경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의됨

거리 (Distance)

정점 u와 v 사이의 거리는 u와 v 사이의 최단 경로의 길이

지름 (Diameter)

그래프의 지름은 정점 간 거리의 최댓값
(그래프에 존재하는 모든 정점의 쌍의 거리를 계산해서 그중 가장 큰 값)

	정점 1과 8사이의 경로 예시
	1, 4, 6, 8 1, 3, 4, 6, 8 1, 4, 3, 4, 6, 8
	정점 1과 8사이의 경로가 아닌 순열의 예시
	1, 6, 8 (조건 2 위배) 1, 3, 4, 5, 6, 8 (조건 2 위배)
	경로의 길이
	경로 1, 4, 6, 8  : 3 경로 1, 3, 4, 6, 8 : 4 경로 1, 4, 3, 4, 6, 8 : 5 (정점 개수 - 1)
	정점 1과 8 사이의 거리
	1과 8사이의 최단 경로 = {1,4,6,8} 해당 경로의 길이 = 3 즉, 정점 1과 8사이의 거리 = 3
	해당 그래프의 지름
	모든 정점의 쌍 중 가장 거리가 큰 경로는 {2,3,4,6,8} 즉, 본 그래프의 지름은 4

 

---

작은 세상 효과

임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?

여섯 단계 분리 실험 (Six Degrees of Separation)

• 1960년대 사회학자 스탠리 밀그램(Stanley Milgram)에 의해 수행된 실험
• 오마하와 위치타의 사람들이 지인을 통해서만 보스턴에 있는 한 사람에게 편지를 전달하게 한 실험
• 결과 : 실험 대상 중 25%의 편지만 도착했지만 평균적으로 6단계 만을 거침 

MSN 메신저 그래프

• 정점 간의 평균 거리는 7 (거대 연결 구조만 고려한 경우)

작은 세상 효과 (Small-world Effect)

• 위와 같은 현상을 일컬음
• 즉, 사람들은 소수의 공통된 지인을 통해 연결됨
• 높은 확률로 랜덤 그래프에도 존재함
• 모들 그래프에서 작은 세상 효과가 존재하는 것은 아님 : 체인(Chain), 사이클(Cycle),  격자(Grid) 그래프에서는 작은 세상 효과가 존재하지 않음

---

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

---

필수 개념 : 연결성

• 정점의 연결성(Degree)은 정점과 연결된 간선의 수
• 연결성 = 해당 정점의 이웃의 수
• $d(v), d_v$ 또는 $|N(v)|$

나가는 연결성 (Out Degree)

• 해당 정점에서 나가는 간선의 수를 의미
• $d_{out}(v)$. $|N_{out}(v)|$

들어오는 연결성 (In Degree)

• 해당 정점으로 들어오는 간선의 수
• $d_{in}(v)$, $|N_{in}(v)|$

$d_{in}(1) = 1,  d_{out}(1) = 1$ $d_{in}(2) = 3, d_{out}(2) = 1$ $d_{in}(3) = 0, d_{out} = 2$ $d_{in}(4) = 1, d_{out}(4) = 2$ $d_{in}(5) = 2, d_{out}(5) = 2$ $d_{in}(6) = 1, d_{out}(6) = 0$

 

---

연결성의 두터운 꼬리 분포

실제 그래프

• 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 가짐
• 즉, 연결성이 매운 높은 허브(Hub) 정점이 존재

랜덤 그래프

• 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사
• 즉, 허브 정점이 존재할 가능성이 0에 가까움

 

 

---

다음 포스트에 이어서 작성하겠습니다.

2022.09.28 - [Analysis] - [그래프] 2-2. 그래프 패턴

[그래프] 2-2. 그래프 패턴

---

 

edwith의 그래프와 추천 시스템 강의를 듣고 정리 한 내용입니다. 

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith