[자료구조] 그래프 (추천 시스템과 네트워크 분석의 기반 구조)

자료구조 시리즈를 트리까지 정리하고 나면 자연스럽게 그래프로 이어집니다. 트리도 사실 그래프의 특수한 형태거든요. 그래프는 노드(Node)와 엣지(Edge)로 구성되는데, 소셜 네트워크에서 친구 관계, 추천 시스템에서 사용자-아이템 관계, 지도에서 경로 탐색까지 실제로 굉장히 많은 곳에 쓰입니다.

 

오늘은 그래프의 기본 구조와 탐색 방법, 그리고 데이터 분석에서 어떻게 활용되는지 정리해보겠습니다. 🕸️

 

1. 그래프의 기본 구조

그래프는 노드(Node, 정점)와 엣지(Edge, 간선)로 구성됩니다. 노드는 데이터를 담는 개체이고, 엣지는 노드 사이의 관계를 나타냅니다. 소셜 네트워크라면 노드가 사람, 엣지가 친구 관계입니다. 지도라면 노드가 도시, 엣지가 도로입니다.

트리와 가장 큰 차이는 사이클(Cycle)의 존재입니다. 트리는 사이클이 없는 계층 구조지만, 그래프는 노드 간 자유롭게 연결될 수 있고 순환 경로도 존재할 수 있습니다.

 

1.1 방향 그래프 vs 무방향 그래프

 

엣지에 방향이 있는지 없는지에 따라 나뉩니다.

 

무방향 그래프(Undirected Graph)는 엣지가 양방향입니다. A-B 엣지가 있으면 A→B도 되고 B→A도 됩니다. 친구 관계가 대표적입니다.

 

방향 그래프(Directed Graph)는 엣지에 방향이 있습니다. A→B 엣지가 있다고 B→A가 되는 건 아닙니다. 팔로우 관계(인스타그램, 트위터)가 여기 해당합니다. 내가 팔로우한다고 상대방이 팔로우하는 건 아니니까요.

 

엣지에 가중치(Weight)가 붙으면 가중 그래프(Weighted Graph)입니다. 지도에서 도시 간 거리, 추천 시스템에서 사용자-아이템 간 상호작용 강도 등에 씁니다.

종류	특징	실제 예시
무방향 그래프	엣지 양방향	친구 관계, 협업 네트워크
방향 그래프	엣지 단방향	팔로우, 웹 페이지 링크
가중 그래프	엣지에 가중치	지도 경로, 유사도 네트워크
이분 그래프	두 집합 간 연결만 존재	사용자-아이템 관계

 

2. 그래프 표현 방법

 

2.1 인접 행렬 vs 인접 리스트

그래프를 코드로 표현하는 방법은 크게 두 가지입니다. 인접 행렬(Adjacency Matrix)은 N×N 행렬로 노드 간 연결 여부를 표시합니다. 연결됐으면 1, 아니면 0입니다. 특정 두 노드가 연결됐는지 O(1)로 확인할 수 있지만, 노드가 많아지면 메모리를 N² 만큼 씁니다. 엣지가 적은 희소 그래프에서는 비효율적입니다.

 

인접 리스트(Adjacency List)는 각 노드가 연결된 노드 목록을 리스트로 가집니다. 메모리를 엣지 수에 비례해서 쓰기 때문에 희소 그래프에 효율적입니다. 실제 데이터 분석에서 다루는 대부분의 그래프(소셜 네트워크, 웹 그래프)는 희소하기 때문에 인접 리스트를 더 많이 씁니다.

# 인접 리스트로 그래프 구현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 인접 행렬로 표현 (노드: A=0, B=1, C=2, D=3, E=4, F=5)
import numpy as np

adj_matrix = np.zeros((6, 6), dtype=int)
edges = [(0,1),(0,2),(1,3),(1,4),(2,5),(4,5)]
for u, v in edges:
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1  # 무방향

print(adj_matrix)

 

3. 그래프 탐색: BFS와 DFS

그래프를 탐색하는 방법은 BFS와 DFS 두 가지입니다. 어떤 걸 쓸지는 어떤 문제를 푸느냐에 따라 달라집니다.

 

