목차
그래프란 무엇이고 왜 중요할까?
그래프란 무엇일까?
- 그래프는 정점(노드) 집합과 간선(엣지, 링크) 집합으로 이루어진 수학적 구조
- 하나의 간선은 두 개의 정점을 연결
- 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아님
- 우리 주변에는 많은 복잡계(Complex System) 이 있음
- 사회, 통신 시스템, 뇌, 신체 등
- 복잡계는 구성 요소 간의 상호작용으로 이루어짐, 복잡계의 상호작용을 그래프로 표현
→ 그래프는 복잡계를 효과적으로 표현하기 위한 언어
그래프 관련 인공지능 문제
정점 분류 (Node Classification) 문제
-
트위터에서 공유(Retweet) 관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있을까?
- 비슷한 정치적 성향을 가진 사람끼리 공유를 더 많이함
- 새로운 정점이 등장했을 때 어떤 글을 공유했냐에 따라 정치적 성향 예측 가능
연결 예측 (Link Prediction) 문제
- 거시적 관점
- 주어진 그래프가 어떻게 성장할지 예측하는 문제
- 페이스북 소셜네트워크는 어떻게 진화할까?
- 미시적 관점
- 추천 (Recommendation) 문제
- 각 정점이 앞으로 어떤 정점과 연결될지 예측하는 문제
군집 분석 (Community Detection) 문제
- 서로 밀접하게 연결된 정점들의 집합, 군집을 찾아내는 문제
- 많은 그래프에서 군집은 의미있는 구조를 띔
-
연결 관계로부터 사회적 무리 (Social Circle) 을 찾아낼 수 있을까?
랭킹 (Ranking) 및 정보 검색 (Information Retrieval) 문제
- 웹이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?
정보 전파 (Information Cascading) 및 바이럴 마케팅 (Viral Marketing) 문제
- 정보는 네트워크를 통해 어떻게 전달될까? 어떻게 정보 전달을 최대화 할 수 있을까?
그래프 관련 필수 기초 개념
그래프의 유형 및 분류
- 방향
- 방향이 없는 그래프 (Undirected Graph)
- 페이스북 친구 그래프
- 협업 관계 그래프
- 방향이 있는 그래프 (Directed Graph)
- 트위터 팔로우 그래프
- 인용 그래프
- 방향이 없는 그래프 (Undirected Graph)
- 가중치
- 가중치가 없는 그래프 (Unweighted Graph)
- 페이스북 친구 그래프
- 가중치가 있는 그래프 (Weighted Graph)
- 전화 그래프 (전화 횟수)
- 유사도 그래프
- 가중치가 없는 그래프 (Unweighted Graph)
- 정점의 종류
- 동종 그래프 (Unpartite Graph)
- 단일 종류의 정점을 가짐
- 페이스북 친구 그래프
- 이종 그래프 (Bipartite Graph)
- 두 종류의 정점을 가짐
- 다른 종류의 정점사이에만 간선이 연결됨
- 배우 - 영화
- 동종 그래프 (Unpartite Graph)
기초 개념
- 정점들의 집합 V, 간선들의 집합 E, 그래프 G = (V, E)
- 정점의 이웃은 그 정점과 연결된 다른 정점
- N(1) = {2, 5}
- 방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분함
- 나가는 이웃 (Out-Neighbor) 의 집합을 $N\mathit{out}(v)$ 으로 적음
- 들어오는 이웃 (In-Neighbor) 의 집합을 $N\mathit{in}(v)$ 으로 적음
(실습) 그래프의 표현 및 저장
- 파이썬 라이브러리 NetworkX 사용 (Snap.py 라는 라이브러리도 많이 사용함, 사용 불편하지만 빠름)
- 그래프 생성, 변경, 시각화 가능
- 그래프의 구조와 변화 분석 가능
https://colab.research.google.com/drive/1-cbGAX97xMUyn1CkXApn0BWcpKRBRWlB?usp=sharing
https://colab.research.google.com/drive/1pNeTsA_8yeM6rAJPgoBQBiZFwQ9is6eh
간선을 표현하는 방법
- 간선 리스트 (Edge List) : 그래프를 간선들의 리스트로 저장
- 방향성이 있는 경우에는 (출발점, 도착점) 순서로 저장
- 인접 리스트 (Adjacency List) : 각 정점의 이웃들을 리스트로 저장
- 방향성이 없는 경우
- 1 : {2, 5}
- 2 : {1, 3, 5}
- …
- 방향성이 있는 경우, in 과 out 을 따로 만듦
- out
- 1 : {2}
- 2 : {5}
- …
- in
- 1 : {5}
- 2 : {1, 3, 5}
- …
- out
- 방향성이 없는 경우
- 인접 행렬 (Adjacency Matrix)
- 정점 수 x 정점 수 크기의 행렬 (일반 행렬, nx.to_numpy_array)
- 방향성이 없는 경우, 정점 i 와 정점 j 에 간선이 있으면 A[i][j] = 1, A[j][i] = 1
- 방향성이 있는 경우, 정점 i 에서 정점 j 로 가는 간선이 있으면 A[i][j] = 1
- 0이 아닌 원소만을 저장하여 간선의 수에 비례하는 저장 공간 사용 (희소 행렬, nx.to_scipy_sparse_matrix)
- 0 이 많을 때 효율적
- 정점 수 x 정점 수 크기의 행렬 (일반 행렬, nx.to_numpy_array)
실제 그래프는 어떻게 생겼을까?
실제 그래프 vs 랜덤 그래프
- 실제 그래프는 다양한 복잡계로부터 얻어진 그래프
- 소셜 네트워크, 인터넷, 웹, 전자상거래 구매 내역 등
- MSN 메신저 그래프를 예로 보자
- 1억 8천만 정점 (사용자)
- 13억 간선 (메시지를 주고받은 관계)
- 랜덤 그래프는 확률적 과정을 통해 생성한 그래프
- 에르되스-레니 랜덤 그래프
- 임의의 두 정점 사이에 간선이 존재하는지 여부를 동일한 확률 분포로 결정
- 에르되스-레니 랜덤그래프 G(n, p) 는
- n 개의 정점을 가짐
- 임의의 두 개의 정점 사이에 간선이 존재할 확률은 p
- 정점 간의 연결은 서로 독립적
-
G(3, 0.3) 에 의해 생성될 수 있는 그래프와 각각의 확률은?
- 8 개의 결과가 나올 수 있으며 각 확률은 p 나 not p 를 n 번이 되도록 곱함
- 에르되스-레니 랜덤 그래프
그래프의 구조적 특성
- 실제 그래프의 구조적 특성
- 작은 세상 효과
- 연결성의 두터운 꼬리 분포
- 거대 연결 요소
- 군집 구조
- 랜덤 그래프의 구조적 특성 (항상 만족하진 않음)
- 작은 세상 효과
- 거대 연결 요소
필수 개념 : 경로, 거리 및 지름
- 정점 u 와 v 사이의 경로(path) 는 아래 조건을 만족하는 정점들의 순열(sequence)
- u 에서 시작해서 v 에서 끝나야 함
- 순열에서 연속된 정점은 간선으로 연결돼야 함
- 경로의 길이는 해당 경로 상에 놓인 간선의 수, 경로의 정점 개수 - 1
- 경로 1, 4, 6, 8 의 길이는 3
- 정점 u 와 v 사이의 거리(Distance) 는 u 와 v 사이의 최단 경로의 길이
- 위 예시에서 여러 경로 중 가장 길이가 작은 3
- 그래프의 지름(Diameter) 은 정점 간 거리의 최댓값
- 위 예시에서 2 와 8 or 2 와 7 의 거리인 4 가 지름
작은 세상 효과
- 임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?
- 여섯 단계 분리 (Six Degrees of Separation) 실험
- 1960년대 수행된 실험에서 한 지역에서 다른 지역으로 편지를 보낼 때 지인을 통해 전달할 경우 6 단계가 걸린다는 실험
- MSN 메신저에서도 정점 간의 평균 거리는 7 정도 (거대 연결 구조에 속하는 정점만 고려)
→ 이러한 현상을 작은 세상 효과라고 함
- 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재
- 모든 사람이 100명의 지인이 있다 하면 5명만 거쳐도 100억명을 알 수 있음
- 하지만 모든 그래프에서 효과가 나타나지 않음 (체인, 사이클, 격자 그래프에서는 효과가 존재하지 않음)
연결성 (Degree)
- 정점의 연결성은 그 정점과 연결된 간선의 수
- 해당 정점의 이웃들의 수와 같음
- d(v), $d_v$ 혹은 |N(v)| 로 적음
- 방향 그래프에서는 in, out 존재
연결성의 두터운 꼬리 분포
- 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail) 를 가짐
- 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재
- 트위터 팔로워 일반인과 비교하여 BTS (Hub) 는 매우 높은 연결성 지님
- 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사
- 실제 분포 중 안되는 경우는 키의 분포, 10 미터 넘을 수 없음
거대 연결 요소
- 연결 요소 (Connected Component) 의 조건
- 연결 요소에 속하는 정점들은 경로로 연결될 수 있음
- 위 조건을 만족하면서 정점을 추가할 수 없음
- 실제 그래프에는 거대 연결 요소 (Giant Connected Component) 가 존재함
- 거대 연결 요소는 대다수의 정점을 포함
- MSN 메신저 그래프에는 99.9% 의 정점이 하나의 거대 연결 요소에 포함됨
- 랜덤 그래프에도 높은 확률로 거대 연결 요소 존재
- 단, 정점들의 평균 연결성이 1보다 충분히 커야함
- 자세한 이유는 Random Graph Theory 참고
군집 구조
- 군집 (Community) 이란 다음 조건들을 만족하는 정점들의 집합 (수학적으로 엄밀한 정의는 아님)
- 집합에 속하는 정점 사이에는 많은 간선이 존재
- 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재
- 지역적 군집 계수 (Local Clustering Coefficient) 는 한 정점에서 군집의 형성 정도를 측정
- 정점 i 의 지역적 군집 계수는 정점 i 의 이웃 쌍 중 간선으로 직접 연결된 것의 비율
- 정점 i 의 LCC 는 $C_i$ 로 표현
- 이웃끼리 연결된 개수 / 이웃개수C2
- 지역적 군집 계수와 군집과 관계
- 정점 i 의 지역적 군집 계수가 매우 높으면, 정점 i 의 이웃끼리 많이 연결돼있기 때문에 정점 i 와 그 이웃들은 높은 확률로 군집 형성
- 전역 군집 계수 (Global Clustering Coefficient) 는 전체 그래프에서 군집의 형성 정도를 측정
- 그래프 G 의 전역 군집 계수는 각 정점에서의 지억적 군집 계수의 평균 (단, 연결성이 0이라 지역적 군집 계수가 정의되지 않는 정점 제외)
- 실제 그래프는 군집 계수가 높음. 즉 많은 군집이 존재
- 다양한 이유
- 동질성 (Homophily) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높음
- 같은 동네에 사는 같은 나이의 아이들이 친구가 됨
- 전이성 (Transitivity) : 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줌
- 친구를 서로에게 소개해주는 경우
- 동질성 (Homophily) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높음
- 다양한 이유
- 반면, 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않음
- 랜덤 그래프 G(n, p) 에서 군집 계수는 p 인데, 이는 독립적이므로 간선 연결에 있어 전이성과 동질성이 없음. 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않음
(실습) 군집 계수 및 지름 분석
- 작은 세상 그래프는 균일 그래프에서 몇 간선을 임의로 연결해준 것
https://colab.research.google.com/drive/1ll62ZpmgdOaOcthy50mzQL74u9TflJCG#scrollTo=qEI5BI2onH4v
Further Reading
피어 세션
MJ 님 넥슨 면접 후기
- 머신러닝 기본, GAN, Transformer, BERT 등 다양한 영역의 질문이 나옴
- 인성보다 기술을 많이 물어봄
주말 회고
샐리님 : 증명사진 찍음 (처참ㅋㅋ)
히스님 : 생일을 보냄
원딜님 : 졸업식이라 학교에서 놀고 캐글 과제 하다가 다른 캐글 프로젝트 함. 공부 의욕이 떨어져서 유튜버 조코딩님과 이유한님 인터뷰 보고 공부의욕 불타는 상태
펭귄님 : 핸드폰만 했음. 펜트하우스 봄. (기만)
서폿님 : 코드플래닛? 강의 플랫폼 공부. 월 4만원.
후미님 : 롤챔스 경기 보고 일리 캡슐 커피 머신 삼.
mj님 : 면접 준비와 공부 때문에 스트레스 받아서 침대 명상을 함. 헬스도 하고 면접 준비했음.
수업 질문
Today I Felt
졸업
지난주 금요일 졸업을 했다. 학교에서 좋은 사람들을 통해 선한 가치를 배울 수 있었다. 이제는 AI 기술로 사회에 선한 영향을 주는 사람이 되고 싶다. 이를 위해서는 실력 있는 사람이 돼야할 것이다. 아직은 모든게 미비하지만 부캠을 통해 실력을 키우고 옆에 있는 조원들과 다른 캠퍼들에게 좋은 영향을 주는 사람이 될 수 있도록 노력해야겠다. 나아가 대학원을 가든 취업을 하든 이 목표를 바라보며 나아가리라.