Graph

What is Graph?

 

Graph는 Network라고도 불리며, 정점(Vertex=Node) 집합과 간선(Edge=Link) 집합으로 이루어진 수학적 구조다.

 

Graph

그래프는 복잡계를 표현하고 분석하기 위한 언어다.

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

 

통신 시스템, 70억 인구로 구성된 사회, 소셜네트워크, 뇌 뉴런 또한 모두 구성 요소 간의 복잡한 상호작용을 특성으로 가지는 복잡계다. 

복잡계는 그래프를 통해 효과적으로 표현과 분석이 가능하다.

 

그래프를 사용한 인공지능

• Node Classification(정점 분류): 트위터에서 공유관계를 분석하여 사용자의 정치적 성향을 알아낸다
• Link Prediction(연결 예측): 페이스북 같은 소셜네트워크의 확산 과정 예측
• Recommendation(추천): 소비자와 상품을 Vertex로 하고 구매행위를 Edge로 하는 그래프를 통해 상품 추천
• Community Detection(군집 분석): 연결 관계를 분석하여 사회적 무리(Social Circle) 찾아내기
• Ranking, Information Retrieval(랭킹, 정보검색): 웹이라는 거대한 그래프에서 중요한 웹페이지 찾아내기
• Information Cascading, Viral Marketing(정보 전파, 바이럴 마케팅): 정보 전달 최대화 방법 도출

 

군집 분석

 

Graph의 특성에 따른 분류

• Undirected Graph vs Directed Graph - 간선의 방향 유무
• Unweighted Graph vs Weighted Graph - 간선의 가중치 유무
• Unpartite Graph vs Bipartite Graph - 단일 종류의 정점, 두 종류의 정점 (i.e 소셜 네트워크 친구관계, 전자 상거래 구매내역)

Graph 관련 용어 및 개념

• 정점의 집합 V, 간선의 집합 E, 그래프 G = (V, E)
• Neighbor(이웃): 정점과 간선으로 연결된 다른 정점
• Path(경로): 정점 u에서 v까지 간선으로 연결된 순열
• Length(길이): 경로 상에 놓이는 간선의 수 (ex. 경로 1,4,6,8의 길이는 3)
• Distance(거리): 정점 u와 v사이의 최단 경로의 길이
• Diameter(지름): 정점 간 거리의 최댓값
• Degree(연결성): 정점과 연결된 간선의 수 == 정점의 Neighbor의 수 (Directed Graph의 경우 Out Degree, In Degree 2가지 종류의 Degree 존재)
• Connected Component(연결 요소): 경로로 연결될 수 있고 더 이상 정점을 추가할 수 없는 정점들의 집합
• Community(군집): 집합에 속하는 정점 사이에 많은 간선, 집합에 속하는 정점과 속하지 않는 정점 사이에는 적은 수의 간선 존재
• Local Clustering Coefficient(지역적 군집 계수): 한 정점에서 군집의 형성 정도
  • 정점의 지역적 군집 계수는 정점의 이웃 쌍 중 간선으로 직접 연결된 것의 비율
• Global Clustering Coefficient(전역 군집 계수): 전체 그래프에서 군집의 형성 정도 측정
  • 각 정점에서 지역적 군집 계수의 평균

 

연결 요소 예시

지역적 군집 계수 예시

 

Random Graph, Real Graph

실제 그래프는 다양한 복잡계에서 얻은 그래프로 예로 사용자를 Vertex로 메시지를 주고받은 관계를 Edge로 하는 MSN 메신저 그래프가 있다.

 

랜덤 그래프는 확률적 과정을 통해 생성한 그래프로 Erdős-Rényi RandomGraph (에르되스-레니 랜덤 그래프)가 이에 포함된다.

 

에르되스-레니 랜덤 그래프는 G(n, p)로 표기하며 n개의 정점을 가지고 임의의 2개의 정점 사이에 간선은 p의 확률로 존재하며 각 정점 간의 연결은 모두 독립적이다.

n=3, p=0.3 인 에르되스-레니 랜덤 그래프 G(3, 0.3)이 생성 가능한 그래프는 다음과 같다.

 

Erdős-Rényi RandomGraph

 

Small-World Network

작은 세상 효과는 인간관계에서 몇 단계만 거치면 서로 연결되어 있다는 것을 보인 이론이다.

 

Six Degree of Separation (여섯 단계 분리) 실험

• 스탠리 밀그램에 의해 1950년 수행
• 오마하와 위치타에서 500명의 사람 뽑아 지인을 통해 편지를 전달하여 보스턴에 있는 사람에게 편지 보내기 실험

Six Degree of Separation Experiment Result

25%의 편지가 도달하였고 평균 6단계를 거쳐 편지가 보내졌다.

이는 아무리 먼 관계라도 몇 개의 간선을 지나면 이어질 수 있다는 것을 보였다.

랜덤 그래프에서도 작은 세상 효과가 존재하는데 모든 사람이 100명의 지인 (100 Edge)를 가지고 있다고 하면 5단계를 거치면 100억 명의 사람과 연결이 가능하다.

중복을 제거하더라도 많은 수치다.

 

Heavy Tail

실제 그래프의 연결성 분포는 Heavy Tail을 갖는다.

이는 연결성(Degree)이 매우 높은 Hub 정점이 존재한다는 것을 말한다.

 

Heavy Tail

실제 그래프에서 예를 들면 소셜 네트워크의 Celeb은 그래프에서 Hub 정점으로 매우 많은 follower를 가지고 있다.

하지만 랜덤 그래프는 iid 한 간선의 생성으로 인해 연결성의 분포가 정규분포와 유사하며 따라서 Hub 정점, Heavy Tail이 나타나지 않는다.

 

Giant Connected Component

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

 

MSN Graph 거대 연결 요소

MSN 그래프에서 99.9%의 정점은 하나의 거대 연결 요소에 속하는 정점이다.

 

 

랜덤 그래프에서도 거대 연결 요소가 존재하지만 평균 연결성이 1보다 충분히 커야 한다는 제약 조건이 있다.

 

Random Graph 거대 연결 요소

 

Clustering Coefficient

실제 그래프에서는 많은 군집이 나타나 군집 계수가 높다.

서로 유사한 정점은 간선으로 연결될 가능성이 높은 동질성, 공통 이웃이 친구를 서로 소개해주듯이 매개 역할을 해주는 전이성에 의해 실제 그래프의 군집 계수는 높게 나타난다.

 

하지만 랜덤 그래프에서는 간선의 연결이 iid 한 확률 p로 생성되기 때문에 공통 이웃이 많고 적음이 p에 간선의 형성에 영향을 끼치지 않기 때문에 지역적, 전역적 군집 계수가 높지 않다.

 

 

Reference

[1] Naver Connect Boostcamp AI-Tech 그래프 이론 기초 (신기정 마스터)