Graph 01 - 그래프 기초와 패턴

본 정리 내용은 Naver BoostCamp AI Tech의 edwith에서 학습한 내용을 정리한 것입니다.
사실과 다른 부분이 있거나, 수정이 필요한 사항은 댓글로 남겨주세요.

Graph Basic

그래프(Graph)는 정점(Vertex) 집합과, 간선(Edge) 집합으로 이루어진 수학적 구조이다. 네트워크로도 불리며, 정점은 노드(Node)로, 간선은 링크(Link)로도 불린다.

우리 주위에 있는 복잡계(Complex System)가 가진 공통적인 특성은 구성요소간의 복잡한 상호작용이다. 그래프는 이 복잡계의 상호작용을 효과적으로 표현하고, 복잡계를 분석하기 위한 언어이다.

• 뇌, 지식 그래프, 화학 분자, 단백질 상호작용, 세포간 유사도 그래프, 이미지 분해...

그래프를 활용한 AI Task

정점 분류(Node Classification) 문제

• 트위터의 공유(Retweet) 관계를 분석하여 사용자의 정치적 성향 파악하기
• 단백질의 상호작용을 표현하여 단백질의 역할 알아내기

연결 예측(Linked Prediction) 문제

• 거시적 - 페이스북 소셜네트워크는 진화 방향 예측하기
• 미시적 : 추천문제 - 고객에게 필요한 물건을 추천하고, 어떤 물건을 구매했을 때 만족도가 높을지 예측하기

군집 분석(Community Detection) 문제

• 연결관계로부터 사회적 무리(Social Circle) 찾아내기

랭킹(Ranking) 및 정보 검색(Information Retrieval) 문제

• 웹(Web)을 그래프로 보고, 중요한(필요한) 웹페이지를 찾아내기

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

• 네트워크를 통한 정보전달을 최대화하기

그래프 관련 필수 기초 개념

유형 및 분류

• 방향의 유무에 따라
  • 방향이 없는 그래프(Undirected Graph)
    • 간선에 방향이 없음
    • ex) 협업관계 그래프, 페이스북 친구 그래프
  • 방향이 있는 그래프(Directed Graph)
    • 간선에 방향이 있음
    • ex) 인용 그래프, 트위터 팔로우 그래프
• 가중치의 유무에 따라
  • 가중치가 없는 그래프(Unweighted Graph)
    • 간선에 가중치가 없음
    • ex) 웹 그래프, 페이스북 친구 그래프
  • 가중치가 있는 그래프(Weighted Graph)
    • 간선에 가중치가 있음
    • ex) 전화(횟수) 그래프, 유사도 그래프
• 정점의 종류 개수에 따라
  • 동종 그래프(Unpartite Graph)
    • 단일 종류의 정점을 가짐
    • ex) 웹 그래프, 페이스북 친구 그래프
  • 이종 그래프(Bipartite Graph)
    • 두 종류의 정점을 가짐 - 다른 종류의 정점 사이에만 간선이 연결됨
    • ex) 전자 상거래 구매내역(사용자-상품), 영화 출연 그래프(배우-영화)

표현 방식

• 일반적으로 정점들의 집합을 $V$, 간선들의 집합을 $E$, 그래프를 $G = (V,E)$로 적는다.
• 이웃(Neighbor)는 해당 정점과 연결된 다른 정점을 의미한다. 정점 v의 이웃들의 집합을 $N(v)$ 혹은 $N_v$로 표시한다.
  • 방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분한다.
  • 나가는 이웃들의 집합을 $N_{out}(v)$, 들어오는 이웃들의 집합을 $N_{in}(v)$로 적는다.
• 간선 리스트(Edge List) - 그래프를 간선들의 리스트로 저장한다.
  • 간선은 해당 간선이 연결하는 두 정점들의 순서쌍(Pair)로 저장된다.
    • ex) (1,2), (5,7)
  • 방향성이 있는 간선의 경우 (출발점, 도착점) 순서로 저장된다.
• 인접 리스트(Adjacent List) - 각 정점들의 이웃들을 리스트로 저장한다.
  • 방향성이 없는 경우
    • ex) {1: 2,4,5 }
  • 방향성이 있는 경우
    • ex) 나가는 이웃 {1 : 2,4}, 들어오는 이웃 {1: 4, 2 : 1, 4 : 1}
• 인접 행렬(Adjacent Matrix) - 방향성이 없는 경우
  • 정점 수 X 정점 수 크기의 행렬
  • 방향성이 있는 경우
    • 정점 i와 j 사이에 간선이 있는 경우, 행렬 i행 j열(그리고 j행 i열)의 원소가 1, 그렇지 않으면 0
  • 방향성이 없는 경우
    • 정점 i에서 j로의 간선이 있는 경우, 행렬의 i행 j열 원소가 1, 그렇지 않으면 0

관련 라이브러리

NetworkX - 비교적 속도가 느리지만, 사용이 편리하다.

Snap.py - 비교적 속도가 빠르지만, 사용이 어렵다.

Graph Pattern

실제 그래프와 랜덤 그래프

실제 그래프

실제 그래프(Real Graph)란, 다양한 복잡계로부터 얻어진 그래프를 의미한다.

• 소셜 네트워크, 전자상거래 구매 내역, 인터넷 ,웹, 뇌 ...

랜덤 그래프

