해당 포스팅은 네이버 부스트캠프 AI Tech 학습 정리 자료임을 알려드립니다.
1. 강의 정리
신기정 교수님 - 그래프란 무엇이고 왜 중요할까?
1) 그래프란 무엇일까?
그래프는 정점 집합과 간선 집합으로 이루어진 수학적 구조입니다. 간선은 두 개의 정점을 연결하며, 모든 정점은 반드시 간선으로 연결되는 것은 아닙니다. 여기서의 간선은 엣지, 링크로 , 정점은 노드로, 그래프는 네트워크로 표현하기도 합니다.
그렇다면 이 그래프란 것이 왜 중요할까요? 그래프의 중요성을 이해하기 위해서는 가장 먼저 복잡계(Complex System)을 알아야 합니다. 복잡계는 말로만 들어도 어렵게 느껴지기에 어떤한 것들이 복잡계인지 설명하면, 우리가 살고 있는 사회, 전자 장치로 구성된 통신시스템 외에도 정보, 뇌, 신체 모두 복잡계로 생각할 수 있습니다. 이러한 복잡계들은 공통적으로 구성요소 간의 복잡한 상호작용이 존재합니다. 그래서 그래프를 사용하면 복잡계를 효과적으로 표현하고 분석할 수 있습니다. 이를 활용한 예시로는 페이스북을 들 수 있는데 사용자를 정점, 두 사이의 관계가 있다면 그것을 간선으로 이어주는 방식으로 활용할 수 있습니다. 이외에도 수많은 복잡계를 그래프로 표현해서 분석할 수 있습니다.
2) 그래프 관련 인공지능 문제
첫 번째, 정점 분류(Node Classification) 문제는 정점이 여러 유형을 가졌을 때, 각 정점이 어떤 유형인지 추측하는 문제입니다. 이러한 예시로는 트위터를 통해 나오는 글을 사용자(정점)가 공유했을 때, 그 사용자(정점)이 어떤 유형인지를 파악하는 문제가 있습니다. 또한 단백질의 상호작용을 분석하여 단백질의 역할을 분류하는 문제가 포함되어 있습니다.
두 번째, 연결 예측(Link Prediction) 문제는 거시적 관점과 미시적 관점으로 살펴볼 수 있습니다. 거시적 관점에서 연결 예측 문제는 주어진 그래프가 얼마나 성장할 수 있는 지 예측하는 것입니다. 미시적 관점에서의 연결 예측 문제는 각 정점이 앞으로 어떤 정점과 연결될 지를 예측하는 것입니다. 이것은 추천 문제와도 밀접하게 연관되어 있습니다.
세 번째, 군집 분석(Community Detection) 문제는 서로 밀접하게 연결된 정점들의 집합(군집)을 찾아내는 것입니다. 많은 그래프에서 군집들은 의미있는 구조를 나타내는 경우가 많습니다. 군집은 사회적 무리(Social Circle)을 이루게 되는 데, 이러한 사회적 무리를 그룹핑해주는 것이라고 생각하시면 될 것 같습니다.
네 번째, 랭킹(Ranking) 및 정보 검색(Information Retrieval) 문제는 우리가 원하는 정보를 얻기 위한 것입니다. 이는 웹 상에서 웹페이지들의 관계를 파악해서 우리에게 중요한 정보인 것을 찾는 것과 같습니다.
다섯 번째, 정보 전파(Information Cascading) 및 바이럴 마케팅(Viral Marketing) 문제는 정보가 소셜 미디어를 통해서 어떻게 전파가 되고, 어떻게 해야 멀리까지 전달이 될 수 있는가에 대한 것입니다.
3) 그래프 관련 필수 기초 개념
그래프는 다양한 기준인 방향의 유무, 가중치의 유무, 정점의 종류로 나눠볼 수 있습니다.
먼저, 방향의 유무에 따라 방향이 없는 그래프(Undirected Graph)와 방향이 있는 그래프(Directed Graph)로 나눠 볼 수 있습니다. 간선에 방향이 없는 그래프는 동등한 위치의 그래프를 이야기합니다. 반면, 간선에 방향이 있는 그래프는 동등한 위치의 그래프가 아닙니다. 예를 들어, 제가 유명 연예인의 계정을 follow했다고 해서 그 유명한 연예인이 저를 follow하지는 않듯이 동등한 위치가 아니고 다른 위치에 있는 그래프입니다.
두 번째, 가중치의 유무에 따라 가중치가 없는 그래프(Unweighted Graph)와 가중치가 있는 그래프(Weighted Graph)로 나눌 수 있습니다. 간선에 가중치가 없는 그래프는 보통 웹 그래프가 여기에 해당됩니다. 물론, 가중치를 부여할 수 있지만 그것이 크게 의미가 없을 때, 간선에 가중치가 없는 그래프를 활용합니다. 반면, 간선에 가중치가 있는 그래프는 전화 그래프처럼 전화횟수가 그 사람과의 친밀도를 나타낼 수 있는 경우에 활용하게 되며, 간선에 숫자로 가중치를 부여합니다.
마지막으로, 동종 그래프(Unpartite Graph)와 이종 그래프(Bipartite Graph)로 나눠볼 수 있습니다. 단일 종류의 정점을 가지는 경우는 동종 그래프로 분류하게 됩니다. 페이스북 친구 그래프가 이것에 해당됩니다. 페이스북의 경우에는 정점이 사용자로만 이뤄져있기 때문입니다. 반면, 이종 그래프는 사용자가 상품을 구매하는 것과 같이 여러개의 정점을 가지는 특징이 있으며, 전자 상거래 구매내역 등이 여기에 포함됩니다.
그래프는 위에서 설명했듯이 정점 집합과 간선 집합으로 이루어져 있습니다. 정접들의 집합을 $V$, 간선들의 집합을 $E$라고 했을 때, 그래프를 $G = (V, E)$라고 표현합니다.
정점의 이웃(neighbor)은 해당 정점과 연결된 다른 정점을 의미합니다. 그래서 정점 $v$의 이웃들의 집합을 보통 $N(v)$ 혹은 $N_{v}$로 표현합니다.
방향성이 있는 그래프에서는 이웃(neighbor)의 개념을 나가는 이웃과 들어오는 이웃을 구분합니다. 그래서 정점 $v$에서 간선이 나가는 이웃의 집합을 $N_{out}(v)$로 적고, 정점 $v$로 간선이 들어오는 이웃의 집합을 보통 $N_{in}(v)$로 적습니다.
4) 그래프의 표현과 저장
그래프를 다루기 위해 파이썬 라이브러리인 NetworkX를 사용합니다. 이 라이브러리를 활용해서 그래프를 생성, 변경, 시각화할 수 있습니다. 또한 그래프의 구조와 변화 역시 확인할 수 있습니다. 이외에도 Snap.py라는 라이브러리도 많이 사용됩니다. NetworkX는 사용하기엔 편리하지만 속도가 느리고, Snap.py는 사용은 불편하지만 속도는 빠른 특징이 있습니다. 서로 다른 내용을 포함하고 있어 둘다 아는 것이 좋습니다.
NetworkX를 활용한 코드는 아래의 접은 글에 주석과 함께 설명해놓았습니다.
# 실습에 필요한 library를 임포트합니다.
import networkx as nx # NetworkX
import numpy as np # 선형대수를 위한 라이브러리
import matplotlib.pyplot as plt # 그림을 그리기 위한 라이브러리
import sys
np.set_printoptions(threshold=sys.maxsize) # 배열의 전체를 확인할 때 사용하는 명령어
###### Graph Init ######
G= nx.Graph() # 방향성이 없는 그래프 초기화
DiGraph = nx.DiGraph() # 방향성이 있는 그래프 초기화
# Add node 1
G.add_node(1) # 정점 1 추가
print(str(G.number_of_nodes())) # 정점의 수 반환 실행결과 : 1
print(str(G.nodes)) # 정점의 목록 반환 실행결과 : [1]
# Add vertex 2 ~ 10 # 정점 2 ~ 10 추가
for i in range(2,11):
G.add_node(i)
print(str(G.number_of_nodes())) # 실행결과 : 10
print(str(G.nodes)) # 실행결과 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Add edge to graph
G = nx.Graph()
G.add_edge(1, 2) # 정점 1과 2 사이에 간선 추가
print(str(G.edges)) # 간선의 목록 반환 실행결과 : [(1, 2)]
# 1과 다른 정점 i 와의 간선 추가
for i in range (2, 11):
G.add_edge(1, i)
print(str(G.edges)) # 실행결과 : [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)]
# 그래프를 시각화
pos = nx.spring_layout(G) # 정점의 위치 결정
im = nx.draw_networkx_nodes(G, pos, node_color="red", node_size=100) # 정점의 색과 크기를 지정하여 출력
nx.draw_networkx_edges(G, pos) # 간선 출력
nx.draw_networkx_labels(G, pos, font_size=10, font_color="black") # 각 정점의 라벨을 출력
plt.show()
그래프를 저장하는 방법에는 여러가지가 있으며, 여기에서도 방향성의 여부에 따라 나눠서 표현해주기도 합니다.
간선 리스트(Edge List)는 그래프를 간선들의 리스트로 저장하는 방식입니다. 방향성이 없는 경우에는 인접한 정점 사이에 간선이 존재하면, 해당 정점들을 튜플 형태로 리스트에 저장합니다. 예시는 [(1, 2), (1, 3), (1, 4)] 와 같이 표현할 수 있습니다. 방향성이 있는 경우에는 (출발점, 도착점) 순서로 저장합니다. 간선 리스트는 표기는 편하지만, 간선을 찾는 과정이 오래걸리는 단점이 존재합니다.
인접 리스트(Adjacent list)는 방향성이 있는 경우와 없는 경우로 나눌 수 있지만, 위에서 방향성의 유무에 따라 in, out으로 나눈 것과 같이 표현해주면 됩니다. 각 정점의 이웃들을 리스트로 저장하는 방식을 활용하고, 이 방법은 출발점을 중심으로 한 간선의 개수를 파악하기 용이합니다.
인접 행렬(Adjacency Matrix)도 방향성의 유무에 따라 두가지로 나눌 수 있습니다. 인접 행렬의 경우 정점 수의 차원을 갖는 정방행렬로 만들 수 있습니다.
방향성이 없는 경우에는 위의 그림처럼 대칭행렬의 형태를 가지게 되며, 간선의 유무로 0과 1을 표현할 수 있습니다. 방향성이 있는 경우는 두 번째 그림에 해당되며, 행이 출발점, 열이 도착점으로 생각하고 0과 1을 표시해주면 됩니다. 방향성이 있는 경우의 인접행렬은 대칭성을 가지지 않습니다.
아래의 코드블럭은 다양한 방법으로 그래프를 저장하는 것을 구현한 코드입니다. 여기서 일반 행렬과 희소 행렬이 있는데, 기본적으로 0이 아닌 원소가 적을 때에는 희소 행렬을 사용하는 것이 메모리 상에서 유리합니다. 하지만, 0이 아닌 원소가 많을 때에는 일반행렬이 더 계산이 빠르다는 특징이 있습니다.
# 그래프를 인접 리스트로 저장
nx.to_dict_of_lists(G)
# 그래프를 간접 리스트로 저장
nx.to_edgelist(G)
# 그래프를 인접 행렬(일반 행렬)로 저장
nx.to_numpy_array(G)
# 그래프를 인접 행렬(희소 행렬)로 저장
nx.to_scipy_sparse_matrix(G)신기정 교수님 - 실제 그래프는 어떻게 생겼을까?
1) 실제 그래프 vs 랜덤 그래프
실제 그래프(Real Graph)란 다양한 복잡계로부터 얻어진 그래프를 의미합니다. 예를 들어, 소셜 네트워크, 전자상거래 구매 내역 등과 같은 것들이 포함되어 있습니다. 랜덤 그래프(Random Graph)는 확률적 과정을 통해 생성한 그래프를 의미합니다. 여기서 다루는 랜덤 그래프는 에르되스와 레니가 제안한 모델을 사용하고 있습니다. 에르되스-레니 랜덤 그래프는 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됩니다. 표기는 $G(n, p)$로 사용하며, $n$은 정점의 개수를 의미하며, $p$는 임의의 두 개의 정점 사이에 간선이 존재할 확률입니다. 정점 간의 연결은 서로 독립적입니다.
2) 작은 세상 효과
작은 세상 효과를 이해하기 위해서는 경로, 거리 및 지름의 개념이 필요합니다. 경로(Path)는 정점 $u$에서 시작해서 정점 $v$에서 끝나야 하며, 순열에서 연속된 정점은 간선으로 연결되어 있어야 합니다. 여기서 동일한 정점을 여러번 지나가도 상관 없습니다. 경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의됩니다. 항상 경로의 시작점과 끝점을 포함한 정점의 수에서 1개를 뺀 값이 길이가 됩니다. 거리(Distance)는 정점 $u$와 $v$ 사이의 최단 경로의 길이를 의미합니다. 지름(Diameter)은 정점 간 거리의 최댓값입니다. 거리는 최단 경로의 길이를 말하기 때문에 정점의 중복이 허용되지 않습니다.
사회학자 스탠리 밀그램은 1960년대에 여섯 단계 분리라는 실험을 진행했습니다. 오마하(네브라스카 주)와 위치타(켄사스 주)에서 500명의 사람을 뽑아서 보스턴에 있는 한 사람에게 편지를 전달하게끔 했습니다. 이때, 단 지인을 통해서만 전달할 수 있도록 제한했습니다. 그래서 몇 단계를 거쳐야 편지가 도착하는 지를 실험한 것입니다. 약 25%의 편지만 도착했지만, 평균적으로 6단계를 거쳐서 편지가 도착하게 되었습니다. 이러한 현상을 작은 세상 효과라고 부릅니다. 이러한 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재합니다. 예를 들어, 모든 사람이 100명의 지인이 있다고 가정해보면 5단계를 거치면 최대 100억명의 사람과 연결될 수 있습니다. 단, 실제로는 지인의 중복으로 100억명보다는 적을 것이지만 많은 사람들과 연결될 가능성이 높습니다. 하지만, 모든 그래프에서 작은 세상 효과가 존재하는 것은 아닙니다. 체인이나 사이클 그래프, 격자 그래프에서는 작은 세상 효과가 존재하지 않습니다.
3) 연결성의 두터운 꼬리 분포
여기서 이야기하는 연결성(Degree)는 해당 정점과 연결된 간선의 수를 의미합니다. 정점 $v$의 연결성은 $d(v)$, $d_{v}$, $|N(v)|$로 표현합니다. 방향성이 존재하는 경우에는 연결성을 in, out으로 나눠서 표현합니다.
실제 그래프의 연결성 분포는 두터운 꼬리라는 특징을 가집니다. 즉, 연결성이 매우 높은 허브 정점이 존재한다는 것을 의미합니다. 예를 들면, BTS는 수많은 Follower가 있는 허브가 되며 다른 정점들과 연결성이 높습니다. 하지만, 저의 계정의 Follower 수는 엄청 적은 것 처럼 연결성이 낮습니다. 하지만, 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사하게 됩니다. 그래서 랜덤 그래프의 경우 높은 허브 정점이 존재할 가능성은 0에 가깝습니다.
4) 거대 연결 요소
연결 요소는 연결 요소에 속하는 정점들은 경로로 연결될 수 있어야 하며, 정점을 추가할 수없는 정점들의 집합을 이야기 합니다.
위와 같은 그래프가 존재했다고 했을 때, 위에서 말한 조건을 만족하는 연결요소는 {1,2,3,4,5},{6,7,8},{9}가 있습니다. 그렇다면 {1,2,3,4}는 왜 연결요소가 아닐까요? {5}라는 정점이 추가될 수 있기 때문입니다. {5,6,7}은 왜 연결요소가 아닐까요? 이것은 정점들이 경로로 연결될 수 없기 때문입니다.
실제 그래프에는 거대 연결 요소가 존재합니다. 거대 연결 요소는 대다수의 정점을 포함하고 있습니다. 실제 상황에서는 대다수의 정점을 포함하는 거대 연결 요소가 존재합니다.
랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재합니다. 위의 그림처럼 정점들의 평균 연결성이 1보다 충분히 커야 존재할 수 있게 됩니다.
5) 군집 구조
군집 구조를 이해하기 위해서는 군집(Community)이란 개념을 이해해야 하는데 군집은 정점 사이에는 많은 간선이 존재하고 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재해야 합니다. 수학적으로 엄밀한 정의는 아닙니다. 위의 그림을 보면 11개의 군집이 있는 것으로 보입니다.
또한 지역적 군집 계수를 알 수 있어야 합니다. 지역적 군집 계수는 한 정점에서 군집의 형성 정도를 측정합니다. 위의 그림과 같은 그래프가 있었다고 해보면, 먼저 정점 $i$의 이웃 쌍은 총 6개의 경우의 수를 찾을 수 있습니다. 4개의 인접한 정점 중에 2개를 임의로 고르는 방법을 적용하면 6이라는 값이 나오게 됩니다. 그 중에서 이웃 쌍이 직접 간선으로 이어진 것들을 구해서 위와 같이 0.5라는 값을 얻을 수 있습니다. 참고적으로, 연결성이 0인 정점에서는 지역적 군집 계수가 정의 되지 않습니다.
이번에는 전역 군집 계수에 대해 알아보려고 합니다. 전역 군집 계수는 전체 그래프에서 군집의 형성 정도를 측정합니다. 그래프 $G$의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균입니다. 단, 여기서 연결성이 0이여서 지역적 군집 계수가 정의되지 않는 정점은 제외합니다.
실제 그래프에서는 군집 계수가 높습니다. 즉 많은 군집이 존재합니다. 이에 대한 이유는 2가지 정도가 있는 데 하나는 동질성으로 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다는 것입니다. 예를 들어, 같은 동네에 사는 같은 나이의 아이들은 친구가 되기 쉽듯이 이런 경우가 동질성의 예입니다. 두 번째는 전이성으로 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있습니다. 예를 들면, 친구를 서로 소개해주는 경우가 전이성에 해당됩니다.
하지만, 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않습니다. 그 이유는 랜덤 그래프에서는 간선 연결이 독립적이기 때문입니다. 하나의 간선에 다른 간선이 영향을 미치지 않기 때문에 위에서 언급한 동질성, 전이성의 성질을 가지지 않습니다.
