부스트캠프 AI Tech 1기 [T1209 최보미]/U stage
Day21 학습정리 - 그래프 이론 기초 & 그래프 패턴
B1001101
2021. 2. 22. 23:47
강의복습
1. 그래프란 무엇이고 왜 중요할까?
더보기
1) 그래프란 무엇이고 왜 중요할까?
- 그래프(Graph): 정점(Vertex) 집합과 간선(Edge) 집합으로 이루어진 수학적 구조
- 하나의 간선은 두 개의 정점을 연결
- 그래프는 네트워크(Network)로도 불림
- 정점: Node, 간선: Link
- 복잡계를 표현하고 분석하기 위한 언어
2) 그래프 관련 인공지능 문제
- 정점 분류, 연결 예측, 추천, 군집 분석, 랭킹, 정보 검색, 정보 전파, 바이럴 마케팅 등
3) 그래프 관련 필수 기초 개념
- 방향성이 없는 그래프(Undirected Graph) / 방향성이 있는 그래프(Directed Graph)
- 가중치가 없는 그래프(Unweighted Graph) / 가중치가 있는 그래프(Weighted Graph)
- 동종 그래프(Unpartite Graph) / 이종 그래프(Bipartite Graph - 다른 종류의 정점 사이에만 간선이 연결됨)
- 정점들의 집합: 𝑽, 간선들의 집합: 𝑬, 그래프: 𝑮 = (𝑽,𝑬)
- 정점의 이웃(Neighbor): 그 정점과 연결된 다른 정점
정점 𝑣의 이웃들의 집합: 보통 𝑵(𝒗) 혹은 𝑵𝒗로 적음 - 나가는 이웃(Out-Neighbor)의 집합: 𝑵𝒐𝒖𝒕(𝒗)
들어오는 이웃(In-Neighbor)의 집합: 𝑵𝒊𝒏(𝒗)
4) 그래프의 표현 및 저장
- 파이썬 라이브러리
- NetworkX: networkx.org/documentation/stable/index.html
- Snap.py: snap.stanford.edu/snappy/
- 간선 리스트
- 방향성 없는 경우: 그래프를 간선들의 리스트로 저장
- 방향성 있는 경우: (시작점, 출발점) 순서로 저장
- 인접 리스트
- 방향성 없는 경우: 각 정점의 이웃들을 리스트로 저장
- 방향성 있는 경우: 각 정점의 나가는 이웃들과 들어오는 이웃들을 각각 리스트로 저장
- 인접 행렬
- 방향성 없는 경우: 정점 i와 j 사이에 간선이 있으면 i행 j열과 j행 i열 원소 1, 없으면 0
- 방향성 있는 경우: 정점 i에서 j로의 간선이 있으면 i행 j열 원소 1, 없으면 0
2. 실제 그래프는 어떻게 생겼을까?
더보기
1) 실제 그래프 vs 랜덤 그래프
- 실제 그래프: 복잡계로부터 얻어짐
- 랜덤 그래프: 확률적 과정을 통해 생성
- 에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph): G(n,p)
- n개의 정점 가짐
- 임의의 두 개의 정점 사이에 간선이 존재할 확률: p
- 정점 간의 연결은 서로 독립적
2) 작은 세상 효과
- 정점 u와 v 사이의 경로(Path): 다음 조건을 만족하는 정점들의 순열(Sequence)
- u에서 시작해서 v에서 끝나야 함
- 순열에서 연속된 정점은 간선으로 연결되어 있어야 함
- 정점 u와 v 사이의 거리(Distance): u와 v 사이의 최단 경로의 길이
- 그래프의 지름(Diameter): 정점 간 거리의 최댓값
- 작은 세상 효과(Small-world Effect): 실제 그래프의 정점들은 가깝게 연결되어 있음
3) 연결성의 두터운 꼬리 분포
- 정점의 연결성(Degree): 그 정점과 연결된 간선의 수, 𝒅(𝒗), 𝒅𝒗 혹은 |𝑵(𝒗)|로 표시
- 나가는 연결성(Out Degree): 그 정점에서 나가는 간선의 수, 𝒅𝒐𝒖𝒕(𝒗) 혹은 |𝑵𝒐𝒖𝒕(𝒗)|로 표시
들어오는 연결성(In Degree): 그 정점으로 들어오는 간선의 수, 𝒅𝒊𝒏(𝒗) 혹은 |𝑵𝒊𝒏(𝒗)|로 표시 - 실제 그래프에는 연결성이 매우 높은 허브(Hub) 정점이 존재함 → Heavy Tail
4) 거대 연결 요소
- 연결 요소(Connected Component): 다음 조건들을 만족하는 정점들의 집합
- 연결 요소에 속하는 정점들은 경로로 연결될 수 있음
- 첫번째 조건을 만족하면서 정점을 추가할 수 없음
- 실제 그래프에는 대부분의 정점을 포함하는 거대 연결 요소(Giant Connected Component)가 존재함
- 랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재하지만 평균 연결성이 1보다 충분히 커야 함
5) 군집 구조
- 군집(Community): 다음 조건들을 만족하는 정점들의 집합
- 집합에 속하는 정점 사이에는 많은 간선이 존재
- 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재
- 지역적 군집 계수(Local Clustering Coefficient): 한 정점에서 군집의 형성 정도 측정
(정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율)- 𝑪𝒊 = 𝒏 / (𝒌𝒊(𝒌𝒊 - 1) / 2) = 2𝒏 / 𝒌𝒊(𝒌𝒊 - 1)
- 𝑪𝒊: 정점 𝒗𝒊의 지역적 군집 계수
𝒏: 정점 𝒗𝒊의 이웃 안의 edge 개수
𝒌𝒊: 정점 𝒗𝒊의 degree - degree가 2 미만인 정점에 대해 지역적 군집 계수 0으로 정의하는 경우도 있음
- 전역 군집 계수(Global Clustering Coefficient): 전체 그래프에서 군집의 형성 정도 측정
(각 정점에서의 지역적 군집 계수의 평균) - 실제 그래프에는 군집이 존재하며, 실제 그래프는 군집 계수가 높음
- 동질성(Homophily): 서로 유사한 정점끼리 간선으로 연결될 가능성 높음
- 전이성(Transivity): 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있음
𝑪𝒊
6) 파이썬을 이용한 지름 및 군집 계수 분석
3. 과제 코드 분석
Metaclass
코멘트
이번주에는 그래프에 대해 배운다. 다행히 오늘 강의는 크게 어려운 내용은 없었던 것 같다.