Kwangmin Kim - 그래프 이론 기초

1 그래프란 무엇인가

정의: 그래프 (Graph)

그래프 \(G = (V, E)\) 는 노드(vertex, node) 의 집합 \(V\) 와 엣지(edge) 의 집합 \(E \subseteq V \times V\) 로 구성된 수학적 구조이다.

\(V = \{v_1, v_2, \dots, v_n\}\) : 개체의 집합
\(E = \{(v_i, v_j) \mid v_i, v_j \in V\}\) : 개체 간 관계의 집합
\(|V| = n\) : 노드 수, \(|E| = m\) : 엣지 수

그래프는 “사물과 사물 사이의 관계”를 표현하는 가장 일반적인 수학적 도구이다. 소셜 네트워크의 친구 관계, 코드베이스의 함수 호출 관계, 도로망의 도시 간 연결 모두 그래프로 모델링할 수 있다.

[Module_A] --imports--> [Module_B] --imports--> [Module_C]
     │                                              │
     └──────────calls──────────────────────────────┘

직관적 이해

그래프는 지도 와 비슷하다. 도시(노드)와 도로(엣지)가 있으면 “서울에서 부산까지 갈 수 있는가?”, “최단 경로는?”, “가장 많은 도로가 연결된 도시는?” 같은 질문에 답할 수 있다. 코드베이스에서는 모듈(노드)과 의존관계(엣지)가 있으면 “모듈 A를 바꾸면 어디에 영향이 가는가?”에 답할 수 있다. 그래프 이론은 이런 질문에 수학적으로 정확하게 답하는 도구를 제공한다.

2 그래프의 유형

2.1 방향 유무에 따른 분류

유형	정의	엣지 표현	예시
무방향 그래프	엣지에 방향이 없음	\(\{v_i, v_j\}\)	소셜 네트워크의 친구 관계
방향 그래프 (Digraph)	엣지에 방향이 있음	\((v_i, v_j)\)	함수 호출 관계, 웹 링크

방향 그래프에서 \((v_i, v_j)\) 는 \(v_i \rightarrow v_j\) 를 의미하며, \(v_j \rightarrow v_i\) 와는 다르다. 코드베이스의 imports, calls 관계는 방향이 있으므로 방향 그래프로 모델링한다.

2.2 가중치 유무에 따른 분류

유형	정의	예시
비가중 그래프	모든 엣지의 가중치가 동일 (1)	모듈 간 의존 관계 (있다/없다)
가중 그래프	엣지에 가중치 \(w: E \rightarrow \mathbb{R}\) 부여	도시 간 거리, 호출 빈도, 유사도 점수

2.3 기타 유형

유형	정의	예시
이분 그래프 (Bipartite)	노드가 두 집합으로 분리, 같은 집합 내 엣지 없음	사용자-상품 추천, 함수-설정값 매핑
다중 그래프 (Multigraph)	같은 노드 쌍 사이에 복수 엣지 허용	두 모듈 간 imports + calls 동시 존재
속성 그래프 (Property Graph)	노드/엣지에 속성(키-값) 부여	Neo4j의 Labeled Property Graph
비순환 방향 그래프 (DAG)	방향 그래프이면서 순환 없음	Git 커밋 히스토리, 인과 그래프
트리 (Tree)	순환 없는 연결 그래프	파일 시스템, AST(추상 구문 트리)

속성 그래프: 실무의 표준

이론적으로는 \(G = (V, E)\) 로 충분하지만, 실무에서는 노드와 엣지에 속성 이 필수이다. “이 모듈의 언어는 Python이고 LOC는 450줄이다”와 같은 정보를 노드 속성으로 저장한다. Neo4j의 Labeled Property Graph 모델이 사실상 업계 표준이며, 온톨로지에서 프레임(Frame)과 동일한 구조이다 (Robinson et al., 2015).

3 핵심 용어

3.1 차수 (Degree)

노드 \(v\) 의 차수 \(\text{deg}(v)\) 는 연결된 엣지의 수이다.

방향 그래프에서는 진입 차수(in-degree) \(\text{deg}^{-}(v)\) 와 진출 차수(out-degree) \(\text{deg}^{+}(v)\) 를 구분한다
\(\text{deg}^{-}(v)\) 가 높은 노드: 많이 의존되는(critical) 모듈
\(\text{deg}^{+}(v)\) 가 높은 노드: 외부 의존이 많은(fragile) 모듈

악수 정리(Handshaking Lemma): 모든 노드의 차수 합은 엣지 수의 2배이다.