랜덤 그래프(Random Graph)란, 확률적 과정을 통해 생성한 그래프를 의미한다. 실제 그래프와 비교하기 위한 대상으로서 사용된다.

에르되스-레니 랜덤 그래프

• 가장 간단한 형태의 랜덤그래프로, 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률분포에 의해 결정된다.
• $G(n,p)$는
  • $n$개의 정점을 가진다.
  • 임의의 두 정점 사이에 간선이 존재할 확률은 $p$이다.
  • 정점 간의 연결은 서로 독립적(Independent)이다.

경로와 거리

개념

• 정점 $u$와 $v$ 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequence)이다.
  1. $u$에서 시작하여 $v$에서 끝난다.
  2. 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.
• 경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의된다.
• 정점 $u$와 $v$ 사이의 거리(Distance)는 $u$와 $v$ 사이 최단경로의 길이이다.
• 지름(Diameter)은 정점 간 거리의 최댓값이다.

작은 세상 효과

스탠리 밀그램의 여섯 단계 분리(Six Degrees of Separation) 실험

• 임의의 두 사람 간의 관계는 평균적으로 6단계로 표현되었다.

사람들이 서로 소수의 공통된 지인을 통해 연결되어 있다는 사실, 즉, 임의의 두 정점 사이의 거리가 작다는 사실을 작은 세상 효과(Small-world Effect)라고 부른다.

• 중복이 없다고 가정하였을 때, 모든 사람에게 100명의 지인이 있다면, 다섯 단계를 거치면 100억(=100^5)명까지도 연결될 수 있다.
• 물론 실제 세상에서는 중복이 있으므로 이보다 적을 것이다.

작은 세상 효과는 높은 확률로 랜덤그래프에도 존재하는데, 한 정점 당 이웃의 수가 늘어날수록, 적은 거리로도 연결되는 정점의 수가 기하급수적으로 증가하기 때문이다.

그렇다고 모든 그래프에서 작은 세상 효과가 존재하지는 않는다. 체인(Chain), 사이클(Cycle), 격자(Grid) 그래프에서는 작은 세상효과가 없다.

연결성

개념

정점의 연결성(Degree)는 그 정점과 연결된 간선의 수를 의미한다.

• 정점 $v$의 연결성은 해당 정점의 이웃들의 수와 같다.
• 보통 정점 $v$의 연결성을 $d(v)$, $d_v$, 혹은 $|N(v)|$로 적는다.
• 나가는 연결성은 $d_{out}(v)$, $|N_{out}(v)|$로 표시하며, 들어오는 연결성은 $d_{in}(v)$, $|N_{in}(v)|$로 표시한다.

두터운 꼬리 분포

실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 갖는다. 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재한다.

그러나, 랜덤 그래프의 연결성 분포는 높은 확률로 정규분포와 유사하다. 즉, 허브 정점이 존재할 가능성이 0에 가깝다.

연결 요소

개념

연결 요소(Connected Component)는 다음 조건들을 만족하는 정점들의 집합을 일컫는다.

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

쉽게 말하면, 뚝 뚝 떨어진 하나의 그래프 덩어리라고 볼 수 있다.

거대 연결 요소

실제 그래프에는 거대 연결 요소(Giant Connected Component)가 존재한다. 거대 연결 요소는 대다수의 정점을 포함한다.

• MSN 메신저에서는 99.9%의 정점이 하나의 거대 연결 요소에 포함된다.

랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재한다. 단, 정점들의 평균 연결성이 1보다 충분히 커야한다.

• 자세한 이유는 Random Graph Theory를 참고한다.

군집 구조

개념

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

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

• 수학적으로 엄밀한 정의는 아니다. '많다'와 '적다'의 정의가 모호하기 때문인 듯 하다.

지역적 군집 계수(Local Clustering Coefficient)는 한 정점에서 군집의 형성 정도를 측정한다.

• 정점 $i$의 지역적 군집 계수는 정점 $i$의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미하며, $C_i$로 표현한다.
• 즉, 정점 $i$와 연결된 이웃 정점들이, ($i$로 연결되는 간선을 제외하고) 서로 간선들로 많이 연결되어 있을 때 지역적 군집 계수가 높다.
• 반면, 정점 $i$만 허브로 존재하고, 나머지 정점들끼리는 연관관계가 없다면 지역적 군집계수가 낮을 것이다.
• 연결성이 0인 정점에서는 지역적 군집계수가 정의되지 않는다.

전역 군집 계수(Global Clustering Coefficient)는 전체 그래프에서 군집의 형성 정도를 측정한다.

• 그래프 $G$의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균이다.
  • 단, 지역적 군집계수가 정의되지 않는 정점은 제외한다.

높은 군집 계수

실제 그래프에서는 군집 계수가 높다. 즉, 많은 군집이 존재한다. 이유에는 여러가지가 있다.

• 동질성(Homophily) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다.
  • ex) 같은 동네에 사는 같은 나이의 아이들이 친구가 되는 경우
• 전이성(Transitivity) : 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있다.
  • ex) 친구를 서로에게 소개해 주는 경우

반면, 랜덤그래프에서는 지역적 혹은 전역 군집계수가 높지 않다. 랜덤그래프에서의 간선 연결이 독립적이기 때문이다.

• 랜덤그래프 $G(n,p)$에서의 군집 계수는 $p$이다.