[21] 그래프(Graph) 개념

1️⃣ 그래프(Graph)란?

 

그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조입니다.

 

하나의 간선은 두 개의 정점을 연결합니다.

모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아닙니다.

 

https://www.edwith.org/bcaitech1

 

• 그래프 (Graph) : 네트워크 (Network)
• 정점 (Vertex) : 노드 (Node)
• 간선 : 엣지 (Edge), 링크 (Link)

 

2️⃣ 그래프(Graph) 관련 인공지능 문제

 

• Node Classification(분류) 문제

트위터에서의 공유(Retweet) 관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있을까?

같은 정치적 성향을 가진 사람들끼리 공유(Retweet)를 많이 하는 것을 알 수 있습니다.

 

https://www.edwith.org/bcaitech1

 

단백질의 상호작용을 분석하여 단백질의 역할을 알아낼 수 있을까?

단백질들의 상호작용을 그래프로 분석하여 단백질이 어떤 일을 하는지 알 수 있습니다.

 

https://www.edwith.org/bcaitech1

 

• Link Prediction (연결 예측) 문제

페이스북 소셜 네트워크는 어떻게 진화할까?

이 소셜 네트워크(그래프)가 어떻게 성장할지를 예측하는 문제입니다.

 

https://www.edwith.org/bcaitech1

 

• Recommendation(추천) 문제

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

 

https://www.edwith.org/bcaitech1

 

• Community Detection(군집 분석) 문제

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

Clustering 문제, node들의 집합인 군집을 찾아내는 문제입니다. 이러한 군집들은 어떠한 의미를 가지는 경우가 많습니다.

 

https://www.edwith.org/bcaitech1

 

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

 

웹(Web)이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?

 

https://www.edwith.org/bcaitech1

 

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

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

 

https://www.edwith.org/bcaitech1

 

 

3️⃣ 그래프 유형 및 분류

1) 방향이 없는 그래프(Undirected Graph) vs 방향이 있는 그래프(Directed Graph)

 

https://www.edwith.org/bcaitech1

 

 

2) 가중치가 없는 그래프(Unweighted Graph) vs 가중치가 있는 그래프(Weighted Graph)

 

(전화 그래프 : 전화를 많이 할수록 친밀도가 높다고 봄)

 

https://www.edwith.org/bcaitech1

 

 

3) 동종 그래프(Unpartite Graph) vs 이종 그래프(Bipartite Graph)

 

(전자 상거래 구매내역 : 사용자끼리 간선이 연결될 수 없고, 상품끼리 간선이 연결될 수 없음)

 

https://www.edwith.org/bcaitech1

 

4) 예시

 

다음 전자 상거래 구매 내역은 어떤 유형의 그래프일까요?

 

https://www.edwith.org/bcaitech1

 

정답은 방향성이 없고, 가중치가 있는 이종 그래프입니다

여기서 방향성이 있는 그래프로 표현해도 되지만 방향성이 없는 그래프로 표현하는 이유는 복잡도가 늘어나고, 방향성을 생성한 것에 비해 얻는 정보가 없기 때문입니다.

 

 

4️⃣ 그래프 필수 기초 개념

1) 그래프 표현

 

보통 정점들의 집합을 𝑽, 간선들의 집합을 𝑬, 그래프를 𝑮 = (𝑽, 𝑬)로 적습니다.

 

https://www.edwith.org/bcaitech1

 

2) 이웃 (Neighbor)

 

정점의 이웃(Neighbor)은 그 정점과 연결된 다른 정점을 의미합니다.

정점 𝑣의 이웃들의 집합을 보통 𝑵(𝒗) 혹은 $𝑵_{𝒗}$로 적습니다

 

https://www.edwith.org/bcaitech1

 

방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분합니다.

정점 𝑣에서 간선이 나가는 이웃(Out-Neighbor)의 집합을 보통 $𝑵_{out}(𝒗)$로 적습니다.

정점 𝑣로 간선이 들어오는 이웃(In-Neighbor)의 집합을 보통 $𝑵_{in}(𝒗)$로 적습니다.

 

https://www.edwith.org/bcaitech1

 

 

5️⃣ 실제 그래프 vs 랜덤 그래프

 

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

