그래프와 추천시스템 1-3

그래프와 추천시스템 1-3

그래프 이론 기초

---

• 그래프
  • 복잡계

    완전한 질서나 완전한 무질서를 보이지 않고, 그 사이에 존재하는 계로써, 수많은 요소들로 구성되어 있으며 그들 사이의 상호작용에 의해 집단성질이 떠오르는 다체 문제이다

  • 그래프는 복잡계를 효과적으로 표현하기 위한 언어이다.

• 그래프의 문제
  • 정점 분류 문제(Node Classification)
    • 정점이 어떤 클래스에 속할지 분류
  • 연결 예측 문제(Link Prediction)
    • 거시적 관점: 어떻게 연결이 진화할 지 예측 (성장, 감소 등)
    • 미시적 관점: 각 정점이 앞으로 어떤 정점과 연결될지 예측 (추천)
  • 군집 분석(Community Detection)
  • 랭킹, 정보 검색 문제
  • 정보 전파, 바이럴 마케팅 문제

• 그래프의 유형 및 분류
  • 방향, 무방향: 관계가 대등한지 아닌지에 따라 다름
  • 가중치 유뮤
  • 동종(unpartite graph), 이종(Bipartite graph): 사람-사람 vs 사람-상품

• 그래프 표현

  정접 집합: V, 간선집합 E, 그래프 G=(V,E)

  • 무방향 이웃

    N(1) = {2,5} : 1번 정점은 2번, 5번 정점과 연결됨

  • 유방향 이웃

    $N_{in}(v)$: 정점 v로 들어오는 이웃 정점 집합

    $N_{out}(v)$: 정점 v에서 나가는 이웃 정점 집합

그래프 패턴

---

• 실제 그래프 vs 랜덤그래프
  • 실제 그래프: 소셜 네트워크, 전자상거래 구매 내역, 인터넷, 웹 페이지 그래프, 지식그래프 등
  • 랜덤 그래프: 확률정 과정을 통해 생성한 그래프
    • 에르되스-레니 랜덤그래프

      임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됨

      G(n,p)는 n개의 정점을 가지며, 간선이 존재할 확률은 p

      정점간의 연결은 서로 독립적이다.

      ex. G(3,0.3)에서 생성될 수 있는 확률가 각각의 확률?

• 실제 그래프의 구조적 특성
  • 작은세상 효과 - 경로
  • 거대 연결 요소 - 연결성
  • 군집 구조 - 군집

• 작은 세상 효과
  • 경로: 두 정점 u, v의 경로는 아래 조건을 만족하는 순열(sequence)

    u에서 시작해 v에서 끝나야 한다. 순열에서의 연속된 정점은 간선으로 연결되어 있어야 한다.

  • 거리: 두 정점 u, v의 길이는 최단 경로이다.
  • 그래프의 지름: 모든 정점간의 거리의 최댓값
  • 작은 세상 효과: 임의의 두 지인은 서로 몇 명을 거치면 서로 알 수 있나.

    → 정점의 평균 거리

  • 모든 그래프에서 작은 세상 효과가 존재하지는 않다. 아래와 같은 그래프들에서는 작은 세상 효과가 존재하지 않는다.

    

• 연결성(Degree)

  정점 v의 연결된 간선의 수. $d(v), \ d_{v}, \ |N(v)|$로 표현

  방향성 그래프의 경우, in out 구분. $d_{in}(v), d_{out}(v)$여

• 연결성의 분포

  실제그래프에서의 연결성 분포는 두터운 꼬리(heavy tail)분포를 갖는다. (연결성이 매우 높은 허브 정점이 존재함을 의미함)

  랜덤그래프에서의 연결성 분포는 높은 확률로 정규분포와 유사하다.

  

