[부스트캠프 AI Tech / Day21] 그래프 - 실제 그래프의 특성

[DAY 21] 실제 그래프의 구조적 효과

1. 작은 세상 효과
2. 연결성의 두터운-꼬리 분포
3. 거대 연결 요소
4. 군집 구조

실제 그래프 vs 랜덤 그래프

• 실제그래프(Real Graph): 다양한 복잡계로 부터 얻어진 그래프
  • 예시: 소셜 네트워크, 전자상거래 구매 내역, 인터넷, 웹, 뇌, 단백질 상호작용, 지식 그래프 등
  • (정점: 사용자, 간선: 주고받은 메시지)로 정의할 수 있다.
• 랜덤 그래프(Random Graph): 확률적 과정을 통해 생성한 그래프
  • 여기서는 가장 기초적인, 에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph) 사용

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

• 정의: 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정된다.
• 𝑛개의 정점을 가진다.
• 임의의 두 개의 정점 사이에 간선이 존재할 확률은 𝑝 이다.
• 정점 간의 연결은 서로 독립적(Independent)이다.

Q.𝑮 𝟑,𝟎.𝟑 에 의해 생성될 수 있는 그래프와 각각의 확률은?

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

• 필수 개념: 경로, 거리 및 지름
• 실제 그래프의 두 정점 사이의 거리는 작다.
• 적은 단계만 거치면, 많은 사람들과 연결될 수 있음을 의미한다.
• 실험: 여섯 단계 분리(Six Degrees of Separataion) 실험
• 속담: “사돈의 팔촌” - 아무리 먼 관계도 결국은 사돈의 팔촌(10촌 관계)

🔍 랜덤그래프에서의 작은 세상 효과?
작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재한다.
모든 사람이 100명의 지인이 있다고 가정해보면,
다섯 단계를 거치면 최대 100억(= 1005)명의 사람과 연결될 수 있다.
단, 실제로는 지인의 중복 때문에 100억 명보다는 적은 사람일 겁니다 하지만 여전히 많은 사람과 연결될 가능성이 높다.
체인(Chain), 사이클(Cycle), 격자(Grid) 그래프에서는 작은 세상 효과가 존재하지 않는다.

경로, 거리, 지름

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

ex) 경로 1, 3, 4, 6, 8의 길이는 4 경로 1, 4, 3, 4, 6, 8의 길이는 5 정점 1과 8 사이의 최단 경로(Shortest Path)는 1, 4, 6, 8 이고, 해당 경로의 길이는 3이다. 따라서 정점 1과 8 사이의 거리는 3이다. 예시 그래프에서의 지름은 4

연결성의 두터운 꼬리 분포

• 필수 개념: 연결성
• 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 가진다.
• 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재함을 의미한다.
• 연결성이 낮은 정점은 많으나, 연결성이 큰 노드의 수는 적다.

🔍 랜덤그래프는 연결성의 두터운 꼬리 분포를 따르지 않는다. 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사하다.
이 경우, 연결성이 매우 높은 허브(Hub) 정점이 존재할 가능성은 0에 가깝다.
정규 분포와 유사한 예시로는 키의 분포가 있다.
키가 10 미터를 넘는 극단적인 예외는 존재하지 않는다.
왜냐면 “키”는 정규분포와 유사한 그래프를 따르기 때문이다.

연결성

• 정점의 연결성(Degree)은 그 정점과 연결된 간선의 수(해당 정점의 이웃들의 수) 를 의미한다.

• 보통 정점 𝑣의 연결성은 𝒅(𝒗), 𝒅𝒗 혹은

  𝑵𝒗

  로 표시한다.

• 정점의 나가는 연결성(Out Degree)
  • 그 정점에서 나가는 간선의 수를 의미

  • 보통 정점 𝑣의 나가는 연결성은 𝒅𝒐𝒖𝒕(𝒗) 혹은

    𝑵𝒐𝒖𝒕 𝒗

    으로 표시한다.

• 정점의 들어오는 연결성(In Degree)
  • 그 정점으로 들어오는 간선의 수를 의미
  • 보통 정점 𝑣의 들어오는 연결성은 𝒅𝒊𝒏(𝒗) 혹은 |𝑵𝒊𝒏 𝒗|으로 표시한다.

거대 연결 요소(Giant Connected Component)

