[Week 5-1] 🔗그래프 이론 기초

5주차 월요일

• 그래프 이론
• 그래프의 표현
• 실제 그래프와 랜덤 그래프

📝[그래프 이론]

• 그래프 : 정점들의 집합과 간선들의 집합으로 이루어진 수학적 구조.
  정점을 vertex 또는 node, 간선을 edge 또는 link, 그래프를 네트워크라고 부르기도 한다.

• 복잡계(complex system)
  사회, 통신시스템, 정보, 지식, 뇌 등 구성요소 간에 복잡한 상호작용이 발생하는 시스템을 말한다. 그래프를 이용하면 상호작용에 대한 표현을 쉽게 할 수 있어서 다양한 분야의 복잡계를 효과적로 분석할 수 있다.

• 그래프의 유형 및 분류

  • 방향이 없는 그래프 : 두 정점의 연결 관계가 동등한 그래프. 협업 관계, 페이스북 친구
  • 방향이 있는 그래프 : 두 정점의 연결 관계가 동등하지 않은 그래프. 논문 인용, 트위터 팔로우
  • 간선에 가중치가 없는 그래프 : 웹 페이지 연결, 페이스북 친구 그래프
  • 간선에 가중치가 있는 그래프 : 통화 횟수에 따른 친밀도 그래프, 유사도 그래프
  • 동종 그래프 : 단일 종류의 정점을 갖는 그래프
  • 이종 그래프 : 두 종류의 정점을 가지며 다른 종류의 정점 사이에만 간선이 연결된 그래프. 사용자/상품 그래프, 배우/영화 그래프

  이들 그래프는 방향성이 없고 가중치가 있는 이종 그래프와 같이 여러 유형이 중복될 수도 있다.

---

[그래프 관련 인공지능 문제]

• 정점 분류 문제
  트위터의 공유(리트윗) 관계를 분석하여 각 사용자의 정치적 성향을 예측하는 문제.
  이 때 사용자가 정점, 특정 성향 사용자의 글을 리트윗한 것이 간선이 된다.

• 연결 예측 문제
  거시적 범위 : 페이스북 소셜 네트워크는 어떻게 진화할까? 지금 상태에서 발전할지 쇠퇴할지 예측
  미시적 범위 : 추천 시스템. 사용자가 어떤 물건을 필요로 할지, 어떤 물건을 구매하면 만족할지 예측

• 군집 분석 문제
  정점들의 군집(밀접하게 연결된 집합)을 찾는 문제. 예를 들면 sns에서 고등학교 동창 집합, 회사 동기 집합, 가족 등을 찾는 것 등이 있다.

• 랭킹 및 정보 검색 문제
  웹을 거대한 그래프로 보고, 웹 안에서 웹 페이지들의 연결을 분석해 중요하고 관련성 높은 페이지를 찾는 문제.

• 정보 전파 및 바이럴 마케팅 문제
  소셜 미디어 등을 이용해서 정보를 더 많은 정점에 퍼뜨리도록 하는 문제.

---

[그래프의 표현 및 저장]

정점의 집합을 V, 간선의 집합을 E, 그래프를 G=(V,E)와 같이 표현한다. 한 정점에 연결된 다른 정점(이웃)의 집합을 N(v) 또는 N_v로 표현한다.
방향이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분하는데, 나가는 이웃의 집합은 N_out(v), 들어오는 이웃의 집합은 N_in(v)와 같이 표현한다.

그래프를 저장하는 방법은 간선 리스트, 인접 리스트, 인접 행렬 등이 있다.

• 간선 리스트 : 그래프를 간선들의 리스트로 저장한다. 각 정점을 연결하는 간선이 순서쌍 형태로 저장된다. 그래프를 단순하게 표현할 수 있지만, 특정 정점에 연결된 정점을 확인하려면 리스트를 처음부터 끝까지 살펴봐야 한다.
  (예시그림)

• 인접 리스트 : 각 정점에 연결된 이웃들을 리스트로 저장한다. 방향이 있는 그래프일 경우 들어오는 이웃과 나가는 이웃을 별도의 리스트에 저장한다. 그래프를 단순하게 표현하기는 어렵지만 특정 정점에 연결된 정점을 확인할 때 편리하다.
  (예시그림)

• 인접 행렬 : 정점 수x정점 수 크기의 행렬 A를 만들어 정점 i와 j 사이에 간선이 있을 경우 A(i,j)와 A(j,i)의 원소를 1로 저장한다. 간선이 없을 경우 해당 위치의 원소는 0이 된다. 이와 같은 저장 방식 때문에 이 행렬 A는 대칭행렬이 된다. 저장공간을 많이 먹는다.
  (예시그림)

---

[실제 그래프의 패턴]

정규분포를 따르도록 확률적으로 만든 랜덤 그래프와 실제 그래프를 비교하기 위해 실제 그래프의 예시로 1억 8천만 개의 정점(사용자)과 13억 간선(메시지를 주고받은 관계)을 가진 MSN 메신저 그래프를, 랜덤 그래프의 예시로 수학자 에르되스와 레니가 제안한 랜덤 그래프를 사용한다.

