[U] Day 21 - 그래프 이론 기초 & 그래프 패턴

[Graph 1강] 그래프란 무엇이고 왜 중요할까?

💡

그래프의 관련 필수 개념 소개를 통해 그래프에 대한 개요를 알아본다.

그래프란 무엇일까?

그래프란, 정점의 집합과 간선의 집합으로 이루어진 수학적 구조이다.

그래프의 다양한 용어는 같은 의미임에도 여러가지로 칭해질 수 있다.

그래프(Graph) = 네트워크(Network)

정점(Vertex) = 노드(Node)

간선(Edge) = 링크(Link)

그래프는 왜 중요할까?

그래프는 복잡계(Complex System)을 표현하고 분석하기 위한 일종의 '언어'이다.

복잡계란, 구성 요소간의 상호작용이 있는 복잡한 세계를 의미한다. 예를 들면, 사회는 70억 인구로 구성된 복잡계이며, 통신 시스템은 전자장치로 구성된 복잡계이다.

그래프는 복잡계에서 일어나는 상호작용을 표현하기에 효과적인 언어이다. 상호작용에 대한 이해를 바탕으로 복잡계를 이해하고, 복잡계에 대한 예측을 수행할 수 있다. 대표적으로 전산학, 물리학, 생물학, 화학, 사회과학 등에서 중요한 역할을 수행한다.

그래프 관련 인공지능 문제

인공지능과 그래프를 활용하여 다양한 분야의 문제를 해결할 수 있다. 본 강의에서 배울 분야와 예시에 대해 알아보자.

정점 분류 문제(Node Classification)는 정점에 해당하는 개체가 어떤 특성을 가지는지 파악하는 문제에 해당한다.

연결 예측 문제(Link Prediction)는 간선에 대한 분석을 통해 복잡계에 대한 예측을 수행하는 문제이다.

추천 문제(Recommendation)는 어떤 사용자가 어떤 물체에 대한 만족도를 예측하는 문제이다.

군집 분석 문제(Community Detection)는 연결 관계로부터 특징을 도출하는 등의 문제이다.

랭킹 문제(Ranking)와 정보 검색 문제(Information Retrieval)는 웹과 같은 거대한 복잡계 속에서 정보를 선별해내는 등의 문제이다.

정보 전파 문제(Information Cascading)와 바이럴 마케팅 문제(Viral Marketing)는 정보가 어떤 네트워크를 통해 전파되는지 파악하는 등의 문제이다.

그래프의 유형 및 분류

그래프는 다양한 기준을 통해 구분되고 다양한 특성을 효과적으로 표현할 수 있다.

간선 방향의 유무에 따라 Undirected Graph와 Directed Graph로 구분할 수 있다.

가중치의 유무에 따라 Unweighted Graph와 Weighted Graph로 구분할 수 있다.

정점의 종류에 따라 동종 그래프(Unpartite Graph)와 이종 그래프(Bipartite Graph)로 구분할 수 있다. 이종 그래프는 다른 종류의 정점이 존재하고, 정점이 서로 다른 경우에만 간선이 연결된다.

위와 같은 구분으로 예시의 그래프의 종류를 구별해보자.

그래프관련 필수 기초개념

그래프는 수학적 구조이므로, 수학적 표기를 통해 구조를 표현할 수 있다.

$V$ : 정점의 집합

$E$ : 간선의 집합

$G = (V, E)$ : 그래프의 표현

정점간의 상호관계에서 가장 대표적인 정보는 이웃 정보이다. 이는 다양한 방식으로 표현될 수 있다. 우선, 방향성의 유무에 따라 다르게 표현되는 방법을 알아보자.

방향성이 없는 그래프의 경우에는 정점 $v$ 의 이웃 집합을 $N(v)$ 혹은 $N_v$ 의 형태로 표현할 수 있다.

방향성이 있는 그래프의 경우에는 정점 $v$ 로부터 나가는 이웃을 $N_{out}(v)$ 으로, 들어오는 이웃을 $N_{in}(v)$ 로 표현한다.

