[추천시스템] 그래프와 추천시스템 : 1. 그래프 이론의 기초

<네이버 Boost course의 강의 내용 정리>

1. 그래프 이론의 기초

1.1 그래프란 무엇이고 왜 중요할까
    1.1.1 그래프란 무엇일까
    1.1.2 그래프가 왜 중요할까?
1.2 그래프 관련 인공지능 문제
    - 정점 분류(Node Classification) 문제
    - 연결 예측(Link Prediction) 문제
    - 추천(Recommendation) 문제
    - 군집 분석(Community Detection)
    - 랭킹(Ranking) 및 정보 검색(Information Retrieval)
    - 정보 전파(Information Cascading) 및 바이럴 마케팅(Viral Marketing) 문제

 

1.1 그래프란 무엇이고 왜 중요할까

1.1.1 그래프란 무엇일까

• 그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조이다.
• 하나의 간선(엣지,링크)은 두 개 이상의 정점(노드)을 연결한다.
• 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아니다.
• 그래프를 네트워크라고도 부른다.

출처: https://www.boostcourse.org/ai211/lecture/1108373

 

1.1.2 그래프가 왜 중요할까?

• 다양한 복잡계가 존재한다.
• 사회, 통신시스템, 정보, 지식, 뇌, 신체 등
• ✔️ 예시
  • 소셜네트워크 - Facebook, LinedIn, Line, KakaoTalk
  • 전자상거래 구매내역 - amazon, ebay, 네이버쇼핑 사용자가 제품을 구매했다면 간선이 생긴다.
  • 랜선, 뇌, 지식,그래프, 화학분자...
    
    

✅ 복잡계의 공통적인 특성: 구성요소 간의 복잡한 상호작용

• 상호작용이 복잡계를 복잡하게 만든다.
• 이러한 복잡한 상호작용을 표현하기 위한 수단이 그래프이다.
• 그래프는 복잡계를 효과적으로 표현하고 분석하기 위한 언어이다.
• 복잡계를 이해하고 복잡계에 대한 정확한 예측을 하기 위해서는
  복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요하다.
• 그래프를 공부함으로써 복잡계가 등장하는 수많은 분야에서 활용할 수 있다.
  • 전산학, 물리학, 생물학, 화학, 사회과학 등

 

1.2 그래프 관련 인공지능 문제

▶️ 정점 분류(Node Classification)

• 정점이 여러 유형을 가진 경우, 각 정점의 유형을 추측하는 문제
• ✔️ 예시 1
  • 트위터(현 'X')에서의 공유 관계:
    리트윗. 어떤 계정이 어떤 계정의 글을 리트윗했는지를 간선으로 표시한 것
  • 다양한 주제 중 하나가 정치. 크게 (보수 vs 진보)로 나누어 색으로 표시함
  • 같은 정치적 성향을 가진 사람들끼리 좀 더 글을 많이 공유했다.
  • 같은 색을 가진 사람은 같은 정치 성향을 가졌다고 볼 수 있다.
  • '새로운 정점의 등장, or 정치적 성향을 모르는 정점이 등장했을 때
  • 그 정점이 어떤 계정의 글을 공유했는지를 통해 그 정점이 어떤 정치적 성향을 가졌는지 추측할 수 있다.

출처: https://www.boostcourse.org/ai211/lecture/1108373

• ✔️ 예시 2
  • 단백질의 상호작용을 분석하여 단백질의 역할을 알아낼 수 있는가
  • 각 단백질이 다른 단백질과 어떻게 상호작용하는지 확인하면서 단백질의 역할을 분류하는 문제

출처: https://www.boostcourse.org/ai211/lecture/1108373

 

▶️ 연결 예측(Link Prediction)

• 거시적관점 - 주어진 그래프가 어떻게 성장할 지 예측하는 문제'
• ✔️ 예시 1
  • 페이스북 소셜네트워크는 앞으로 어떻게 진화할까?
  • 사람들은 앞으로 상호작용을 더 많이 할까? 적게 할까?
  • 한 사람은 더 많은 사람과 상호작용할까? 적은 사람과 상호작용할까?
• 미시적 관점 - 각 정점이 앞으로 어떤 정점과 연결될 지를 예측하는 문제
• → 추천 문제와도 밀접한 관련

 

▶️ 추천(Recommendation) ⭐️

• 많은 추천시스템들이 추천을 할 때 각 사용자가 어떤 물건을 구매할지 예측하여 이를 토대로 추천한다.
• 어떤 물건을 살지, 어떤 물건을 구매해야 만족도가 더 높을지를 복잡한 요소를 고민
• 좋아요, 장바구니, 주문내역 등

출처: https://www.boostcourse.org/ai211/lecture/1108373

 

▶️ 군집 분석(Community Detection)

• 서로 밀접하게 연결된 정점의 집합, 즉 군집을 찾아내는 문제
• 이러한 군집을 자동으로 찾아내는 알고리즘을 만드는 문제
• 많은 그래프에서 군집들은 의미있는 구조를 나타낸다.
• ✔️예시 1
  • 페이스북 소셜네트워크: 군집을 발견할 수 있다.
  • 연결 관계로부터 사회적 무리(Social Circle)를 찾아낼 수 있을까?

출처: https://www.boostcourse.org/ai211/lecture/1108373

 

▶️ 랭킹(Ranking) 및 정보 검색(Information Retrieval)

• 전세계 인구수보다 더 많은 웹페이지가 존재한다고 알려져 있다.
• WEB이라는 거대한 그래프로부터 어떻게 우리가 찾고 싶은, 중요한 웹페이지를 찾아낼 수 있을까?
• 웹을 거대한 그래프로 표현하고 웹페이지들 간의 연결관계를 분석하여 중요하고 관련성 있는 웹페이지들을 찾아낸다.

출처: https://www.boostcourse.org/ai211/lecture/1108373

 

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

• 소셜네트워크를 통해 많은 정보들이 전파된다.
• 정보는 소셜네트워크를 통해 어떻게 전파될까?
• 어떻게 정보 전달을 최대화할 수 있을까?

출처: https://www.boostcourse.org/ai211/lecture/1108373

 

 

출처: 네이버 부스트코스 - 그래프와 추천시스템

https://www.boostcourse.org/ai211/lecture/1108373

그래프와 추천 시스템