• 거대 연결요소
  • 연결요소(Connected Component)

    연결 요소에 속하는 정점들은 경로로 연결될 수 있다. 이전 조건을 만족하면서, 정점을 추가할 수 없다.

  • 거대 연결 요소

    실제 그래프에는 거대 연결요소가 존재하며, 거대 연결요소는 대다수의 정점을 포함한다.

    MSN 메신저 그래프에는 99.9%의 정점을 포함하는 하나의 거대연결요소가 있다.

    자세한 이유는 Random Graph Theory에 있다. (https://dl.acm.org/doi/pdf/10.1145/3369782)

• 군집

  군집의 집합에 속하는 정점에는 많은 간선이 존재하며, 군집의 집합에 속하지 않은 정점 사이에는 적은 수 의 간선 존재.

  • 지역적 군집 계수(local clustering coefficient)

    한 정점에서 군집 형성 정도 측정. i 정점에서의 지역적 군집계수는 정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미

    연결성이 0인 정점에서의 지역적 군집 계수는 분모가 0이기 때문에 정의하지 않음

    정점 i의 지역적 군집 계수가 높은 경우, i와 이웃들은 높은 확률로 군집을 형성한다.

    $4/{_{5}C_{2}}$ , $3/{_{5}C_{2}}$ , $0/{_{5}C_{2}}$

    

    다른 군집계수 : https://en.wikipedia.org/wiki/Clustering_coefficient

  • 전역 군집 계수(global clustering coefficient)

    전체 그래프에서의 군집의 형성 정도 측정

    그래프 G의 전역 군집 계수는 각 정점들의 지역적 군집 계수 평균 (정의 되지 않은 정점 제외)

    • 실제 그래프에서 지역적/전역 군집 계수가 높은 이유(군집이 많은 이유):

      동질성(Homophily): 유사한 정점끼리 간선의 연결성이 높다.

      전이성(Transitivity): 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 할 수 있다.

    • 랜덤그래프에서 지역적/전역 군집 계수가 낮은 이유:

      간선간의 연결을 독립으로 설정

페이지 랭크

---

• 웹

  페이지라는 정점과 하이퍼링크라는 간선이 있는 방향성 그래프

• 페이지 랭크 이전의 검색엔진
  • 디렉토리 기반: 카테고리의 수와 깊이가 너무 커짐
  • 키워드 기반: 악의적 웹페이지에 취약

• 페이지랭크란
  • 투표 관점: 웹페이지는 하이퍼링크를 통해 투표한다. 하이퍼링크를 포함한 웹페이지의 작성자가 판단하기에, 하이퍼링크를 받은 웹페이지가 관련성이 높고 신뢰할 수 있다는 것을 의미함.

    하지만, 관련성과 신뢰성이 높아보이도록 조작 가능.

    → 이를 해결하기 위해, 가중(weighted) 투표를 함. 신뢰성이 높은 웹사이트의 투표를 더 중요하게 간주함.

    • 페이지 랭크 점수: 웹페이지의 관련성, 신뢰도 점수

      

    • 계산: 연립방정식으로 풀이
  • 랜덤워크 관점

    랜덤워크를 통해 웹을 서핑하는 한 웹서퍼를 가정한다. 웹서퍼가 t번째에서 웹페이지 i를 방문할 확률을 $p_{i}(t)$라고 하면, t+1에서 웹페이지 j를 방문할 확률을 아래와 같이 표현할 수 있다.

    

    이 때, 웹서퍼가 해당 과정을 무한히 반복하면 (t가 무한히 커지면) p(t) = p(t+1) = p인 정상 분포를 띠며, 아래와 같이 표현할 수 있다.

    

• 페이지랭크 점수 계산
  • 반복곱(power iteration)

    

    • 예시

      

    • 질문

      Q. 반복곱의 계산이 항상 수렴하는가

      A. 아니다. 나가는 간선이 없는 spider trap같은 경우

      Q. 합리적인 점수로 수렴하는 것을 보장하는가

      A. 아니다. 막다른 정점(Dead end)으로 들어가는 경우

      ⇒ 해결방안

      

      이는 페이지 랭크의 점수를 아래와 같이 바꾼다는 것을 의미한다.

      

Ref

---

• 강의: https://www.boostcourse.org/ai211/joinLectures/316864

• 코드: https://github.com/NamSahng/TIL/tree/master/recsys/codes_graph