728x90
반응형
1. 그래프란 (Graph)?
그래프(Graph): 정점 집합과 간선 집합으로 이루어진 수학적 구조. 네트워크라고 부르기도 함
- 정점(Vertex), 노드(Node)
- 간선, 엣지(Edge), 링크(Link)
- 하나의 간선은 두 개의 정점을 연결 (모든 정점 쌍이 반드시 간선으로 직접 연결된 것은 아님)
그렇다면 그래프를 어떻게 수식으로 표현할까?
- $$ G = (V, E) $$
- G 는 그래프, V 는 정점들의 집합, E 는 간선들의 집합
정점과 연결된 정점은 어떻게 말하고 표현할까? -> 정점의 이웃(Neighbor)
- N(v) 혹은 $$ N_v $$ 로 표현
- 방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분
- $$ N_{out} (v) $$: 정점 v에서 간선이 나가는 이웃들의 집합 (Out-Neighbor)
- $$ N_{in} (v) $$: 정점 v에서 간선이 들어오는 이웃들의 집합 (In-Neighbor)
2. 그래프가 왜 중요할까?
- 우리 주변에 많은 복잡계가 있음 (예: 사회, 통신 시스템, 정보와 지식, 뇌 신체 등)
- 이러한 복잡계는 구성 요소 간의 복잡한 상호작용이 있다는 공통점이 있음
- 그래프는 이러한 복잡한 상호작용을 가진 복잡계를 표현 및 분석하기 위한 적절한 도구이자 언어임
3. 그래프의 유형 및 분류
방향의 유무에 따른 분류
- 방향이 없는 그래프 (Undirected Graph): 간선에 방향이 없는 그래프
예: 협업 관계 그래프, 페이스북 친구 그래프 - 방향이 있는 그래프 (Directed Graph): 간선에 방향이 있는 그래프 - 관계를 맺을 때, 주체와 대상이 동등한 관계가 아님
예: 논문 인용 그래프, 트위터 팔로우 그래프
가중치의 유무에 다른 분류
- 가중치가 없는 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프
예: 웹 그래프, 페이스북 친구 그래프 - 가중치가 있는 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프
예: 전화 그래프 (전화를 많이할 수록 친밀도가 높다고 판단), 유사도 그래프
정점의 종류에 따른 분류
- 동종 그래프 (Unpartite Graph): 단일 종류의 정점을 가지는 그래프 (동종간 연결)
예: 웹 그래프, 페이스북 친구 그래프 - 이종 그래프 (Bipartite Graph): 다른 종류의 정점을 가지는 그래프 (이종간만 연결)
예: 전자 상거래 구매 내역 (사용자-상품), 영화 출연 그래프 (배우-영화)
4. 인공지능과 그래프로 푸는 문제
- 정점 분류 (Node Classification): 정점들이 여러 유형을 가질 수 있다고 가정할 때, 각 정점이 어떤 유형이 속하는지 판단하는 것
- 연결 예측 (Link Prediction): 그래프의 연결관계에 관한 문제
- 거시적 관점: 그래프가 성장할 것인가? 그래프가 커지거나 작아질 것 인가?
- 미시적 관점: 각 정점이 앞으로 어떤 정점에 연결될 것인가? - 추천 문제(Recommendation)로 이어짐 - 추천 (Recommendation): 각 정점을 어떤 정점에 연결할 것인가? 정확도와 만족도는? - Link Prediction의 미시적 관점과 연관
- 군집 분석 (Community Detection): 밀접하게 연결된 정점들의 집합, 즉 군집을 찾아내는 것! 이를 통해 의미있는 사회적 무리를 찾을 수 있음 (기계학습의 클러스터링과 유사)
- 랭킹 (Ranking) 및 정보 검색 (Information Retrieval): 수많은 웹 페이지에서 찾고자하는 웹페이지 및 내용을 거대한 그래프로 표현 및 분석하여 찾고자 하는 것과 관련성이 높은 것을 제시
- 정보 전파 (Information Cascading) 및 바이럴 마케팅 (Viral Marketing): 정보가 어떻게 전파되는지 그래프를 통해 파악하여 효과적인 정보 전파 수단을 파악 가능
본 내용은 부스트코스의 '그래프와 추천 시스템' 강의를 토대로 작성되었습니다
728x90
반응형
