[BoostCamp] DAY21 Graph#1

[BoostCamp] DAY21 Graph#1

---

1. 그래프를 이용한 기계학습

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

1.1 그래프란 무엇일까?

정점 집합과 간선 집합으로 이루어진 수학적 구조이다.

• 하나의 간선은 두개의 정점을 연결한다.
• 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아니다.
• 그래프는 Network라고도 불린다.
  • 정점 : vertex, node
  • 간선 : edge, link

1.2 그래프가 왜 중요할까?

우리 주변에는 많은 복잡계가 있다.

• 사회는 70억 인구로 구성된 복잡계이다.
• 통신시스템은 전자장치로 구성된 복잡계이다.
• 이외에도 정보, 지식, 뇌, 신체등의 복잡계가 존재한다.

복잡계가 가진 공통적인 특성?

구성 요소간의 복잡한 상호작용이다.

어떻게 이런 복잡계를 표현할 수 있을 까?

• Graph로 표현하면 된다. 즉, Graph는 복잡계를 효과적으로 표현하고 분석하기 위한 언어이다.
• 복잡계는 구성 요소들 간의 상호작용으로 이루어진다.
• 상호작용을 표현하기 위한 수단으로 graph가 널리 사용된다.
• 복잡계를 이해하고 복잡계에 대한 정확한 예측을 하기 위해서는 복잡계 이면에 있는 graph에 대한 이해가 반드시 필요하다.

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

정점 분류 문제

• 트위터에서 공유 관계를 분석하여 각 사용자의 성향을 분석하는 문제
• 단백질의 상호작용을 분석하여 단백질의 역할 분석 문제
• 

연결 예측 문제

• 페이스북 소셜네트워크는 어떻게 진화할까?(거시적 관점)

추천 문제

• 각자에게 필요한 물건은 무엇일까?
• 어떤 물건을 구매해야 만족도가 높을 까?

군집분석 문제

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

랭킹 및 정보 검색의 문제

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

정보전차 및 바이럴 마케팅에 대한 문제

• 정보는 네츠워크를 통해 어떻게 전달될까? 어떻게 정보 전달을 최대화 할 수 있을까?

3. 그래프 관련 필수 기초 개념

3.1 그래프의 유형 및 분류

1. 방향성이 없는 그래프 VS 방향이 있는 그래프
   • 방향성이 없는 그래프 (Undirected Graph)
     • 협업 관계 그래프
     • 페이스북 친구 그래프
   • 방향성이 있는 그래프 (Directed Graph)
     • 인용 그래프
     • 트위터 팔로우 그래프
2. 가중치가 없는 그래프 VS 가중치가 있는 그래프
   • 간선에 가중치가 없는 그래프 (Unweighted Graph)
     • 웹그래프
     • 페이스북 친구 그래프
   • 간선에 가중치가 있는 그래프 (Weighted Graph)
     • 전화 그래프
     • 유사도 그래프
3. 동종 그래프 VS 이종 그래프
   • 동종 그래프 (Unpartite Graph)
     • 단일 종류의 정점을 가진다.
       • 웹그래프
       • 페이스북 친구 그래프
   • 이종 그래프 (Bipartite Graph)
     • 두 종류의 정점을 가진다.
     • 다른 종류의 정점사이에만 간선이 연결된다.
       • 전자 상거래 구매내역 (구매자, 상품)
       • 영화 출연 그래프 (배우, 영화)

3.2 그래프 관련 필수 기초 개념

• 그래프틑 정점 집합과 간선 집합으로 이루어진 수학적 구조이다.
  • 정점들의 집합을 V, 간선들의 집합을 E, 그래프를 G = (V, E)로 표현한다.
• 정점의 이웃은 그 정점과 연결된 다른 정점을 의미한다.
  • 정점 v의 이웃들의 집합을 보통 N(v) 혹은 Nv로 표현한다.
• 방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분한다.
  • 정점 v에서 나가는 이웃의 집합을 보통 Nout(v)
  • 정점 v로 들어오는 이웃의 집합을 Nin(v)

4. 그래프의 표현 및 저장

4.1 파이썬 라이브러리 NetworkX

• NetworkX를 이용하여 그래프를 생성, 변경, 시각화할 수 있다.
• 이외에도 Snap.py역시 많이 사용되는 라이브러리이다.

4.2 그래프의 표현 및 저장

1. 간선리스트
   • 그래프를 간선들의 리스트로 저장
   • 각 간선은 해당 간선이 연결하는 두 정점들의 순서쌍으로 저장
   • 방향성 그래프의 경우 (출발점, 도착점)의 순서로 저장이 된다.
2. 인접리스트
   • 각 정점의 이웃들을 리스트로 저장
   • 방향성 그래프의 경우 나가는 이웃들과 들어오는 이웃들을 각각 리스트로 저장한다.
