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

이전 포스트에 계속되는 내용입니다

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

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

---

4. 거대 연결 요소

---

필수 개념 : 연결 요소 (Connected Component)

• 다음 조건들을 만족하는 정점들의 집합
  1. 연결 요소에 속하는 정점들은 경로로 연결될 수 있음
  2. 1의 조건을 만족하면서 정점을 추가할 수 없음
• 예시

	좌측 그래프에는 3개의 연결 요소가 존재 {1, 2, 3, 4, 5}, {6, 7, 8}, {9}
	연결 요소가 아닌 경우 {1, 2, 3, 4} : 조건 2를 위배, 5를 추가해도 여전히 조건 1을 만족함 {6, 7, 8, 9} : 조건 1을 위배

---

거대 연결 요소 (Giant Connected Component)

• 실제 그래프에는 거대 연결 요소가 존재
• 거대 연결 요소는 대다수의 정점을 포함함
• 랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재 (단 정점들의 평균 연결성이 1보다 충분히 커야 함)

실제 그래프	MSN 메신저 그래프에는 99.9%의 정점이 하나의 거대 연결 요소에 포함됨
랜덤 그래프

---

5. 군집 구조

---

1. 필수 개념

군집(Community)

다음의 조건들을 만족하는 정점들의 집합, 엄밀한 수학적 정의는 아님

1. 집합에 속하는 정점 사이에는 많은 간선이 존재
2. 집하에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재

아래 그래프에는 약 11개의 군집이 존재하는 것으로 보임

 

지역적 군집 계수 (Local Clustering Coefficient)

• 한 정점에서 군집의 형성 정도를 측정
• 정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미, $C_i$로 표현
• 지역적 군집계수가 매우 높다
  • 정점 i의 이웃들도 높은 확률로 서로 간선으로 연결되어 있음
  • 즉, 정점 i와 그 이웃들은 높은 확률로 군집을 형성

	- 정점 1의 이웃 : 2,3,4,5 총 4개 - 정점 1 의 이웃은 총 6개의 이웃쌍 존재 (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5) - 이 중 간선으로 직접 연결되어 있는 것은 3개 쌍 : (2, 3), (2, 4), (3, 5) => 따라서 $C_1 = \frac{3}{6} = 0.5$
	$C_1 = \frac{4}{6} = 0.66$
	$C_1 = \frac{0}{6} = 0$ 연결성이 0인 정점에서는 지역적 군집 계수가 정의되지 않음

 

전역 군집 계수 (Global Clustering Coefficient)

• 전체 그래프에서 군집의 형성 정도를 측정
• 그래프 G의 전역군집 계수 = 각 정점에서의 지역적 군집 계수의 평균
  (단, 연결성이 0이어서 지역적 군집 계수가 정의되지 않은 정점은 제외)

---

2. 높은 군집 계수

실제 그래프에서는 군집 계수가 높음. (= 많은 군집이 존재) 그 이유는 아래와 같음.

반면, 랜덤 그래프에서는 지역적 또는 전역 군집 계수가 높지 않음. 
(랜덤 그래프 G(n,p)에서 군집 계수는 p인데 간선 연결이 독립적임. 즉, 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않기 때문)

동질성 (Homophily)

서로 유사한 정점끼리 간선으로 연결될 가능성이 높음. (비슷한 집단의 사람들이 친구가 되는 경우)

전이성 (Transitivity)

공통 이웃이 있는 경우, 공통 이웃을 매개로 하여 서로 이웃이 됨

 

---

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

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

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