에르되스-레니 랜덤 그래프 G(n,p)

• n개의 정점을 가진다.
• 임의의 두 정점 사이에 간선이 존재할 확률은 p이다.
• 정점 간의 연결은 서로 독립적이다(어떤 정점 간의 연결 관계가 다른 정점 간의 연결 관계에 영향을 주지 않음).

• 그래프 내의 경로 : 정점 u와 v 사이의 경로는 아래 조건을 만족하는 정점들을 순열로 나타낸 것이다.

1. u에서 시작해서 v에서 끝나야 한다.
2. 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.
   (예시 그림)

• 경로의 길이 : 해당 경로 상에 놓이는 간선의 수
  (예시 그림)

• 두 정점 사이의 거리
  정점 u와 v 사이의 거리는 두 정점 간의 최단경로의 길이다.

• 그래프의 지름
  정점 간 거리의 최대값
  아무 정점에서나 제일 멀리 있는 정점을 구하고 거기서 제일 멀리 있는 정점까지의 거리가 그래프의 지름이다.

• 여섯 단계 분리(Six Degrees of Seperation) 실험
  1960년대에 사회학자 스탠리 밀그램에 의해 수행된 실험으로, 오마하와 위치타에서 500명을 뽑아 보스턴(굉장히 멀다)에 있는 사람에게 오직 지인을 통해서만 편지를 전달하게 했다. 편지의 25%만 돌아왔으나 편지들은 평균적으로 6단계를 거쳐서 전달되었다.

이와 같이 그래프에서 임의의 두 정점 사이의 최단거리가 의외로 작은 현상을 작은 세상 효과(Small-World effect)라고 부른다. 이는 랜덤 그래프에서도 일어나는 현상이다. 예외적으로 체인, 사이클, 격자 그래프에서는 그 형태 때문에 작은 세상 효과가 존재하지 않는다.
(예시 그림)

---

[연결성과 두터운 꼬리 분포]

• 정점의 연결성(Degree)
  어떤 정점 v의 연결성은 해당 정점의 이웃 수와 같다. d(v), d_v, |N(v)| 등으로 표현한다.
  방향이 있는 그래프에서는 들어오는 연결성과 나가는 연결성을 구분해서 세며 d_in(v), d_out(v) 등으로 표현한다.

• 실제 그래프의 연결성 분포
  실제 그래프의 연결성 분포를 살펴보면 정규분포 형태가 아니라 두터운 꼬리(Heavy Tail) 형태를 갖는데, 연결성이 매우 높은 허브 정점이 존재함을 의미한다.
  (예시 그림) * 두터운 꼬리 : 꼬리가 얇아 보이는데 사실 저 정도면 두꺼운 것이다. 정규분포를 보면 꼬리가 거의 없어서 보이지도 않는다.

• 랜덤 그래프의 연결성 분포
  랜덤 그래프의 연결성 분포는 높은 확률로 정규분포 형태와 유사하다. 확률적으로 생성되는 그래프라 연결성이 매우 높은 허브 정점이 존재할 가능성이 0에 가깝다.
  (예시 그림)

• 연결 요소

1. 연결 요소에 속하는 모든 정점들은 경로를 통해 연결된다.
2. 다른 연결 요소에 속하는 정점들과는 연결되지 않는다.
   (예시 그림)
   실제 그래프에는 대다수의 정점을 포함하는 거대 연결 요소라는 것이 존재한다. MSN 메신저 그래프에서는 99.9%의 정점이 하나의 거대 연결 요소에 포함되어 있다.
   
   랜덤 그래프에서도 높은 확률로 거대 연결 요소가 존재하는데, 거대 연결 요소가 존재하려면 정점들의 평균 연결성이 1보다 충분히 커야 한다.

• 군집

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

• 지역적 군집 계수 : 한 정점에서 군집의 형성 정도를 측정
  어떤 정점 i의 지역적 군집 계수는 정점 i의 이웃으로 만들 수 있는 pair 중 서로가 간선으로 직접 연결된 것의 비율이다. 연결성이 0인 정점은 분모가 0이 되므로 지역적 군집 계수를 정의할 수 없다. (예시 그림)
  어떤 정점 i의 지역적 군집 계수가 매우 높다면 정점 i의 이웃들도 높은 확률로 서로 연결되어 있고, 정점 i와 그 이웃들은 높은 확률로 군집을 형성하게 된다.

• 전역 군집 계수 : 전체 그래프에서 군집의 형성 정도를 측정
  그래프 G의 전역 군집 계수란 연결성이 0인 정점을 제외한 각 정점에서의 지역적 군집 계수의 평균이다.

실제 그래프는 군집 계수가 높다. 서로 유사한 정점끼리 연결될 가능성이 높고(동질성), 공통 이웃이 매개 역할을 해 두 정점을 연결할 수 있기 때문(전이성)인데, 랜덤 그래프에서는 간선 연결이 서로 독립적이기 때문에 군집 계수가 낮다.