3. 인접 행렬
   • 정점수 * 정점수 크기의 행렬
   • 방향성이 없는 경우
     • 정점 i와 정점 j사이에 간선이 존재 : Aij = 1, Aji = 1
     • 정점 i와 정점 j사이에 간선이 없음 : Aij = 0, Aji = 0
   • 방향성이 있는 경우
     • 정점 i에서 나와서 정점 j로 도착하는 간선이 있을 때, Aij = 1
     • 없을 때 Aij = 0

2. 실제 그래프는 어떻게 생겼을까?

1. 실제 그래프 VS 랜덤 그래프

• 실제 그래프 : 다양한 복잡계로 부터 얻어진 그래프
  • 소셜 네트워크, 전자상거래 구매 내역, 인터넷, 웹, 뇌 등
  • MSN 메신저 그래프
    • 1억 8천만 정점 (사용자)
    • 13억 간선 (메세지를 주고 받은 관계)
• 랜덤 그래프 : 확률적 과정을 통해 생성한 그래프
  • 에르되스, 레니가 제안한 랜덤 그래프 모델
    • 임의의 두정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정된다.
    • 에르되스-레니 랜덤 그래프 G(n, p)
      • n개의 정점을 가진다.
      • 임의의 두개의 정점 사이에 간선이 존재할 확률은 p이다.
      • 정점 간의 연결은 서로 독립적이다.

2. 작은 세상 효과

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

경로

정점 u와 v의 사이의 경로는 아래조건을 만족하는 정점들의 순열이다.

• u에서 시작해서 v에서 끝나야한다.
• 순열에서 연속된 정점은 간선으로 연결되어 있어야한다.
• 경로의 길이는 해당 경로 상에 높이는 간선의 수로 정의된다.

거리 & 지름

1. 거리
   • 정점 u와 v의 사이의 거리는 u와 v사이의 최단 경로의 길이
2. 지름
   • 그래프의 지름은 정점 간 거리의 최댓값

2.2 작은 세상 효과

• problem
• 임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?
  • 여섯단계 분리 실험
  • 1960년대 사회학자 스탠리 밀그램에 의해 수행된 실험이다.
    1. 오마하와 위치타에서 500명의 사람을 뽑는다.
    2. 그들의 지인을 통하여 편지를 전달하게끔 하였다.
  • 결과
  • 25%의 편지만 도착했지만, 평균적으로 6단계만을 거쳤다.
  • 
  • 이와 비슷하게 MSN메신저에서 정점 간의 평균 거리는 7 정도 였다.
• 이러한 현상을 작은 세상 효과라고 부른다.

단, 체인, 사이클, 격자 그래프에서는 작은 세상 효과가 존재하지 않는다.

3. 연결성의 두터운 꼬리 분포

3.1 필수 개념 : 연결성

• 정점의 연결성은 그정검과 연결된 간선의 수를 의미한다.
• 정점 v의 연결성은 해당 정점의 이웃들의 수와 같다.
• 보통 정점 v의 연결성은 d(v), dv 혹은 |N(v)|로 적는다.
• 방향성이 있는 그래프의 경우
  • 나가는 연결성 : 그 정점에서 나가는 간선의 수
  • 들어오는 연결성 : 그 정점으로 들어오는 간선의 수

3.2 연결성의 두터운 꼬리 분포

• 실제 그래프의 연결성 분포는 두터운 꼬리를 가진다. 즉 연결성이 매우 높은 허브 정점이 존재한다.
• 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사하다.
  • 이 경우 연결성이 매우 높은 허브 정점이 존재할 가능성은 0에 가깝다.

4. 거대 연결 요소

4.1 필수 개념 : 연결 요소

연결 요소는 아래의 조건들을 만족하는 정점들의 집합을 의미한다.

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

4.2 거대 연결 요소

• 실제그래프에는 거대 연결 요소가 존재한다.
• 거대 연결 요소는 대다수의 정점을 포함한다.
• 단, 정점들의 평균 연결성이 1보다 충분히 커야한다. * 참고 : Random Graph Theory

5. 군집 구조

5.1 필수 개념 군집 구조 및 군집 계수

군집이란 아래의 조건들을 만족하는 정점들의 집합이다.

1. 집합에 속하는 정점 사이에는 많은 간선이 존재한다.
2. 집합에 속하는 정점과 그렇지 않은 정점사이에는 적은 수의 간선이 존재한다.

지역적 군집 계수 : 한 정점에서 군집의 형성 정도를 측정한다.

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

지역적 군집 계수가 군집이랑 어떻게 연결이 된는 걸까?
정점 i의 지역적 군집계수가 매우 높다고 하자. 즉, 정점 i의 이웃들도 높은 확률로 서로 간선으로 직접 연결되어 있다.
정점 i와 그 이웃들은 높은 확률로 군집을 형성한다.

전역 군집계수 : 전체그래프에서 군집의 형성 정도를 측정한다.
그래프 G의 전역 군집계수는 각 정점에서의 지역적 군집계수의 평균이다.

5.2 높은 군집 계수

실제 그래프에서는 군집 계수가 높다 –> 많은 군집이 존재한다.

• 동질성 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다.
• 전이성 공통이웃이 있는 경우, 공통이웃이 매개 역할을 해줄 수 있다.

랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않다.