[그래프] 1-1. 그래프 이론기초

1. 그래프란 무엇이고 왜 중요할까?

---

그래프의 정의 및 구성요소

그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조. 네트워크(Network)라고도 불림
하나의 간선은 두 개의 정점을 연결.
모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아님.

---

그래프는 왜 중요할까?

우리 주변의 많은 관계와 시스템은 복잡계(Complex System)로 구성됨.

• ex : 70억 인구로 구성된 사회, 전자 장치로 구성된 통신 시스템, 정보와 지식, 뇌, 신체 등.
• 공통 특징 : 구성 요소 간의 복잡한 상호작용
• 표현 방법 : 그래프 (= 복잡계를 표현하고 분석하기 위한 언어)
• 활용 분야 : 전산학, 물리학, 화학, 사회과학 → 뇌(뉴런 간 연결), 지식 그래프, 화학 분자, 단백질 구조, 세포 간 유사도 그래프, 이미지 분해

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

 

---

2. 그래프 관련 인공지능 문제

---

정점 분류 문제 (Classification)

• 트위터에서의 공유관계를 분석하여, 각 사용자의 정치적 성향 분류
• 단백질의 상호작용을 분석하여 각 단백질의 역할 알아내기

연결 예측 문제 (Link Prediction)

• 소셜 네트워크는 어떻게 진화할까?
  거시적 관점으로는 '그래프가 어떻게 성장할지?' 예측할 수 있고, 미시적 관점으로는 각 정점이 앞으로 어떤 정점과 연결될지 예측할 수 있다. 이는 추천과도 관계가 있다. 

추천 문제 (Recommendation)

• 각 소비자에게 필요한 물건은 어떤 것이고, 어떤 물건을 구매해야 만족도가 높을까?

군집 분석 문제 (Community Detection)

• 연결 관계로부터 사회적 무리(Social Circle)을 찾아낼 수 있을까?

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

• 웹이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?

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

• 정보는 네트워크를 통해 어떻게 전달 되는지
• 어떻게 정보 전달을 최대화 할 수 있는지

 

 

---

edwith의 그래프와 추천시스템 강의를 듣고 정리 한 내용입니다. 

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith