실제 그래프는 어떻게 생겼을까?¶
✅ 실제 그래프 vs 랜덤 그래프¶
- 실제 그래프는 MSN 메신저 그래프 사용
- 랜덤 그래프는 확률적 과정을 통해 생성한 그래프, 에르되스와 레니가 제안한 랜덤 그래프 모델 사용
🔎 에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph)¶
임의의 두 정점 사이에 간선이 존재하는지 여부는 도일한 확률 분포에 의해 결정된다.
에르되스-레니 랜덤그래프$G(n,p)$는
- 𝑛개의 정점을 가진다.
- 임의의 두 개의 정점 사이에 간선이 존재할 확률은 𝑝이다.
- 정점 간의 연결은 서로 독립적(Independent)이다.
📌 예시
Q. G(3,0.3)에 의해 생성될 수 있는 그래프와 각각의 확률은?
✅ 작은 세상 효과¶
1️⃣ 경로, 거리 및 지름¶
📌 두 점정 𝑢와 𝑣의 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequence)이다.¶
- $u$에서 시작해서 $v$에서 끝나야한다.
- 순열에서 연속된 정점은 간선으로 연결되어 있어야한다.
📌 경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의된다.¶
📌 정점 $u$와 $v$의 사이의 거리(Distance)는 $u$와 $v$사이의 최단 경로의 길이이다.¶
📌 그래프의 지름(Diameter)은 정점 간 거리의 최댓값이다.¶
2️⃣ 작은 세상 효과¶
📌 임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?¶
여섯단계분리(Six Degrees of Separataion)실험
- 사회학자 스탠리 밀그램(Stanley Milgram)에 의해 1960년대에 수행된 실험
- 오마하 (네브라스카주)와 위치타 (켄사스주)에서 500명의 사람을 뽑았다.
- 그들에게 보스턴에 있는 한 사람에게 편지를 전달하게끔 하였다.
- 단,지인를 통해서만 전달하게끔 하였다.
25%의 편지만 도착했지만, 평균적으로 6단계만을 거쳤다.¶
MSN 메신저 그래프에서도 거의 정점 간의 평균 거리는 7정도 밖에 되지 않는다.¶
이러한 현상을 작은 세상 효과(small-world Effect)라고 부른다.¶
- 작은 세상 효과는 높은 확률로 랜덤 그래프에 존재.
- 하지만 모든 그래프에서 작은 세상 효과가 존재하는 것은 아니다.
- 체인(chain), 사이클(cycle), 격자(grid) 그래프에서는 작은 세상 효과가 존재하지 않음
✅ 연경성의 두터운 꼬리 분포¶
1️⃣ 연결성¶
📌정점의 연결성(Degree)은 그 정점과 연결된 간선의 수를 의미한다.¶
- 정점 $v$의 연결성은 해당 정점의 이웃들의 수와 같다. 보통 정점 $v$의 연결성은 $d(v), d_{v}$혹은 $|N(v)|$로 적는다.
📌 정점의 나가는 연결성(Out Degree)은 그 정점에서 나가는 간선의 수를 의미¶
- 보통 정점 $v$의 나가는 연결성은 $d_{out}(v)$ 혹은 $|N_{out}(v)|$으로 표시
📌 정점의 들어오는 연결성(Out Degree)은 그 정점에서 들어오는 간선의 수를 의미¶
- 보통 정점 $v$의 들어오는 연결성은 $d_{in}(v)$ 혹은 $|N_{in}(v)|$으로 표시
2️⃣ 연결성의 두터운 꼬리 분포¶
📌 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 갖는다.¶
- 즉 연결성이 매우 높은 허브(Hub) 정점이 존재함을 의미
📌 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사하다.¶
- 이 경우, 연결성이 매우 높은 허브(Hub) 정점이 존재할 가능성은 0에 가깝다.
정규 분포와 유사한 예시로는 키의 분포가 있다. 키가 10미터를 넘는 극단적인 예외는 존재하지 않는다.
비교¶
✅ 거대 연결 요소¶
1️⃣ 연결 요소¶
📌 연결 요소(Connected Component)는 다음 조건들을 만족하는 정점들의 집합을 의미¶
- 연결 요소에 속하는 정점들은 경로로 연결될 수 있다.
- 위 조건을 만족하면서 정점을 추가할 수 없다.
- 여기서 {1,2,3,4}의 경우는 그 집합에서 5을 추가 하더라도 1의 조건을 만족하면서 5라는 새로운 정점을 추가 할 수 있기때문에 2번째 조건에 위배 된다.
2️⃣ 거대 연결 요소¶
📌 실제 그래프에는 거대 연결 요소(Giant Connected Component)가 존재한다. 거대 연결 요소는 대다수의 정점을 포함한다.¶
MSN 메신저 그래프에는 99.9%의 정점이 하나의 거대 연결 요소에 포함된다.
📌 랜덤 그래프에도 높은 확률로 거대 연결 요소(Giant Connected Component)가 존재한다.¶
단, 정점들의 평균 연결성이 1보다 충분히 커야한다. 자세한 이유는 Random Graph Theory를 참고
✅ 군집 구조¶
1️⃣ 군집¶
📌 군집(Community)이란 다음 조건들을 만족하는 정점들의 집합¶
- 집합에 속하는 정점 사이에는 많은 간선이 존재한다.
- 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재한다.
수학저으로 엄밀한 정의는 아니다. 예시 그래프에는 11개의 군집이 있는 것으로 보인다.
📌 지역적 군집 계수(Local Clustering Coefficient)는 한 정점에서 군집의 형성 정도를 측정¶
- 정점 𝑖의 지역적 군집 계수는 정점 𝑖의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미한다.
- 정점 𝑖의 지역적 군집 계수를 $C_{i}$로 표현한다.
예시 그래프를 살펴보자.
정점 1의 이웃은 4개이며, 총 6개의 이웃 쌍((2,3),(2,4),(2,5),(3,4),(3,5),(4,5))이 존재한다. 그 중 3개의 쌍이 간선으로 직접 연결 되어 씨다. 따라서, $C_{i} = {3 \over 6} = 0.5$
참고로 연결성이 0인 정점에서는 지역적 군집 계수가 정의되지 않는다.
📌 지역적 군집 계수가 군집이랑 어떻게 연결되는가?¶
- 정점 $i$의 지역적 군집 계수가 매우 높다고 가정하자
- 즉, 정점 $i$의 이웃들도 높은 확률로 서로 간선으로 연결되어 있다.
- 정점 $i$와 그 이웃들은 높은 확률로 군집을 형성한다.
📌 전역 군집 계수(Global Clustering Coefficient)는 전체 그래프에서 군집의 형성 정도를 측정한다.¶
- 그래프 $G$의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균이다.
- 단, 지역적 군집 계수가 정의되지 않는 정점은 제외
📌 실제 그래프에서는 군집 계수가 높으면 많은 군집이 존재한다.¶
동질성(Homophily)
- 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다. 같은 동네에 사는 같은 나이의 아이들이 친구가 되는 경우가 그 예시
전이성(Transitivity)
- 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있다. 친구를 서로에게 소개해주는 경우가 그 예시
📌 반면 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않다.¶
- 구체적으로 랜덤 그래프 $G(n,p)$에서의 군집 계수는 $p$이다.
- 랜덤 그래프에서는 간선 연결이 독립적인 것을 고려하면 당연한 결과
- 즉, 공통 이웃의 존재 연부가 간선 연결 확률에 영향을 미치지 않는다.
✅ 군집 계수 및 지름 분석¶
In [1]:
# 실습에 필요한 library를 import하고 그래프를 초기화합니다.
import networkx as nx
import os
import os.path as osp
import numpy as np
import sys
import matplotlib.pyplot as plt
import collections
np.set_printoptions(threshold=sys.maxsize)
cycle_graph = nx.Graph()
regular_graph = nx.Graph()
small_world_graph = nx.Graph()
random_graph = nx.Graph()
각 그래프의 데이터를 읽어 오자¶
In [2]:
# 데이터를 읽어옵니다.
print("###### Read Graphs ######")
f = open('../실습코드/data/lab/lab2/cycle.txt')
for line in f:
v1, v2 = map(int, line.split())
cycle_graph.add_edge(v1, v2)
f = open('../실습코드/data/lab/lab2/regular.txt')
for line in f:
v1, v2 = map(int, line.split())
regular_graph.add_edge(v1, v2)
f = open('../실습코드/data/lab/lab2/small_world.txt')
for line in f:
v1, v2, = map(int, line.split())
small_world_graph.add_edge(v1, v2)
f = open('../실습코드/data/lab/lab2/random.txt')
for line in f:
v1, v2 = map(int, line.split())
random_graph.add_edge(v1, v2)
주어진 그래프의 전역 군집 계수를 계산하는 함수 정의¶
In [3]:
# 그래프의 전역 군집 계수를 찾는 함수입니다.
#
# 특정 정점 u의 정점 계수(cc)는 아래와 같이 구할 수 있습니다.
# cc(u) = 2T(u)/(deg(u) * (deg(u) - 1))
# - cc(u) : 정점 u의 군집계수
# - T(u) : 정점 u가 들어있는 삼각형 개수
# - deg(u): 정점 u의 차수 (degree)
#
# 그리고 전역 군집 계수는 모든 node의 cc(u)의 평균을 의미합니다.
# 전역 군집 계수
# avg_cc(G) = sigma(u in G) cc(u) / n
# - avg_cc(G) : 그래프 G의 전역 군집 계수
# - n : 그래프 G의 정점 개수
#
def getGraphAverageClusteringCoefficient(Graph):
ccs = []
for v in Graph.nodes:
num_connected_pairs = 0
for neighbor1 in Graph.neighbors(v):
for neighbor2 in Graph.neighbors(v):
if neighbor1 <= neighbor2:
continue
if Graph.has_edge(neighbor1, neighbor2):
num_connected_pairs = num_connected_pairs + 1
cc = num_connected_pairs / (Graph.degree(v) * (Graph.degree(v) - 1) / 2)
ccs.append(cc)
return sum(ccs) / len(ccs)
주어진 그래프의 지름을 계산하는 함수를 정의¶
In [4]:
# 본 실습에서는 그래프의 다양한 특성 중 그래프 지름과 전역 군집 계수를 분석해봅니다.
# 그래프에서 Diameter, Average Clustering Coefficient를 찾는 알고리즘을 구현하고, networkx에서 제공하는 라이브러리와 결과를 비교해봅시다.
# 그래프의 지름을 찾는 함수입니다.
# Definition. Graph Diameter
# The graph diameter of a graph is the length max(u,v)d(u,v) of the "longest shortest path between any two graph vertices (u,v), where d(u,v) is a graph distance.
#
def getGraphDiameter(Graph):
diameter = 0 # 알고리즘을 시작하기 앞서 diameter 값을 0으로 초기화합니다.
for v in Graph.nodes: # 그래프의 모든 점점들 대해서 아래와 같은 반복문을 수행합니다.
length = nx.single_source_shortest_path_length(Graph, v) # 1. 정점 v로 부터 다른 모든 정점으로 shortest path length를 찾습니다.
max_length = max(length.values()) # 2. 그리고 shortest path length 중 최댓값을 구합니다.
if max_length > diameter: # 3. 2에서 구한 값이 diameter보다 크다면 diameter를 그 값으로 업데이트 합니다.
diameter = max_length
return diameter # 반복문을 돌고 나온 diameter를 return합니다.
정의한 함수를 이용하여, 세 가지의 그래프를 비교¶
In [5]:
# 아래는 위의 함수로 구한 그래프 지름 및 전역 군집 계수 값과 networkX에서 지원하는 library로 구한 값을 비교해봅니다.
#
# | 그래프 지름 | 전역 군집 계수
# ------------------+------------------------------------------------------------
# Regular Graph | High | High
# Small World Graph | Low | High
# Random Graph | Low | Low
#
print("1. Graph Diameter")
print("cycle graph : " + str(nx.diameter(cycle_graph)))
print("cycle graph : " + str(getGraphDiameter(cycle_graph)))
print("regular graph : " + str(nx.diameter(regular_graph)))
print("regular graph : " + str(getGraphDiameter(regular_graph)))
print("small world graph : " + str(nx.diameter(small_world_graph)))
print("small world graph : " + str(getGraphDiameter(small_world_graph)))
print("random graph : " + str(nx.diameter(random_graph)))
print("random graph : " + str(getGraphDiameter(random_graph)) + "\n")
print("2. Average Clustering Coefficient")
print("cycle graph : " + str(nx.average_clustering(cycle_graph)))
print("cycle graph : " + str(getGraphAverageClusteringCoefficient(cycle_graph)))
print("regular graph : " + str(nx.average_clustering(regular_graph)))
print("regular graph : " + str(getGraphAverageClusteringCoefficient(regular_graph)))
print("small world graph : " + str(nx.average_clustering(small_world_graph)))
print("small world graph : " + str(getGraphAverageClusteringCoefficient(small_world_graph)))
print("random graph : " + str(nx.average_clustering(random_graph)))
print("random graph : " + str(getGraphAverageClusteringCoefficient(random_graph)) + "\n")
비교 분석 결과¶
In [6]:
# 그래프의 차수 분포을 그리는 부분입니다.
print("3. Degree Distribution")
degree_sequence = sorted([d for n, d in random_graph.degree()], reverse = True)
degreeCount = collections.Counter(degree_sequence)
deg, cnt = zip(*degreeCount.items())
plt.bar(deg, cnt, color="b")
plt.xlabel('degree')
plt.ylabel('number of vertices')
plt.xticks([2, 3, 4])
plt.show()
'AI > 이론' 카테고리의 다른 글
| 그래프를 추천시스템에 어떻게 활용할까?(기본) (0) | 2021.02.24 |
|---|---|
| 그래프의 구조를 어떻게 분석할까? (0) | 2021.02.24 |
| 그래프를 바이럴 마케팅에 어떻게 활용할까? (0) | 2021.02.23 |
| 검색 엔진에서는 그래프를 어떻게 활용할까? (0) | 2021.02.23 |
| 그래프란 무엇이고 왜 중요할까? (0) | 2021.02.22 |
| Advanced Self-Supervised Pre-training Models (0) | 2021.02.19 |
| Self-Supervised Pre-training Models (0) | 2021.02.19 |
| Transformer 이론 (0) | 2021.02.18 |