연결성(Degree)이란?
정점과 연결된 간선의 개수를 의미합니다.
예를 들어 아래와 같은 그래프에서 A의 degree는 1, B의 degree는 3이라고 할 수 있습니다.
그러면 그래프 내에서 이러한 연결성(Degree)의 분포도는 어떨까요?
실제 그래프와 랜덤 그래프는 둘다 작은 세상 효과를 가지고 있습니다! (자세한 내용은 여기!)
그러나 연결성 분포는 전혀 다르게 나타납니다.
실제 그래프의 연결성 분포는 다음과 같이 두터운 꼬리(Heavy Tail)를 가지고 있습니다.
아래 예시와 같이 일반 사용자의 팔로워 수와 셀럽의 팔로워 수는 극단적으로 차이가 나므로 이런 식의 분포도를 가지게 됩니다.
그러나 랜덤 그래프는 일정 확률에 의해서 랜덤하게 생성이 되는 그래프이므로 연결성 분포가 다음과 같이 정규분포의 형태를 띄게 됩니다.
이런 랜덤한 그래프의 경우 연결성이 매우 높은 허브(Hub) 정점이 생길 가능성은 거의 0입니다!
즉, 실제 그래프와 랜덤 그래프를 비교해보면 다음과 같습니다.
연결 요소(Connected Component)란?
연결 요소에 속하는 정점끼리는 경로로 연결 될 수 있어야 하며, 정점을 추가할 수 없는 정점들의 집합을 의미합니다.
예시로 살펴보겠습니다.
아래 그래프에서는 총 3개의 연결 요소가 존재합니다.
{1, 2, 3, 4, 5}, {6, 7, 8}, {9}
{1, 2, 3, 4, 5} 내에 있는 정점끼리는 서로 경로를 통해 연결 될 수 있으니 첫 번째 조건을 만족합니다.
또한 정점을 추가할 수 없다 라는 의미는 더 이상 해당 연결 요소에 들어올 수 있는 정점이 없다. 라는 의미와 동일합니다.
즉, {1, 2, 3, 4}라는 집합에는 {5}라는 정점이 경로를 통해 연결 될 수 있으니 추가적으로 포함 가능합니다.
따라서 {1, 2, 3, 4}는 연결 요소라고 할 수 없습니다.
거대 연결 요소(Giant Connected Component)란?
대다수의 정점을 포함하는 연결 요소
군집(Community) 구조란?
1) 집합에 속하는 정점 사이에 많은 간선이 존재
2) 집합에 속하는 정점이 아닌 정점 사이에는 적은 수의 간선이 존재
일종의 그래프 내에서의 클러스터링이라고 보면 이해가 조금 더 쉬울 것 같습니다.
본 글은 부스트코스 "그래프와 추천 시스템" 강의를 듣고 공부하며 정리 및 재구성한 글입니다.
그래프와 추천 시스템
부스트코스 무료 강의
www.boostcourse.org
'DL & ML > Graph' 카테고리의 다른 글
| [그래프와 추천 시스템] 페이지 랭크 계산하기 (0) | 2022.02.02 |
|---|---|
| [그래프와 추천 시스템] 페이지 랭크 (0) | 2022.01.28 |
| [그래프와 추천 시스템] 그래프 패턴 - 실제 그래프와 랜덤 그래프 (0) | 2022.01.28 |
| [그래프와 추천 시스템] 그래프의 유형 및 분류 (0) | 2022.01.28 |
| [그래프와 추천 시스템] 그래프란 무엇이고, 왜 중요할까? (0) | 2022.01.28 |