(소셜 네트워크, 전자상거래 구매 내역, 인터넷, 웹, 뇌, 단백질 상호작용, 지식 그래프 등)

 

랜덤 그래프(Random Graph)는 확률적 과정을 통해 생성한 그래프를 의미합니다.

대표적으로 에르되스(Erdős)와 레니(Rényi)가 제안한 랜덤 그래프 모델을 사용합니다.

---

✅ 에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph)

 

임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됩니다.

 

에르되스-레니 랜덤그래프 𝐺(𝑛, 𝑝)는

✓ 𝑛개의 정점을 가집니다.

✓ 임의의 두 개의 정점 사이에 간선이 존재할 확률은 𝑝입니다.

✓ 정점 간의 연결은 서로 독립적(Independent)입니다.

 

예시로 𝑮(𝟑, 𝟎.𝟑)에 의해 생성될 수 있는 그래프와 각각의 확률은?

 

https://www.edwith.org/bcaitech1

---

6️⃣ 작은 세상 효과(Small-world Effect)

1) 경로(Path)

 

정점 𝑢와 𝑣의 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequence)입니다

 

(1) 𝑢에서 시작해서 𝑣에서 끝나야 합니다.

(2) 순열에서 연속된 정점은 간선으로 연결되어 있어야 합니다.

 

다음은 경로(path)가 맞습니다.

 

https://www.edwith.org/bcaitech1

 

다음은 경로(path)가 맞지 않습니다.

 

https://www.edwith.org/bcaitech1

 

경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의됩니다.

 

경로 1, 4, 6, 8의 길이는 3 입니다.

경로 1, 3, 4, 6, 8의 길이는 4 입니다.

경로 1, 4, 3, 4, 6, 8의 길이는 5 입니다.

https://www.edwith.org/bcaitech1

 

2) 거리(Distance)

 

정점 𝑢와 𝑣의 사이의 거리(Distance)는 𝑢와 𝑣 사이의 최단 경로의 길이입니다.

 

https://www.edwith.org/bcaitech1

 

3) 지름(Diameter)

 

그래프의 지름(Diameter)은 정점 간 거리의 최댓값입니다.

 

 

4) 작은 세상 효과(Small-world Effect)

 

 

• 여섯 단계 분리 (Six Degrees of Separataion) 실험

오마하와 위치타 주에서 보스턴으로 "지인을 통해서만" 편지를 보낼 때 몇 단계를 거치게 되는지?

 

https://www.edwith.org/bcaitech1

평균적으로 6단계 만을 거쳤습니다.

 

https://www.edwith.org/bcaitech1

 

이렇게 사람들이 소수의 공통된 지인을 통해 세상이 연결되어 있다는 사실을 알 수 있습니다.

그래프 이론으로 일반화시키면, 실제 그래프의 멀리 떨어져 있는 두 정점의 거리가 간선을 통하면 매우 작아진다는 사실을 알 수 있습니다.

이러한 현상을 작은 세상 효과(Small-world Effect)라고 부릅니다.

 

하지만 모든 그래프에서 작은 세상 효과가 존재하는 것은 아닙니다.

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

 

https://www.edwith.org/bcaitech1

 

7️⃣ 연결성(Degree)

1) 연결성(Degree)

 

정점의 연결성(Degree)은 그 정점과 연결된 간선의 수를 의미합니다.

 

정점 𝑣의 연결성은 해당 정점의 이웃들의 수와 같습니다.

보통 정점 𝑣의 연결성은 $𝒅(𝒗)$ , $𝒅_{𝒗}$ 혹은 $| 𝑵(𝒗) |$ 로 적습니다.

 

https://www.edwith.org/bcaitech1

 

정점의 나가는 연결성(Out Degree)은 그 정점에서 나가는 간선의 수를 의미합니다.

보통 정점 𝑣의 나가는 연결성은 $𝒅_{out}(𝒗)$ 혹은 $|𝑵_{out} (𝒗) |$으로 표시합니다.

 

정점의 들어오는 연결성(Out Degree)은 그 정점에서 들어오는 간선의 수를 의미합니다.

보통 정점 𝑣의 들어오는 연결성은 $𝒅_{in}(𝒗)$ 혹은 $|𝑵_{in} (𝒗) |$으로 표시합니다.

 

