그래프(Graph)란?
- 정점(Vertex/Node)집합과 간선(Edge/Link)집합으로 이루어진 수학적 구조
- 복잡계(Complex System)을 잘 표현할 수 있는 도구
그래프관련 인공지능 문제
- Node Classification
트위터에서 Retweet관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있을까?
- Link Prediction
페이스북 소셜네트워크는 어떻게 진화할까?
- Recommendation
각자 필요한 물건은 무엇일까? 어떤 물건을 구매해야 만족도가 높을까?
- Community Detection
연결 관계로부터 사회적 무리(Social Circle)를 찾아낼 수 있을까?
- Ranking 및 Information Retrivial 문제
웹이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?
- Information Cascading 및 Viral Marketing 문제
정보는 네트워크를 통해 어떻게 전달될까?
그래프 유형 및 분류
Undirected Graph vs Directed Graph
간선에 방향이 있는 그래프
- 협업 관계 그래프
- 페이스북 친구 그래프
간선에 방향이 없는 그래프
- 인용 그래프
- 트위터 팔로우 그래프
Unweighted Graph vs weighted Graph
간선에 가중치가 있는 그래프
- 웹 그래프
- 페이스북 친구 그래프
간선에 가중치가 없는 그래프
- 전화 그래프
- 유사도 그래프
Unpartite Graph vs Bipartite Graph
단일 종류의 정점이 있는 그래프
- 웹 그래프
- 페이스북 친구 그래프
두 종류의 정점이 있는 그래프
- 정자 상거래 구매내역(사용자, 상품)
- 영화 출연 그래프 (배우, 영화)
그래프의 표현
- 어떤 그래프 G의 정점들의 집합 V, 간선들의 집합 E 라고 하면 G=(V,E)
- 정점의 Neighbor은 그 정점과 연결된 다른 정점을 의미, 정점 v의 이웃들의 집합을 보통 N(v) 혹은 Nv로 표현
- 방향성이 있는 그래프에서는 In/Out을 구분해 표현