\[ \sum_{v \in V} \text{deg}(v) = 2|E| \]

이 정리가 실무에서 유용한 이유: 전체 의존 관계 수를 빠르게 추정할 수 있다. 예를 들어 40개 모듈의 평균 차수가 5라면, 전체 의존 관계는 약 \(40 \times 5 / 2 = 100\) 개이다.

3.2 경로 (Path)

노드 \(v_0\) 에서 \(v_k\) 까지의 경로 는 엣지로 연결된 노드의 시퀀스 \((v_0, v_1, \dots, v_k)\) 이다.

경로 길이: 경로에 포함된 엣지 수 \(k\)
단순 경로: 같은 노드를 두 번 방문하지 않는 경로
순환 (Cycle): 시작 노드와 끝 노드가 같은 경로 (\(v_0 = v_k\))

순환 의존성 탐지는 그래프에서 순환을 찾는 문제와 정확히 같다.

3.3 연결성 (Connectivity)

연결 그래프: 모든 노드 쌍 사이에 경로가 존재
강연결 (Strongly Connected): 방향 그래프에서 모든 노드 쌍 사이에 양방향 경로 존재
연결 요소 (Connected Component): 서로 연결된 노드들의 최대 부분집합

모듈 의존성 그래프에서 연결 요소가 여러 개이면, 독립적으로 배포 가능한 서비스 경계를 나타낼 수 있다.

3.4 강연결 요소 (Strongly Connected Components, SCC)

방향 그래프에서 모든 노드 쌍이 서로 도달 가능한 최대 부분 그래프 이다. 코드베이스에서 SCC는 곧 순환 의존성 그룹 을 의미한다. A→B→C→A가 순환이면 {A, B, C}가 하나의 SCC이다.

4 그래프의 표현 방법

4.1 인접 행렬 (Adjacency Matrix)

\(n \times n\) 행렬 \(\mathbf{A}\) 로, \(a_{ij} = 1\) 이면 \((v_i, v_j) \in E\) 이다.

\[ \mathbf{A} = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \]

위 행렬은 \(v_1 \rightarrow v_2\), \(v_1 \rightarrow v_3\), \(v_2 \rightarrow v_3\), \(v_3 \rightarrow v_4\) 를 의미한다.

특성	설명
공간 복잡도	\(O(n^2)\) — 노드 수가 많고 엣지가 희소하면 낭비
엣지 존재 확인	\(O(1)\) — 바로 조회 가능
이웃 탐색	\(O(n)\) — 한 행을 전부 스캔
행렬 거듭제곱	\(\mathbf{A}^k\) 의 \((i,j)\) 원소 = \(v_i\) 에서 \(v_j\) 까지 길이 \(k\) 경로의 수

\(\mathbf{A}^k\) 의 경로 해석은 선형대수와 그래프 이론의 핵심 연결점이다 (Strang, Ch.10).

4.2 인접 리스트 (Adjacency List)

각 노드에 대해 연결된 이웃 노드의 리스트를 저장한다.

graph = {
    "Module_A": ["Module_B", "Module_C"],
    "Module_B": ["Module_C"],
    "Module_C": ["Module_D"],
    "Module_D": []
}

특성	설명
공간 복잡도	\(O(n + m)\) — 실제 엣지 수에 비례, 희소 그래프에 효율적
엣지 존재 확인	\(O(\text{deg}(v))\) — 이웃 리스트를 순회
이웃 탐색	\(O(\text{deg}(v))\) — 직접 접근

대부분의 실무 그래프(코드베이스, 소셜 네트워크)는 희소하므로 인접 리스트가 더 효율적이다. Neo4j는 내부적으로 인덱스-프리 인접(index-free adjacency) 을 사용한다. 각 노드가 인접 노드로의 물리적 포인터를 직접 저장하여 \(O(1)\) 탐색을 제공한다 (Robinson et al., 2015, Ch.6).

5 그래프 탐색 알고리즘

5.1 너비 우선 탐색 (BFS, Breadth-First Search)

시작 노드에서 가까운 노드부터 방문한다. 큐(Queue)를 사용한다.

시작: A
큐: [A]

Step 1: A 방문 → 이웃 B, C 추가 → 큐: [B, C]
Step 2: B 방문 → 이웃 D 추가    → 큐: [C, D]
Step 3: C 방문 → 이웃 D (이미 큐) → 큐: [D]
Step 4: D 방문 → 완료

from collections import deque

def bfs(graph, start):
    """너비 우선 탐색: 시작 노드에서 도달 가능한 모든 노드를 반환한다."""
    visited = set()
    queue = deque([start])
    order = []

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

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": []
}
print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D']