https://www.edwith.org/bcaitech1

 

2) 실제 그래프 vs 랜덤 그래프 연결성

 

실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 갖습니다.

즉, 연결성이 매우 높은 허브(Hub) 정점이 존재함을 의미합니다. (정규분포가 아니라서 극단적인 차이가 발생)

 

랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사합니다.

연결성이 매우 높은 허브(Hub) 정점이 존재할 가능성은 0에 가깝습니다.

 

https://www.edwith.org/bcaitech1

 

 

8️⃣ 거대 연결 요소(Giant Connected Component)

1) 거대 연결 요소(Giant Connected Component)

 

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

 

(1) 연결 요소에 속하는 정점들은 경로로 연결될 수 있습니다.

(2) "(1)의 조건"을 만족하면서 정점을 추가할 수 없습니다.

 

https://www.edwith.org/bcaitech1

다음과 같은 경우는 연결 요소(Connected Component)가 아닙니다.

 

- {1,2,3,4}는 조건 (2)를 위배합니다. ({1,2,3,4}는 5번을 추가할 수 있기 때문에 조건(2)에 위배)

- {6,7,8,9}는 조건 (1)을 위배합니다.

 

 

2) 실제 그래프 vs 랜덤 그래프 거대 연결 요소

 

실제 그래프에는 거대 연결 요소(Giant Connected Component)가 존재합니다.

거대 연결 요소는 대다수의 정점을 포함합니다.

 

https://www.edwith.org/bcaitech1

 

랜덤 그래프에도 높은 확률로 거대 연결 요소(Giant Connected Component)가 존재합니다.

단, 정점들의 평균 연결성이 1보다 충분히 커야 합니다.

(거대 연결 요소는 1 이상일 때만 생기게 됩니다. 3 정도가 되었을 때 거대 연결 요소가 대부분의 정점을 포함하는 것을 알 수 있습니다; Random Graph Theory)

 

https://www.edwith.org/bcaitech1

 

9️⃣ 군집(Community)

1) 군집(Community)

 

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

 

(1) 집합에 속하는 정점 사이에는 많은 간선이 존재합니다.

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

 

아래 예시 그래프에는 11 개의 군집이 있는 것으로 보입니다.

 

https://www.edwith.org/bcaitech1

 

 

2) 지역적 군집 계수(Local Clustering Coefficient)

 

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

 

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

정점 𝑖의 지역적 군집 계수를 $𝑪_{𝒊}$로 표현합시다

 

아래 예시 그래프를 살펴봅시다.

정점 1의 이웃은 4개 (2, 3, 4, 5)이며, 총 6개의 이웃 쌍 ( (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (3, 5) )이 존재합니다.

그중 3개의 쌍이 간선으로 직접 연결되어 있습니다.

따라서, $C_{1} = \frac {3} {6} = 0.5$ 입니다.

이웃 쌍 사이의 간선 개수가 늘어나면 지역적 군집 계수가 증가하고, 이웃 쌍 사이의 간선 개수가 줄어들면 지역적 군집 계수가 감소합니다.

 

 

다만, 연결성이 0인 정점에서는 지역적 군집 계수가 정의되지 않습니다.

 

즉, 지역적 군집 계수가 매우 높으면, 정점 𝑖의 이웃들도 높은 확률로 서로 간선으로 연결되어있다는 뜻이며, 정점 𝑖와 그 이웃들은 높은 확률로 군집을 형성합니다.

 

 

3) 전역 군집 계수(Global Clustering Coefficient)

 

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

 

그래프 𝐺의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균입니다.

단, 지역적 군집 계수가 정의되지 않는 정점은 제외합니다.

 

 

4) 실제 그래프 vs 랜덤 그래프 높은 군집 계수

 

실제 그래프에서는 군집 계수가 높습니다. 즉 많은 군집이 존재합니다.

 

이유는 다음과 같습니다.

 

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

 

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

 

랜덤 그래프에서의 간선 연결이 독립적인 것을 고려하면, 랜덤그래프에서는 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않기 때문에 동질성/전이성이 없습니다. 따라서 군집을 만들 확률이 낮습니다.