728x90
반응형
1. 실제 그래프 vs 랜덤 그래프
- 실제 그래프(Real Graph): 다양한 복잡계로부터 얻어진 그래프
- 예) 소셜 네트워크, 전자상거래 구매 내역, 인터넷, 웹, 뇌, 단백질 상호작용, 지식그래프 등
- 랜덤 그래프(Random Graph): 확률적 과정을 통해 생성한 그래프
- 예) 에르되스-레니 랜덤 그래프 (Erdos-Renyi Random Graph)
- 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됨
- n개의 정점을 가지며, 임의의 두 개의 정점 사이에 간선이 존재할 확률은 p
- 정점 간의 연결은 서로 독립적(independent)
- 아래의 그림은 G(3, 0.3)에 의해 생성될 수 있는 그래프와 각각의 확률임
2. 그래프의 경로, 거리, 지름
- 정점 간 경로(Path): 정점 u와 v 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열임
- 정점 u에서 시작해서 v에서 끝나야 함
- 순열에서 연속된 정점은 간선으로 연결되어 있어야 함
(같은 정점이 여러 번 등장하더라도, 위 조건을 만족하면 경로(Path)임!)
- 경로의 길이: 해당 경로 상에 놓이는 간선의 수로 정의
- 예) 경로 1, 4, 6, 8의 길이는 3
- 예) 경로 1, 4, 3, 4, 6, 8의 길이는 5
- 정점 간 거리(Distance): 정점 u와 정점 b 사이의 최단 경로(path)의 길이
- 그래프의 지름(Diameter): 그래프 내에 있는 모든 정점 간의 길이를 계산하여, 가장 멀리 있는 정점 간의 거리! 즉 모든 정점간의 거리 중 최대값이 그래프의 지름을 의미함
3. 연결성과 꼬리 분포
- 정점의 연결성: 정점과 연결된 간선의 수 (해당 정점의 이웃들의 수와 같음) → d(v) 로 표기
- 정점의 나가는 연결성 (Out Degree): 해당 정점에서 나가는 간선의 수
- 정점의 들어오는 연결성 (In Degree): 해당 정점으로 들어오는 간선의 수
| 특징 | 실제 그래프 | 랜덤 그래프 |
| 꼬리 | 두터운 꼬리 (Heavy Tail) | 꼬리가 거의 없고 정규 분포 모양 |
| 연결성이 매우 높은 허브 | 일반적으로 존재함 | 존재하지 않음 |
4. 거대 연결 요소와 군집
- 연결요소(Connected Component) : 아래 두 조건을 모두 만족하는 정점들의 집합
- 연결 요소에 속하는 정점들은 경로로 연결될 수 있음
- 위의 조건을 만족하면서 정점을 추가할 수 없음
- 군집 : 집합에 속하는 정점사이에 많은 간선이 존재하면서, 다른 집합의 정점 간에는 적은 수의 간선이 존재하는 정점들의 집합 (엄밀한 정의는 아님)
- 지역적 군집 계수(Local Clustering Coefficeint): 한 정점에서 군집의 형성 정도
→ 정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미(C_i)
→ 연결성이 0인 정점에서는 지역적 군집 계수가 정의되지 않음 (당연함! 이웃 노드의 연결 정도를 계산하는데, 이웃 노드가 없기 때문)
→ 지역적 군집 계수가 높을수록 높은 확률로 군집을 형성함 - 전역 군집 계수 (Global Clustering Coefficient): 전체 그래프에서 군집의 형성 정도
→ 그래프 G의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균을 의미함
→ 단, 지역적 군집 계수가 정의되지 않는! 즉, 연결성이 0인 정점은 제외
- 지역적 군집 계수(Local Clustering Coefficeint): 한 정점에서 군집의 형성 정도
<실제 그래프와 랜덤 그래프의 군집 및 군집계수 비교>
| 특징 | 실제 그래프 | 랜덤 그래프 |
| 군집 | 많은 군집 존재 | 많지 않음 |
| 동질성 (Homophily) | 높음 | 없음 |
| 전이성 (Transitivity) | 높음 | 없음 |
| 지역적/전역 군집 계수 | 군집 계수 높음 | 높지 않음 |
* 동질성(Homophily): 유사한 정점끼리 간선으로 연결될 가능성이 높음
* 전이성(Transitivity): 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있음
→ 랜덤 그래프에서 간선 연결이 독립적인 것을 고려하면 당연히 동질성과 전이성은 없음!
즉, 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않기 때문에 군집 형성 확률이 매우 낮음
본 내용은 부스트코스의 '그래프와 추천 시스템' 강의를 토대로 작성되었습니다
728x90
반응형