특성	값
시간 복잡도	\(O(n + m)\)
공간 복잡도	\(O(n)\)
용도	최단 경로(비가중), 영향 범위 분석, 연결 요소 탐지

실무 적용: “모듈 A를 변경하면 영향받는 모든 모듈”을 찾는 것은 역방향 BFS이다. A를 import하는 모듈들을 시작점으로 BFS를 돌리면 전체 영향 범위가 나온다.

5.2 깊이 우선 탐색 (DFS, Depth-First Search)

한 방향으로 끝까지 탐색한 후 돌아와서 다음 경로를 탐색한다. 스택(Stack) 또는 재귀를 사용한다.

def dfs(graph, start, visited=None):
    """깊이 우선 탐색: 재귀 방식."""
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))
    return order

print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C']

특성	값
시간 복잡도	\(O(n + m)\)
공간 복잡도	\(O(n)\) (재귀 깊이)
용도	순환 탐지, 위상 정렬, 경로 열거

BFS vs DFS 선택 기준:

질문 유형	적합한 알고리즘	이유
“최단 경로는?”	BFS	가까운 노드부터 방문하므로 처음 발견이 최단
“경로가 존재하는가?”	둘 다 가능	도달 가능성만 확인
“모든 경로를 열거하라”	DFS	한 경로를 끝까지 추적 후 백트래킹
“순환이 있는가?”	DFS	백 엣지(back edge) 탐지

6 최단 경로 알고리즘

6.1 Dijkstra 알고리즘

가중 그래프에서 시작 노드로부터 모든 노드까지의 최단 거리를 구한다 (Robinson et al., 2015, Ch.7).

핵심 아이디어: “현재까지 알려진 최단 거리가 가장 짧은 노드”를 선택하여 이웃 노드의 거리를 갱신한다.

초기: dist[시작] = 0, dist[나머지] = ∞

반복:
  1. 미방문 노드 중 dist가 최소인 노드 u 선택
  2. u의 모든 이웃 v에 대해:
     if dist[u] + weight(u,v) < dist[v]:
       dist[v] = dist[u] + weight(u,v)
  3. u를 방문 처리

import heapq

def dijkstra(graph, start):
    """Dijkstra 최단 경로: graph = {node: [(neighbor, weight), ...]}"""
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))

    return dist, prev

# 예시: 가중 그래프
weighted_graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("D", 3)],
    "C": [("B", 1), ("D", 5)],
    "D": []
}
dist, prev = dijkstra(weighted_graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 2, 'D': 6}
# A→C→B→D (길이 6)가 A→B→D (길이 7)보다 짧다

특성	값
시간 복잡도	\(O((n + m) \log n)\) (우선순위 큐 사용 시)
제약	음수 가중치 불가
용도	물류 경로, 네트워크 라우팅, 가중 의존성 분석

A* 알고리즘

Dijkstra를 개선한 것으로, 목적지까지의 추정 비용(휴리스틱) \(h(n)\) 을 추가하여 불필요한 탐색을 줄인다. 평가 함수: \(f(n) = g(n) + h(n)\) 여기서 \(g(n)\) 은 시작점에서 \(n\) 까지의 실제 비용, \(h(n)\) 은 \(n\) 에서 목적지까지의 추정 비용이다. \(h(n) = 0\) 이면 Dijkstra와 동일하다 (Robinson et al., 2015, Ch.7).

7 중심성 지표 (Centrality Measures)

“가장 중요한 노드는?”이라는 질문에 답하는 지표이다.

7.1 차수 중심성 (Degree Centrality)

\[ C_D(v) = \frac{\text{deg}(v)}{n - 1} \]

가장 단순한 지표이다. 연결이 많은 노드가 중요하다고 본다. 코드베이스에서 진입 차수(in-degree)가 높은 모듈은 많은 모듈이 의존하는 핵심 모듈이다.

7.2 매개 중심성 (Betweenness Centrality)

\[ C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}} \]

\(\sigma_{st}\) : \(s\) 에서 \(t\) 까지의 최단 경로 수
\(\sigma_{st}(v)\) : 그 중 \(v\) 를 경유하는 수

“이 노드를 제거하면 네트워크가 얼마나 단절되는가”를 측정한다. 매개 중심성이 높은 모듈은 많은 의존 경로의 병목점이다. 이 모듈에 장애가 발생하면 광범위한 영향이 전파된다.

7.3 PageRank

Google의 웹 페이지 순위 알고리즘이다. 핵심 아이디어: 중요한 노드가 가리키는 노드도 중요하다.

