그래프란 무엇이고 왜 중요할까?¶
✅ 그래프란 무엇일까?¶
그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조이다.
- 하나의 간선은 두개의 정점을 연결한다.
- 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아니다.
- 그래프는 네트워크(Network)로도 불린다.
- 정점(Vertex)은 노드(Node)로 간선은 엣지(Edge) 혹은 링크(Link)로도 불린다.
✅ 그래프 관련 인공지능 문제¶
- 정점 분류(Node Classification) 문제
- 트위터에서의 공유(Retweet) 관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있을까?
- 단백질의 상호작용을 분석하여 단백질의 역할을 알아낼 수 있을까?
- 연결 예측(Link prediction) 문제
- 페이스북 소셜네트워크는 어떻게 진화할까?
- 추천(Recommendation) 문제
- 각자에게 필요한 물건은 무엇일까? 어떤 물건을 구매해야 만족도가 높을까?
- 군집 분석(Community Detection) 문제
- 연결 관계로부터 사회적 무리(social Circle)을 찾아낼 수 있을까?
- 랭킹(Ranking) 및 정보 검색(Information Retrieval) 문제
- 웹(Web)이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?
- 정보 전파(Information Cascading) 및 바이럴 마케팅(Viral Marketing) 문제
- 정보는 네트워크를 통해 어떻게 전달될까? 어떻게 정보 전달을 최대화 할 수 있을까?
✅ 그래프 관련 필수 기초 개념¶
1️⃣ 그래프의 유형 및 분류¶
방향이 없는 그래프(Undirected Graph) 🆚 방향이 있는 그래프(Directed Graph)¶
가중치가 없는 그래프(Unweighted Graph) 🆚 가중치가 있는 그래프(Weighted Graph)¶
동종 그래프(Unpartite Graph) 🆚 이종 그래프(Bipartite Graph)¶
2️⃣ 필수 기초 개념¶
그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조이다.
보통 정점들의 집합을 $V$, 간선들의 집합을 $E$, 그래프를 $G=(V,E)$로 적는다.
정점의 이웃(Neighbor)은 그 정점과 연결된 다른 정점을 의미한다.
정점 $v$의 이웃들의 집합을 보통 $N(v)$혹은 $N_{v}$로 적는다.
방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분한다.
- 정점 $v$에서 간선이 나가는 이웃(Out-Neighbor)의 집합을 보통 $N_{out}(v)$로 적는다.
- 정점 $v$로 간선이 들어오는 이웃(In-Neighbor)의 집합을 보토$N_{in}(v)$로 적는다.
✅ 그래프의 표현 및 저장¶
1️⃣ NetworkX 라이브러리¶
필요한 라이브러리를 불러온다.¶
In [1]:
import networkx as nx # NetworkX
import numpy as np # 선형대수를 위한 라이브러리
import matplotlib.pyplot as plt # 그림을 그리기 위한 라이브러리
import sys
np.set_printoptions(threshold=sys.maxsize)
그래프를 초기화 한다.¶
In [2]:
print("###### Graph Init ######")
G= nx.Graph() # 방향성이 없는 그래프
DiGraph = nx.DiGraph() # 방향성이 있는 그래프
정점을 추가하고, 정점의 수를 세고, 목록을 반환¶
In [3]:
print("###### Add Node to Graph ######")
print("# Add node 1")
G.add_node(1) # 정점 1 추가
print("Num of nodes in G : " + str(G.number_of_nodes())) # 정점의 수 반환
print("Graph : " + str(G.nodes)+ "\n") # 정점의 목록 반환
더 많은 정점을 추가¶
In [4]:
print("# Add vertex 2 ~ 10") # 정점 2 ~ 10 추가
for i in range (1, 11):
G.add_node(i)
print("Num of nodes in G : " + str(G.number_of_nodes()))
print("Graph : " + str(G.nodes) + "\n")
간선을 추가하고, 목록 반환¶
In [5]:
print("###### Add Edge to Graph ######")
G = nx.Graph()
print("#Add edge (1, 2)")
G.add_edge(1, 2) # 정점 1과 2 사이에 간선 추가
print("Graph : " + str(G.edges) + "\n") # 간선의 목록 반환
더 많은 간선을 추가¶
In [6]:
print("#Add edge (1, i) for i = 2 ~ 10") # 정점 1과 다른 정점 사이의 간선 추가
for i in range (2, 11):
G.add_edge(1, i)
print("Graph : " + str(G.edges) + "\n")
만들어진 그래프를 시각화¶
In [7]:
# 그래프를 시각화
# 정점의 위치 결정
pos = nx.spring_layout(G)
In [8]:
pos
Out[8]:
In [9]:
# 정점의 색과 크기를 지정하여 출력
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()
2️⃣ 그래프의 표현 및 저장¶
간선 리스트(Edge List): 그래프를 간선들의 리스트로 저장¶
- 각 간선은 해당 간선이 연결하는 두 정점들의 순서쌍(Pair)으로 저장한다.
- 방향성이 있는 경우에는 (출발점, 도착점) 순서로 저장된다.
인접 리스트(Adjacent list)¶
- 방향성이 없는 경우 각 정점의 이웃들을 리스트로 저장
- 방향성이 있는 경우 각 정점의 나가는 이웃들과 들어오는 이웃들을 각각 리스트로 저장
인접 행렬(Adjacency Matrix)¶
방향성이 없는 경우
- (정점 수) x (정점 수)크기의 행렬을 가진다.
- 정점 𝑖와 𝑗사이에 간선이 있는 경우, 행렬의 𝑖행 𝑗열(그리고 𝑗행 𝑖열) 원소가 1
- 정점 𝑖와 𝑗사이에 간선이 없는 경우, 행렬의 𝑖행 𝑗열(그리고 𝑗행 𝑖열) 원소가 0
방향성이 있는 경우
- (정점 수) x (정점 수)크기의 행렬을 가진다.
- 정점 𝑖에서 𝑗로의 간선이 있는 경우, 행렬의 𝑖행 𝑗열 원소가 1
- 정점 𝑖에서 𝑗로의 간선이 없는 경우, 행렬의 𝑖행 𝑗열 원소가 0
In [10]:
G = nx.Graph()
In [11]:
# 10개의 node로 이루어진, 원 모양의 그래프 정보를 가져옵니다.
# 각 데이터셋은 edge 형태로 저장되어 있습니다.
print("###### Read Graphs ######")
#data = osp.abspath(osp.join(os.getcwd(), 'drive/MyDrive/data/lab/lab1/small_cycle.txt'))
f = open('../실습코드/data/lab/lab1/small_cycle.txt')
for line in f: # 파일의 각 라인은 v1 v2 형태로 저장되어있습니다.
v1, v2 = list(map(int, line.split())) # 각 라인을 읽어 space를 기준으로 split해주고 이를 integer mapping해줍니다.
G.add_edge(v1, v2)
print(G.edges)
In [12]:
# 그래프를 인접 리스트로 저장
print("###### Graph to List ######")
ListGraph = nx.to_dict_of_lists(G)
for v in ListGraph:
print(str(v) + " : " + str(ListGraph[v]))
In [13]:
# 그래프를 간선 리스트로 저장
print("###### Graph to EdgeList ######")
EdgeListGraph = nx.to_edgelist(G)
for e in EdgeListGraph:
v1, v2, w = e
print(v1, v2)
In [14]:
# 그래프를 인접 행렬(일반 행렬)로 저장
print("###### Graph to numpy array ######")
NumpyArrayGraph = nx.to_numpy_array(G)
print(NumpyArrayGraph)
In [15]:
# 그래프를 인접 행렬(희소 행렬)로 저장
print("###### Graph to Spicy sparse matrix ######")
SparseMatrixGraph = nx.to_scipy_sparse_matrix(G)
print(SparseMatrixGraph)
'AI > 이론' 카테고리의 다른 글
| 그래프의 구조를 어떻게 분석할까? (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 |
| Beam search and BLEU (0) | 2021.02.17 |