Boostcamp Day 21. 2021-02-22.

Graph in AI

Contents

  • 실제 그래프 vs 랜덤 그래프
  • 작은 세상 효과
  • 연결성의 두터운-꼬리 분포
  • 거대 연결 요소
  • 군집 구조
  • 군집 계수 및 지름 분석

Intro

번 강의에서는 실제 그래프의 다양한 패턴들을 배웁니다.

실제 그래프는 다양한 복잡계의 정보를 담고 있습니다. 예를 들어서, 페이스북 네트워크에서 사람을 정점으로 나타내고, 사람들의 친구 관계를 간선으로 나타낼 수 있습니다. 이러한 실제 그래프들은 랜덤으로 생성한 그래프 모델들과 다른 패턴들을 보이고, 우리는 실제 그래프의 패턴들을 이용해서 효과적으로 그래프를 분석할 수 있습니다. 이번 장에서는 실제 그래프와 랜덤 그래프를 간단하게 알아보고, 작은 세상 효과, 연결성의 두터운 꼬리 분포, 군집 구조 등 실제 그래프의 다양한 패턴들을 배우겠습니다. 실제 그래프가 가진 다양한 패턴들에 집중하면서 수업을 들어보세요!


실제 그래프 vs 랜덤 그래프

  • Real Graph : 다양한 복잡계로 부터 얻어진 그래프를 의미
    • ex) SNS, 전자상거래 구매내역, 인터넷, 웹그래프, 단백질 상호작용
  • Random Graph : 확률적 과정을 통해 생성한 그래프를 의미
    • 에르되스,레니가 제안한 그래프 모델.
  • 에르되스-레니 랜덤 그래프
    • 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됨.
    • $G(n,p)$
    • $n$개의 정점을 가짐
    • 임의의 두 개의 정점 사이에 간선이 존재할 확률은 $p$이다.
    • 정점 간의 연결은 서로 독립적(Independent)이다.

작은 세상 효과

필수 개념 : 경로, 거리 및 지름

  • 경로(Path)
    • 정점 $u$와 $v$의 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequence)입니다.
      • u에서 시작해 v에서 끝.
      • 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.
    • 경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의.
  • 지름(Diameter)은 정점 간 거리의 최대값이다.
  • 임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?
    • Six Degree of Separation(여섯단계분리) 실험.
    • 25%만 편지가 도착했지만, 평균적으로 6단계만 거쳤다.
    • MSN 메신저 그래프는 어떨까?
      • 평균적으로 7정도. 하지만 거대 연결 구조만 고려했다.
  • 정점의 연결성(Degree)은 그 정점과 연결된 간선의 수.

연결성의 두터운 꼬리 분포

  • 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 갖는다. 즉, 연결성이 매우 높은 허브(Hub)정점이 존재함을 의미한다.
  • 랜던 그래프의 연결성 분포는 높은 확률로 정규분포와 유사.
    • 이 경우, 연결성이 매우 높은 허브 정점이 존재할 가능성은 0에 가까움.


거대 연결 요소

  • 연결 요소(Connected Component)는 다음 조건들을 만족하는 정점들의 집합을 의미.
    • 연결 요소에 속하는 정점들은 경로로 연결될 수 있다.
    • 위의 조건을 만족하면서 정점을 추가할 수 없다.
  • 실제 그래프에는 거대 연결요소가 존재함. 거대 연결 요소는 대다수의 정점을 포함함.
  • 랜덤 그래프에도 높은 확률로 거대 연결 요소(Giant Connected Componet)가 존재.
  • Futher read : Random Graph Theory


군집 구조

군집(Community)이란 다음 조건들을 만족하는 정점들의 집합이다.

  • 지역적 군집 계수(Local Clustering Coefficient)는 한 정점에서 군집의 형성 정도를 측정함.
    • 정점 i의 지역적 군집 계수는 정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미
  • 실제 그래프에서는 군집 계수가 높음. 즉 많은 군집이 존재함.
  • Homophily(동질성) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높음. 같은 동네 사는 아이들끼리 친구먹는거처럼.

  • 전이성(Transitivity): 공통 이웃이 잇는 경우, 공통 이웃이 매개 역할을 해줄 수 있다. 친구를 서로에게 소개해주는 경우가 그 예시.

  • 반면 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않음. 즉, 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않음.

Summary

  1. 실제 그래프 vs 랜덤 그래프
    • 실제 그래프는 복잡계로부터 얻어지는 반면, 랜덤 그래프는 확률적 과정을 통해 생성된다.
  2. 작은 세상 효과
    • 실제 그래프의 정점들은 가깝게 연결되어 있다
  3. 연결성의 두터운 꼬리 분포
    • 실제 그래프에는 연결성이 매우 높은 허브 정점이 존재
  4. 거대 연결 요소
    • 실제 그래프에는 대부분의 정점을 포함하는 거대 연결요소가 존재함.
  5. 군집 구조
    • 실제 그래프에는 군집이 존재하며, 실제 그래프는 군집 계수가 높다



Reference

  • bootcamp AI Tech pdf .
  • NAVER Connect Foundation.