• 필수 개념: 연결 요소
• 거대 연결 요소는 대다수의 정점을 포함한다.
• 실제 그래프에서는 대다수의 정점을 포함하는 거대 연결 요소, 거대 그룹이 존재한다.

🔍 랜덤 그래프에도 높은 확률로 거대 연결 요소(Giant Connected Component)가 존재한다! 단, 정점들의 평균 연결성이 1보다 충분히 커야한다. 자세한 이유는 Random Graph Theory를 참고

연결 요소(Connected Component)

• 연결되어 있는 그룹은 하나의 연결 요소이다.
• 연결되지 않은 그룹은 다른 연결 요소이다.
• 원래는, 다음 조건들을 만족하는 정점들의 집합을 의미한다.
• 조건
  1. 연결 요소에 속하는 정점들은 경로로 연결될 수 있다.
  2. 1번의 조건을 만족하면서 정점을 추가할 수 없다.
• 예시
  • {1,2,3,4}는 조건 (2)를 위배한다.
  • {6,7,8,9}는 조건 (1)을 위배한다.

군집 구조

• 필수 개념: 군집, 군집 계수
• 실제 그래프에서 군집계수가 높은 이유 (많은 군집이 존재하는 이유)
  • 동질성(Homophily): 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다. 같은 동네에 사는 같은 나이의 아이들이 친구가 되는 경우가 그 예시이다.
  • 전이성(Transitivity): 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있다. 친구를 서로에게 소개해주는 경우가 그 예시이다.

군집(Community)

• 집합 내의 간선 수는 많고, 집합 밖의 간선의 수는 적은 경우
• 아래 조건들을 만족하는 정점들의 집합
  1. 집합에 속하는 정점 사이에는 많은 간선이 존재한다.
  2. 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재한다.

🔍 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않다.
구체적으로 랜덤 그래프 𝐺(𝑛, 𝑝)에서의 군집 계수는 𝑝이다.
랜덤 그래프에서의 간선 연결이 독립적인 것을 고려하면 당연한 결과이다.
즉, 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않는다.
전이성과 동질성을 만족하지 않으므로 군집을 생성할 확률이 적다고 할 수 있다.

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

• 한 정점에서 군집의 형성 정도를 측정
• 정점 𝑖의 지역적 군집 계수는 정점 𝑖의 이웃 쌍 중 간선으로 직접 연결된 것의 비율이다.
• 정점 𝑖의 지역적 군집 계수를 𝑪𝒊로 표현한다.
• 예시
  • 정점 1의 이웃: 2,3,4,5
  • 정점 1의 이웃쌍: (2,3),(2,4),(2,5),(3,4),(4,5),(3,5)
  • 정점 1의 이웃쌍 중, 직접 간선으로 연결된 것: (2,4),(2,3),(3,5)
  • 위의 그림은 이웃쌍 사이의 간선 수에 따른 지역적 군집계수의 변화를 보여준다.
• 참고로 연결성이 0인 정점에서는 지역적 군집 계수가 정의되지 않는다.

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

전역 군집 계수(Global Clustering Coefficient)

• 전체 그래프에서 군집의 형성 정도를 측정
• 그래프 𝐺의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균이다.
• 단, 지역적 군집 계수가 정의되지 않는 정점은 제외한다.

• 균일 그래프: 하나의 정점은 다른 정점과 어떠한 패턴으로 이루어져 있고, 이어져있는 다른 정점도 같은 패턴으로 연결되어있다.
• 작은 세상 그래프: 균일 그래프의 일부를 임의로 선택하여 몇몇 간선들을 일부 대체한다. 실제 그래프와 유사하다고 볼 수 있다.
• 랜덤 그래프

Abstract

• 실제 그래프 vs 랜덤 그래프: 실제 그래프는 복잡계로부터 얻어지는 반면, 랜덤 그래프는 확률적 과정을 통해 생성

• 실제그래프의 특성
  1. 작은 세상 효과: 실제 그래프의 정점들은 가깝게 연결되어 있음
  2. 연결성의 두터운 꼬리 분포: 실제 그래프에는 연결성이 매우 높은 허브 정점이 존재
  3. 거대 연결 요소: 실제 그래프에는 대부분의 정점을 포함하는 거대 연결 요소가 존재
  4. 군집 구조: 실제 그래프에는 군집이 존재하며, 실제 그래프는 군집 계수가 높음
• 랜덤그래프도 가지는 특성
  • 1. 작은 세상 효과
  • 1. 거대 연결 요소