AITech 학습정리-[DAY 21] 그래프 이론 기초 & 그래프 패턴

 

===============================

학습내용

[Graph 1강] 그래프란 무엇이고 왜 중요할까?

그래프를 이용해 뇌, 지식, 화학, 이미지분해 등등.. 여러분야에 쓰일 수 있다.

그래프 = 네트워크(Network)

정점(Vertex) = 노드(Node)

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

그래프 관련 인공지능 문제

- 정점 분류 (Node Classification) 문제

각 정점이 어느 분야에 속하는지

- 연결 예측(Link Prediction) 문제

네트워크가 어떻게 진화할 것인가

- 추천(Recommendation) 문제

- 군집 분석(Community Detection) 문제

연결 관계로부터 사회적 무리(Social Circle)을 찾아낼 수 있을까? Clustering(군집화) 문제라고도 하는듯.

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

웹(Web) 이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까? 가장 많이 연결되어있으면 제일 랭킹이 높거나 중요한 걸로 해석하는 것 같다.

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

홍보를 위해 어떻게 정보 전달을 최대화 할 수 있을까?

그래프 종류들..

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

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

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

이종 그래프는 다른 종류의 정점 사이에만 간선이 있는 경우 (사용자, 상품), (배우, 영화)

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

보통 정점들의 집합을 V, 간선들의 집합을 E, 그래프를 G = (V,E)

실습

https://colab.research.google.com/drive/1jW6CtWArOKRvhjxB6Rd-QVZ1YYeNbZJq?usp=sharing

실습

https://colab.research.google.com/drive/1xhG3-C2haVbNYxIHoXLFAFp8eyQlUolk?usp=sharing

[Graph 2강] 실제 그래프는 어떻게 생겼을까?

에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph)

임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됩니다

에르되스-레니 랜덤그래프 𝐺(𝑛, 𝑝) 는

✓ 𝑛개의 정점을 가집니다

✓ 임의의 두 개의 정점 사이에 간선이 존재할 확률은 𝑝입니다

✓ 정점 간의 연결은 서로 독립적(Independent)입니다

길이와 경로는 다름을 유의하자. 길이는 말 그대로 경로 간선 길이고 경로는 두 정점 사이의 최단경로 (Shortest Path)이다.

여섯 단계 분리(Six Degrees of Separation) 실험을 진행했는데 임의의 사람에게 지인을 통해서만 편지를 주게 하니, 평균적으로 6단계만을 거쳐서 갔다. 그래서 지인 6명이면 모든사람 다 연결하네 마네 소리가 나온거. 이걸 작은 세상 효과라 부른다.

사실 생각해보면 당연하다. 모든사람이 100명의 지인이 있다고 가정하면 5단계를 거치면 최대 100^5(100억)의 사람과 연결이 되기 때문이다. 하지만 체인 그래프, 사이클 그래프, 격자 그래프등에는 작은 효과 세상이 없음.

앞에 있던 이웃 N과 다르다. N은 정점이 뭔지 저장하는거고 얘는 얼마나 있는지 개수를 저장하는 것. 그래서 |N|으로 절대값으로 나타내기도 한걸 볼 수 있다.

랜덤과 실제가 다른 이유는 랜덤은 말 그대로 랜덤하게 막 연결해서 정규분포 비슷하게 나오지만 실제그래프는 발이 넓은 사람이나 연예인 팬층 등 연결관계가 압도적으로 많은 사람등이 존재해서 그럼.

평균 연결성이 1이상일 때부터 거대 연결 요소가 연결된 비율이 급격하게 늘어난다. 

군집은 말 그대로 비슷한 애들끼리 모여있는거. 그래서 비슷하다고 정의해 놓으니 수학적으로 엄밀한 정의가 되지 않는 것 같다.

여기서 중요한 점은 정점 1의 지역적 군집 계수라고 했을 때 1과 연결된걸 세는게 아닌 1과 연결되어있는 2,3,4,5 끼리의 관계를 보는 것이다. 그래서 C1 = 3/6 = 0.5가 되는 이유가 len((2,3),(2,4),(3,5))) / len((2,3),(2,4),(2,5),(3,4),(3,5),(4,5)) 가 되는 것.

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

정점 i의 지역적 군집 계수가 높다는 것은 그 이웃들도 서로 간선으로 연결되어 있을 확률이 높다 = 이웃들은 높은 확률로 군집을 형성한다 는 뜻.

전역 군집 계수(Global Clustering Coefficient)는 전체 그래프에서 군집의 형성 정도를 측정한다. 즉 그래프 G의 전역 군집 계수는 각 정점에서 직역적 군집 계수가 있을 텐데 그것들의 평균. (모든 지역적 군집 계수) / (지역적 군집 갯수) 인 듯. 단, 지역적 군집 게수가 정의되지 않는 정점은 제외.

실제 그래프에는 동질성(Homophily)과 전이성(Transitivity)이 있어 보통 군집계수가 높다. 같은 인종끼리 모이고 친구가 친구 소개시켜주고.. 랜덤 그래프에서는 이런게 없으니 (간선 연결이 독립적이니까) 지역적 혹은 전역 군집 계수가 높지 않다.

실습

https://colab.research.google.com/drive/1nawpQ1vIoJ2UmTWfcpQGj6TZasdggOCt?usp=sharing

===============================

과제 / 퀴즈

클래스 구조 파악하는데 좀 헷갈렸다. 잘 보자.

https://colab.research.google.com/drive/1_nSG9GrVFKypEj5J11hTrgtnI4_UC9n9?usp=sharing

=================================

피어세션

기존에 하던것보다는 쉬워서 좋았다. 재미없었다 등.. 의견 많음.

무작위로 하면 다른데 여기선 실제 상황까지 고려해서 설계한다니까 놀라웠음.

colab pro는 램이 34GB, 그래픽카드는 16GB.

농협은 꼭 중앙어쩌구에.

================================

후기

의외로 빨리 끝나서 좋다.