$N_{out}(5) = \{1,2\}$ 이고, $N_{in}(4)=\{3\}$ 이다.

파이썬 라이브러리 NetworkX 소개

NetworkX를 이용해 그래프를 생성, 변경, 시각화할 수 있다. 이외에도 Snappy 라이브러리도 자주 사용된다.

라이브러리의 명칭은 networkx이며, nx의 별칭으로 사용된다.

import networkx as nx  # 라이브러리 임포트 및 별칭 지정

함수 호출을 통해 그래프를 초기화한다. 방향성의 유무에 따라 nx.Graph()와 nx.DiGraph()로 구분하여 사용한다.

G = nx.Graph()  # 방향성이 없는 그래프 초기화
DiGraph = nx.DiGraph()  # 방향성이 있는 그래프 초기화

정점을 추가하고, 정점의 수를 세거나 목록을 반환하는 함수가 존재한다.

G.add_node(1)  # 정점 1 추가
G.number_of_nodes()  # 그래프 내의 정점 수 반환
G.nodes  # 그래프 내의 정점 목록 반환

정점을 추가한 이후에, 간선을 추가하고, 간선의 목록을 확인한다. 간선을 추가할 때에는, 연결하고자 하는 두 정점을 전달인자로 전달한다.

for i in range(11) :
	G.add_node(i)  # 1~10 정점 추가

G.add_edge(1, 2)  # 정점 1과 정점 2를 연결하는 간선 추가
G.edges  # 그래프 내의 간선 목록 반환

간선을 추가한 이후에, 그래프를 시각화한다. 시각화할 때에는 그래프의 위치를 지정하는 nx.spring_layout()을 사용한다. 위 함수로부터 얻어진 위치값을 전달인자로 사용해 nx.draw_networks_edges()에 전달한다.

for i in range(2, 11) :  
	G.add_edge(1, i)  # 정점 1과 정점 2~10과의 간선 추가

pos = nx.spring_layout(G)  # 간선이나 정점이 겹치지 않도록 위치 초기화
im = nx.draw_networkx_nodes(G, pos, node_color='red', node_size=100)  # 정점의 색과 크기 지정하여 출력
nx.draw_networks_edges(G, pos)  # im위에 간선 출력
nx.draw_networks_labels(G, pos, font_size=10, font_color='black')  # 정점의 라벨 출력
plt.show()  # 전체 이미지 출력

그래프의 표현 및 저장

위에서 보았듯 그래프는 다양한 구조를 가지며, 각 그래프의 특징에 따라 적합한 표현방식과 저장방식이 있다.

간선 리스트(Edge List)는 그래프를 간선들의 관계를 순서쌍으로 하여 리스트로 저장하는 형태이다. 방향성이 없는 경우에는 각 노드간의 순서가 바뀌어도 무관하나, 방향성이 있는 경우에는 출발점과 도착점의 순서로 저장된다.

인접 리스트(Adjacent List)는 정점을 기준으로 하여 이웃의 리스트를 저장하는 형태이다. 방향성이 없는 경우에는 한 개의 리스트로 저장할 수 있으나, 방향성이 있는 경우에는 두 개의 리스트로 저장한다.

인접 행렬(Adjacency Matrix)는 정점을 기준으로 한 행렬의 형태이다. $i$ 는 행으로, $j$ 는 열로 할 때, 정점 $i$ 로부터 정점 $j$ 까지의 간선을 표기한다. 간선이 있는 경우 1, 없는 경우 0의 값을 갖는다. 방향성이 없는 경우에는 대칭행렬이나, 방향성이 있는 경우에는 이를 만족하지 않을 수 있다.

NetworkX를 통해 그래프를 표현하고 저장할 때에는 다음과 같은 함수를 사용할 수 있다. 인접 행렬로 저장할 때에는, 정점과 간선의 수를 고려하여 적합한 행렬의 형태로 저장하는 것이 바람직하다.