3.1 BFS (너비 우선 탐색)

시작 노드에서 가까운 노드부터 탐색합니다. 큐(Queue)를 사용합니다. 최단 경로를 찾을 때 BFS를 씁니다. 가중치 없는 그래프에서 두 노드 사이의 최단 거리(엣지 수 기준)를 보장합니다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

print(bfs(graph, 'A'))
# 출력: ['A', 'B', 'C', 'D', 'E', 'F']
# A에서 가까운 순서: A(0) → B,C(1) → D,E,F(2)

 

3.2 DFS (깊이 우선 탐색)

한 방향으로 끝까지 탐색한 뒤 돌아와서 다른 방향을 탐색합니다. 스택(Stack) 또는 재귀로 구현합니다. 경로가 존재하는지 확인하거나, 연결된 모든 노드를 방문할 때 씁니다.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]

    for neighbor in graph[start]:
        if neighbor not in visited:
            order += dfs(graph, neighbor, visited)
    return order

print(dfs(graph, 'A'))
# 출력: ['A', 'B', 'D', 'E', 'F', 'C']
# A → B 방향으로 끝까지 → 되돌아와서 C 탐색

항목	BFS	DFS
탐색 방향	가까운 노드부터	한 방향으로 끝까지
자료구조	큐 (Queue)	스택 / 재귀
최단 경로	보장 (비가중 그래프)	보장 안 됨
주 사용처	최단 경로, 레벨 탐색	경로 존재 여부, 연결 요소

 

4. 데이터 분석에서의 그래프

 

4.1 추천 시스템

협업 필터링 기반 추천 시스템은 이분 그래프(Bipartite Graph) 구조를 씁니다. 한쪽 집합은 사용자, 다른 쪽 집합은 아이템이고, 사용자가 아이템을 구매하거나 평점을 매기면 엣지가 생깁니다. 특정 사용자와 비슷한 패턴을 가진 다른 사용자를 찾아 그 사용자가 좋아하는 아이템을 추천하는 구조가 이 그래프 탐색에서 나옵니다.

 

최근에는 Graph Neural Network(GNN)를 활용해서 그래프 구조 자체를 학습하는 방식으로 발전하고 있습니다. Pinterest, Uber Eats 같은 서비스의 추천 엔진이 GNN 기반으로 동작합니다.

 

4.2 네트워크 분석

소셜 네트워크 분석에서는 노드의 중요도를 측정하는 중심성(Centrality) 지표를 씁니다. 연결 중심성(Degree Centrality)은 연결된 엣지 수, 매개 중심성(Betweenness Centrality)은 다른 노드 쌍 사이의 최단 경로에 얼마나 많이 등장하는지를 나타냅니다. 어떤 사람이 네트워크에서 허브 역할을 하는지, 정보가 어떻게 퍼지는지 분석할 때 씁니다.

import networkx as nx

# networkx로 그래프 생성 및 분석
G = nx.Graph()
G.add_edges_from([
    ('A','B'), ('A','C'), ('B','D'),
    ('B','E'), ('C','F'), ('E','F')
])

# 중심성 분석
degree_centrality = nx.degree_centrality(G)
betweenness = nx.betweenness_centrality(G)

for node in G.nodes():
    print(f"{node}: 연결수={G.degree(node)}, "
          f"연결중심성={degree_centrality[node]:.2f}, "
          f"매개중심성={betweenness[node]:.2f}")

 

 

정리

그래프는 자료구조 중에서 가장 표현력이 넓습니다. 트리, 연결 리스트도 그래프의 특수한 형태이고, 현실 세계의 복잡한 관계 데이터는 대부분 그래프로 표현할 수 있습니다. 추천 시스템이나 네트워크 분석을 다룰 때 그래프 구조를 이해하고 있는 것과 모르는 것 차이가 꽤 납니다. networkx 라이브러리가 파이썬에서 그래프 분석을 시작하기 좋은 도구이니, 한 번 직접 소셜 네트워크 예제를 돌려보는 것을 추천합니다. 😊