[Day 21] 그래프 이론 기초 & 그래프 패턴

[Day 21] 그래프 이론 기초 & 그래프 패턴

 

 

1. 강의 복습 내용

---

그래프 이론 기초 & 그래프 패턴

 

 

1. 그래프 Overview

1) 그래프 (Graph)

- 그래프(Graph)는 네트워크(Network)라고도 불림

- 그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조

- 하나의 간선은 두 개의 정점을 연결

- 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아님

- 정점(Vertex) = 노드(Node)

- 간선 = 엣지(Edge) = 링크(Link)

- 그래프는 복잡계를 표현하고 분석하기에 용이한 일종의 언어

그래프로 나타낼 수 있는 예시

*) 위와 같이 복잡계는 구성 요소들 간의 상호작용으로 이루어진다.

- 상호작용을 표현하기 위한 수단으로 그래프가 용이, 널리 사용된다.

- 따라서 복잡계를 이해하고, 복잡계에 대한 정확한 예측을 위해서는 복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요

 

---

2) 그래프 (Graph) 관련 인공지능 문제

- 정점 분류(Node Classification) 문제

ex) 트위터에서의 공유 관계를 분석하여, 각 사용자의 정치석 성향 파악

ex) 단백질의 상호작용을 분류하여 단백질의 역할 파악

 

- 연결 예측(Link Prediction) 문제

ex) 페이스북 소셜네트워크는 어떻게 진화할까?

 

- 추천(Recommendation) 문제

ex) 각자에게 필요한 물건은 무엇일까? 어떤 물건을 구매해야 만족도가 높을까?

 

- 군집 분석(Community Detection) 문제

ex) 연결 관계로부터 사회적 무리(Social Circle) 찾기

 

- 랭킹(Ranking) 및 정보검색(Information Retrieval) 문제

ex) 웹으로 부터 중요한 웹페이지 찾아내기

 

- 정보 전파(Information Cascading) 및 바이럴 마케팅(Viral Marketing) 문제

ex) 정보는 네트워크를 통해 어떻게 전달될까? 어떻게 정보 전달을 최대화 할 수 있을까?

---

3) 그래프 (Graph) 유형 및 분류

- 방향이 없는 그래프(Undirected Graph)와 방향이 있는 그래프(Directed Graph)

 

- 가중치가 없는 그래프(Unweighted Graph)와 가중치가 있는 그래프(Weighted Graph)

 

- 동종 그래프(Unpartite Graph)와 이종 그래프(Bipartite Graph)

---

4) 그래프 (Graph)의 표현

- 간선 리스트 (Edge List) : 그래프를 간선들의 리스트로 저장

- 인접 리스트 (Adjacent List)

방향성이 없을 경우

방향성이 있는 경우

 

- 인접 행렬(Adjacency Matrix)

 

---

 

2. 그래프 패턴

1) 랜덤 그래프

- 확률적 과정을 통해 생성한 그래프

- 에르되스-레니 랜덤그래프 G(n,p)

- n개의 정점을 가지고, 임의의 두 개의 정점 사이에 간선이 존재할 확률은 p

- 정점 간의 연결은 서로 독립적

---

2) 작은 세상 효과

- 인간 관계에서 몇 단계만 거치면 서로 연결되어 있다는 것을 보인 이론 (ex) 여섯 단계 분리 이론)

- 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재

- 그러나 모든 그래프에서 작은 세상 효과가 존재하지는 않다. (반례: 체인, 사이클, 격자 그래프)

---

3) 연결성의 두터운 꼬리 분포

- 정점의 연결성(Degree)는 그 정점과 연결된 간선의 수 (= 정점의 차수)

- 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 갖는다.

- 이는 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재한다는 것이다.

실제 그래프의 연결성 분포

 

- 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사하다.

- 이 경우에는 연결성이 매우 높은 허브(Hub) 정점이 존재할 가능성은 0에 가깝다.

랜덤 그래프의 연결성 분포

 

- 즉, 실제 그래프와 랜덤 그래프에는 차이가 존재한다.

랜덤 그래프 vs 실제 그래프

---

4) 거대 연결 요소

- 연결 요소(Connected Component)는 다음 두 조건을 만족하는 정점들의 집합

- 즉, 그래프 속에서 임의의 두 정점의 경로가 항상 존재하는 부분 그래프 속 정점들의 집합

(1) 연결 요소에 속하는 정점들은 경로로 연결될 수 있다.

(2) (1)의 조건을 만족하면서 정점을 추가할 수 없다.

 

- 실제 그래프에는 거대 연결 요소(Giant Connected Component)가 존재

- 거대 연결 요소는 대다수의 정점을 포함한다.

 

- 랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재한다.

- 단, 정점들의 평균 연결성이 1보다 충분히 커야 한다.

---

5) 군집 구조

- 군집(Community)이란 다음 조건들을 만족하는 정점들의 집합

(1) 집합에 속하는 정점 사이에는 많은 간선이 존재

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

 

- 지역적 군집 계수(Local Clustering Coefficient)는 한 정점에서의 군집 형성 정도를 측정

*) 연결성(차수)이 0인 정점에서는 지역적 군집 계수가 정의되지 않는다.

 

- 전역 군집 계수(Global Clustering Coefficient)는 전체 그래프에서 군집의 형성 정도를 측정

- 그래프 G의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균

- 단, 지역적 군집 계수가 정의되지 않는 정점(연결성이 0인 정점)은 제외

 

- 실제 그래프에서는 군집 계수가 높다. 즉 많은 군집이 존재한다.

(1) 동질성(Homophily) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다.

(2) 전이성(Transitivity) : 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있다.

 

- 반면, 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않다.

- 랜덤 그래프 G(n,p)에서의 군집계수는 p이다.

- 랜덤 그래프에서의 간설 연결은 '독립적' 이기 때문

- 즉, 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않는다. (동질성, 전이성을 적용할 수 없다)

---

2. 피어 세션

---

1. 강의 내용에 대한 토의

- 방향성이 없는 그래프와 방향성이 있는 그래프의 두터운 꼬리 분포 차이?

- 연결 요소의 정의

 

2. 저번 주 금요일 과제에 대한 토의

 

- 각자 시행해본 파인 튜닝 과정

- Classification imbalanced 문제

- Ensemble의 다양한 방법

---

3. Conclusion

---

새로운 한 주가 시작되었고, 저번주는 NLP에 대해 학습하였지만 이번주는 새로운 내용 그래프에 돌입하였다.

그래프는 그동안 코딩테스트에서도 많이 나온 개념이였으므로 오늘은 수월했지만, 이를 신경망에 어떻게 적용하고 모델링에서 그래프 개념을 어떻게 적용시켜 더 발전된 딥러닝 개념을 이끌어내는지 아직 감이 잡히진 않는다.

---