nx.to_dict_of_lists(G)  # 그래프를 인접 리스트로 저장
nx.to_edgelist(G)  # 그래프를 간선 리스트로 저장
nx.to_numpy_array  # 그래프를 일반 인접 행렬로 저장
nx.to_scipy_sparse_matrix(G)  # 그래프를 희소 인접 행렬로 저장

실습 코드

Graph Basic

Graph Representation

[Graph 2강] 실제 그래프는 어떻게 생겼을까?

💡

실제 그래프와 랜덤 그래프에 대해 알아보고, 각 그래프의 패턴에 대해 알아본다.

실제 그래프 vs 랜덤 그래프

실제 그래프란, 현실 세계나 실제 존재하는 복잡계로부터 생성된 그래프를 의미한다. 랜덤 그래프는 확률적 과정을 통해 생성된 그래프를 의미한다. 예를 들면, 메신저 사용과 관련된 그래프는 실제 그래프이고 수학자에 의해 제시된 확률 그래프는 랜덤 그래프에 해당한다.

대표적으로 에르되스-레니 랜덤 그래프가 있다. 이 그래프 $G(n, p)$ 는 $n$ 개의 정점을 지니며, 임의의 두 정점 사이에 간선이 존재할 확률을 $p$ 로 정의한다. 또한, 정점간의 연결은 서로 독립적으로 가정한다. 예를 들면, $G(3, 0.3)$ 으로 정의 할 수 있다. 이 랜덤 그래프는 다음과 같이 확률에 따라 다른 그래프가 된다.

각 그래프의 등장 확률은 간선이 존재하거나, 존재하지 않을 확률을 곱해 구할 수 있다. 이는, 각 간선이 서로 독립적인 사건이기 때문이다.

작은 세상 효과

작은 세상 효과는 그래프의 크기에 비해 정점간의 평균 거리가 짧다는 현상을 일컫는다. 이에 대해 자세히 알아보기 전에, 관련된 개념에 대해 정리하자.

경로(Path)란, 정점 $u$ 와 $v$ 에 대해서 아래 두 조건을 만족하는 정점들의 순열을 의미한다.

$u$ 에서 시작해서 $v$ 로 끝난다.

순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.

경로의 길이는 해당 경로상에 놓이는 간선의 수를 의미한다. 거리(Distance)는 최단 경로의 길이를 의미한다. 그래프의 지름(Diameter)는 정점 간 거리의 최대값을 의미한다.

정점 1과 8의 거리는 3이다. 정점 2와 8의 거리 등에 의해 그래프의 지름은 4이다.

여섯 단계 분리 실험을 통해서 평균적으로 6단계만으로 편지가 미국을 횡단할 수 있다는 놀라운 결과를 보여주었고, 대표적인 작은 세상 효과의 예시이다.

이 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재하는 특징이다. 단, 작은 세상 효과가 존재하지 않는 형태의 그래프도 존재한다.

연결성의 두터운 꼬리 분포

실제 그래프의 연결성 분포는 두터운 꼬리를 갖는다. 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재한다는 의미이다. 이에 대해 자세히 알아보기 전에, 연결성의 개념에 대해 알아보자.

정점의 연결성(Degree)은 정점과 연결된 간선의 수를 의미한다. 방향성이 없는 그래프에서는 이웃의 수와 연결성이 동일한 값을 가진다. 정점 $v$ 의 연결성은 $d(v)$ , $d_v$ , $|N(v)|$ 로 표시한다. 방향성이 있는 그래프에서는 방향에 따라 다르게 연결성을 표현한다.

실제 그래프는 연결성이 매우 높은 허브가 존재하나, 랜덤 그래프의 연결성 분포는 허브 정점이 존재할 확률이 매우 낮다. 랜덤 그래프의 연결성 분포는 높은 확률로 정규분포를 따르기 때문이다.

거대연결 요소

실제 그래프에는 대다수의 정점을 포함하는 거대한 연결요소가 존재한다. 이전에 연결 요소가 무엇인지 알아보자.

연결요소란, 아래 두 조건을 만족하는 정점의 집합을 의미한다.

연결 요소에 속하는 정점들은 경로로 연결될 수 있다.

