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

Analysis

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

da-da-da 2022. 9. 27. 12:51

728x90

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$