\[ PR(v) = \frac{1-d}{n} + d \sum_{u \in \text{in}(v)} \frac{PR(u)}{\text{deg}^{+}(u)} \]

\(d\) : 감쇠 계수 (보통 0.85)
\(\text{in}(v)\) : \(v\) 를 가리키는 노드 집합

코드베이스에서 PageRank가 높은 모듈은 “중요한 모듈들이 의존하는 모듈”이다. 단순 진입 차수와 다른 점은, 누가 의존하느냐의 질 을 반영한다는 것이다.

def pagerank(graph, d=0.85, iterations=100):
    """단순 PageRank 구현."""
    nodes = list(graph.keys())
    n = len(nodes)
    pr = {node: 1 / n for node in nodes}

    # 역방향 그래프 구축
    in_edges = {node: [] for node in nodes}
    for node, neighbors in graph.items():
        for neighbor in neighbors:
            if neighbor in in_edges:
                in_edges[neighbor].append(node)

    for _ in range(iterations):
        new_pr = {}
        for node in nodes:
            rank_sum = sum(
                pr[src] / len(graph[src])
                for src in in_edges[node]
                if len(graph[src]) > 0
            )
            new_pr[node] = (1 - d) / n + d * rank_sum
        pr = new_pr

    return pr

graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": ["D"],
    "D": ["A"]
}
pr = pagerank(graph)
for node, rank in sorted(pr.items(), key=lambda x: -x[1]):
    print(f"{node}: {rank:.4f}")

8 그래프 이론의 예측 모델링 활용

8.1 삼자 폐합 (Triadic Closure)

Granovetter의 강한 삼자 폐합 속성: 노드 A가 B, C와 강한 관계를 가지면, B와 C 사이에도 관계가 형성될 가능성이 높다 (Robinson et al., 2015, Ch.7).

A ---강한--- B
|              ?
강한          약한 (높은 확률로 형성)
|              ?
C ------------

→ B-C 사이에 약한 연결이 형성될 가능성이 높다

코드베이스에서의 해석: 모듈 A가 모듈 B, C를 모두 import하면, B와 C 사이에도 직접 의존이 있을 가능성이 높다. 이를 통해 누락된 의존 관계를 예측할 수 있다.

8.2 지역 교량 (Local Bridge)

두 그룹 간의 유일한 소통 경로를 형성하는 약한 연결이다. 조직에서 정보 흐름의 병목점을 식별하는 데 사용된다. Granovetter의 “약한 연결의 힘(Strength of Weak Ties)”이 이 개념에 기반한다.

9 왜 필요한가: 응용 분야

분야	그래프 모델	핵심 연산
코드 분석	모듈/함수 → 노드, imports/calls → 엣지	영향도 분석(역방향 BFS), 순환 탐지(SCC)
지식 그래프	개체 → 노드, 관계 → 엣지	경로 추론, 링크 예측
GraphRAG	문서/엔티티 → 노드, 관계 → 엣지	다중홉 추론, 커뮤니티 탐지
소셜 네트워크	사용자 → 노드, 팔로우 → 엣지	추천(공통 이웃), 영향력(PageRank)
물류/경로	도시 → 노드, 도로 → 가중 엣지	최단 경로(Dijkstra), 최적 경로(A*)
인과 추론	변수 → 노드, 인과 관계 → 방향 엣지	DAG 구조 추론, d-separation
추천 시스템	사용자/상품 → 이분 그래프	협업 필터링, 그래프 임베딩

10 관련 주제

후속 주제

온톨로지 개론 — 그래프 위에 의미(semantics)를 부여하는 설계 사상
온톨로지와 메타데이터 저장소 설계 — RDB vs GraphDB 구현 비교
GraphRAG 개념과 최근 트렌드 — 그래프 이론의 RAG 응용

선행 지식

Ch.1 Introduction to Vectors — 벡터 공간 기초
Ch.2 §2.4 — Rules for Matrix Operations — 행렬 연산 (인접 행렬 이해를 위해)

다른 카테고리 연결

DAG와 인과 다이어그램 — 그래프 이론의 인과추론 응용
Neo4j GraphRAG Overview — Property Graph의 실무 구현

11 참고 문헌

Robinson, I., Webber, J. & Eifrem, E. (2015). Graph Databases, 2nd Edition, Ch.7
Brachman, R. & Levesque, H. (2004/2022). Knowledge Representation and Reasoning, Part 4
Kejriwal, M., Knoblock, C. & Szekely, P. (2021). Knowledge Graphs, Part 4