위 조건을 만족하는 동시에, 정점을 더 추가할 수 없는 상태이다.

실제 그래프에 해당하는 MSN 메신저 그래프에는 99.9%의 정점이 하나의 거대 연결요소에 포함된다. 랜덤 그래프에도 높은 확률로 거대 연결요소가 존재할 수 있다. 단, 이는 정점들의 평균 연결성에 의해 결정된다.

군집 계수

실제 그래프에서는 군집 계수가 높아 많은 군집이 존재하지만, 랜덤 그래프는 군집 계수가 높지 않다. 군집 계수가 무엇인지 알아보자.

군집이란, 수학적으로 엄밀하지는 않지만 비교적 다음과 같은 특징을 가진 정점들의 집합을 의미한다.

집합에 속하는 정점 사이에는 많은 간선이 존재한다.

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

군집의 정도를 파악하는 지표로 지역적 군집 계수를 사용할 수 있다. 이는 한 정점에서 군집의 형성 정도를 측정하는 지표이다. 정점 $i$ 의 군집 계수는, $i$ 의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미한다. 사진의 예를 통해 계산해보자.

정점 1의 이웃은 총 4개이며, 이웃의 쌍은 총 6개 존재한다. 이 중 각 쌍이 서로 연결되어 있는 경우는 3가지로, 최종적인 값은 0.5가 된다. 즉, 지역적 군집 계수가 높을수록 군집의 형성 정도가 높다는 것을 알 수 있다.

다양한 지역적 군집 계수의 예시 지역적 군집 계수가 0인 경우는 전역 군집계수를 계산할 때 제외된다.

전역 군집계수는 지역적 군집 계수의 평균을 통해 계산된다. 이는 전체 그래프에서의 군집의 형성 정도를 측정하는데 사용된다.

실제 그래프는 군집 계수가 높고, 많은 군집이 존재한다. 이는 실제 세계에서 나타나는 다양한 현상과 밀접한 관계가 있을 수 있다. 하지만, 랜덤 그래프는 간선의 연결을 독립적으로 가정하기 때문에, 이와 같은 현상이 발생하지 않고 군집 계수가 낮은 특징을 보인다.

파이썬을 이용한 지름 및 군집 계수 분석

세 종류의 그래프 데이터를 불러와 구조를 분석하는 실습을 진행해보자.

작은 세상 그래프는 균일 그래프의 일부 간선을 임의로 대체한 그래프이다.

Drive에 저장되어 있는 Text File의 정보를 통해 그래프를 생성한다.

regular_graph = nx.Graph()
data = osp.abspath(osp.join(os.getcwd(), 'drive/MyDrive/data/simple/regular.txt'))
f = open(data)
for line in f :
	v1, v2 = map(int, line.split())
	regular_graph.add_edge(v1, v2)

그래프의 전역 군집 계수를 계산하는 함수를 정의한다.

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_conncted_pairs / (Graph.degree(v) * (Graph.degree(v) -1) / 2)
		ccs.append(cc)
	return sum(ccs) / len(ccs)

그래프의 지름을 계산하는 함수를 정의한다.

def getGraphtDiameter(Graph) :
	diameter = 0
	for v in Graph.nodes :
		length = nx.single_source_shortest_path_length(Graph, v)
		max_length = max(length.values())
		if max_length > diameter :
			diameter = max_length
	return diameter

이를 통해 세 종류의 그래프를 비교하여 정리하면 다음과 같다.

실습 코드

Graph Property

Reference

NetworkX Documentation

Snappy Page

Explain Random Graph Modeling

Uploaded by Notion2Tistory v1.1.0

[U] Day 23 - 군집 탐색 & 추천시스템 (기초) (0)	2021.03.26
[U] Day 22 - 페이지 랭크 & 전파 모델 (0)	2021.03.26
[U] Day 20 - NLP V (0)	2021.03.26
[U] Day 19 - NLP IV (0)	2021.03.26
[U] Day 18 - NLP III (0)	2021.03.26

까짓 거 해보죠!