그래프 이론(Graph Theory)이란 무엇인가, 소셜 네트워크부터 GNN까지

카카오톡 친구 추천이 어떻게 작동하는지 생각해 본 적 있나요. 내가 A를 알고, A가 B를 알면 나와 B가 "아는 사람"이 될 가능성이 높습니다. 페이스북, 링크드인의 "알 수도 있는 사람" 기능이 이 원리로 작동합니다. 관계를 수학적으로 표현하고 분석하는 게 그래프 이론입니다.

그래프 이론이 흥미로운 건 적용 범위가 소셜 네트워크에 그치지 않는다는 점입니다. 구글 검색 순위, 물류 최적화, 금융 사기 탐지, 신약 개발, 자율주행 경로 탐색까지 모두 그래프 이론 위에서 작동합니다. 오늘은 노드와 엣지라는 단순한 개념이 어떻게 이 모든 문제를 해결하는지 따라가 보겠습니다.

그래프 이론(Graph Theory)과 소셜 네트워크, 관계를 데이터로 표현하는 수학

📌 목차

• 그래프란 무엇인가 — 노드와 엣지로 세상을 표현하기
• 인접 행렬 — 그래프를 컴퓨터가 이해하는 숫자로
• 중심성 지표 — 네트워크의 핵심 인물 찾기
• 페이지랭크 — 구글이 웹페이지 순위를 매기는 방법
• 그래프 신경망(GNN) — 관계를 학습하는 AI
• 그래프 이론의 실무 활용

그래프란 무엇인가 — 노드와 엣지로 세상을 표현하기

그래프는 노드(Node)와 엣지(Edge)로 구성됩니다. 노드는 분석 대상, 엣지는 관계입니다. 단순한 정의지만 적용 범위가 엄청납니다.

소셜 네트워크: 노드=사람, 엣지=친구 관계
웹: 노드=웹페이지, 엣지=하이퍼링크
물류: 노드=도시, 엣지=도로(가중치=거리)
생물학: 노드=단백질, 엣지=상호작용
금융: 노드=계좌, 엣지=송금 내역
뇌과학: 노드=뉴런, 엣지=시냅스 연결

엣지의 종류도 중요합니다. 카카오톡 친구는 A가 B를 추가하면 B도 A의 친구가 됩니다. 양방향(Undirected) 그래프입니다. 인스타그램 팔로우는 내가 상대를 팔로우해도 상대가 나를 안 팔로우할 수 있습니다. 단방향(Directed) 그래프입니다. 여기에 가중치(Weight)까지 더하면 관계의 강도도 표현할 수 있습니다. 전화 통화 횟수, 송금 금액, 거리 같은 것들이죠.

---

인접 행렬 — 그래프를 컴퓨터가 이해하는 숫자로

그림으로 그린 그래프는 사람이 이해하기 좋지만 컴퓨터가 계산하려면 숫자로 변환해야 합니다. 인접 행렬(Adjacency Matrix)이 그 역할을 합니다. 노드를 행과 열에 배치하고 연결되어 있으면 1, 없으면 0을 넣습니다.

4명(A, B, C, D)의 소셜 네트워크:
A-B 연결, A-C 연결, B-D 연결, C-D 연결

인접 행렬:
   A B C D
A [0, 1, 1, 0]
B [1, 0, 0, 1]
C [1, 0, 0, 1]
D [0, 1, 1, 0]

행렬 A² = A × A 계산하면:
→ 2단계 이내에 도달 가능한 노드 수를 알 수 있다
→ A에서 D까지 친구의 친구로 갈 수 있는지 계산 가능

인접 행렬로 변환하는 순간 그래프 이론이 선형대수학의 영역으로 들어옵니다. 행렬 거듭제곱으로 몇 단계를 거쳐야 특정 노드에 도달하는지 계산하고, 고윳값 분해로 네트워크의 핵심 구조를 파악합니다. 이 연재에서 다룬 행렬 연산과 고윳값이 그래프 분석의 핵심 도구가 됩니다.

---

중심성 지표 — 네트워크의 핵심 인물 찾기

소셜 네트워크 분석의 핵심 질문은 "이 네트워크에서 가장 영향력 있는 노드는 누구인가?"입니다. 그래프 이론은 이를 중심성(Centrality) 지표로 측정합니다. 목적에 따라 다른 중심성을 씁니다.

1. 연결 중심성 (Degree Centrality)
직접 연결된 노드 수
→ 친구가 가장 많은 사람, 팔로워 수

2. 매개 중심성 (Betweenness Centrality)
다른 노드들 사이의 최단 경로에 얼마나 자주 등장하는가
→ 정보 흐름의 병목점, 브로커 역할

3. 근접 중심성 (Closeness Centrality)
다른 모든 노드까지의 평균 거리가 짧은 정도
→ 소문이 가장 빨리 퍼지는 사람

4. 고유벡터 중심성 (Eigenvector Centrality)
연결된 노드들의 중요도를 반영
→ 중요한 사람을 많이 아는 사람 (PageRank의 기반)

마케팅에서 인플루언서를 찾을 때는 팔로워 수(연결 중심성)보다 매개 중심성이 더 중요할 수 있습니다. 팔로워가 적어도 서로 다른 커뮤니티를 연결하는 사람이 정보 확산에 훨씬 효과적이기 때문입니다. 코로나 확산 경로 분석, 조직 내 정보 병목 파악에도 이 지표들이 쓰입니다.

---

페이지랭크 — 구글이 웹페이지 순위를 매기는 방법

구글 창업자 래리 페이지와 세르게이 브린이 1998년에 만든 페이지랭크(PageRank) 알고리즘은 그래프 이론의 가장 유명한 성공 사례입니다. 웹페이지를 노드, 하이퍼링크를 엣지로 보는 방향 그래프입니다.

PageRank 핵심 아이디어:

단순히 링크 수만 세지 않는다
→ 링크를 보내는 페이지의 중요도도 반영

수식: PR(A) = (1-d)/N + d × Σ PR(B)/L(B)

d: 감쇠 계수 (보통 0.85)
PR(B): B 페이지의 PageRank 점수
L(B): B가 가진 총 링크 수

예시:
뉴욕타임즈(중요 페이지)가 내 블로그를 링크
→ 내 블로그 PageRank 크게 올라감

무명 사이트 100개가 내 블로그를 링크
→ 뉴욕타임즈 하나보다 효과 적을 수 있음

페이지랭크는 수학적으로 고유벡터 중심성의 응용입니다. 반복 계산으로 각 페이지의 점수가 수렴할 때까지 업데이트합니다. "내가 누구를 아느냐보다 누가 나를 아느냐가 가치를 결정한다"는 원리가 현대 인터넷 검색의 기반이 됐습니다.

---

그래프 신경망(GNN) — 관계를 학습하는 AI

딥러닝이 이미지(격자 구조)와 텍스트(선형 구조)에 특화되어 있다면, 그래프 신경망(GNN, Graph Neural Network)은 불규칙하게 얽힌 관계 자체를 학습합니다.

GNN의 핵심 아이디어는 메시지 패싱(Message Passing)입니다. 각 노드가 자신과 연결된 이웃 노드들의 정보를 수집해서 자신의 표현을 업데이트합니다. 이 과정을 여러 층에 걸쳐 반복하면 멀리 있는 노드의 정보도 간접적으로 반영됩니다.

GNN 메시지 패싱:

h_v^(k) = UPDATE(h_v^(k-1), AGGREGATE({h_u : u ∈ N(v)}))

h_v: 노드 v의 표현 벡터
N(v): v의 이웃 노드 집합
k: 레이어 번호 (깊어질수록 더 먼 이웃 반영)

활용 사례:
신약 개발: 분자 구조(원자=노드, 결합=엣지)에서 특성 예측
금융 사기: 거래 패턴 그래프에서 이상 거래 탐지
추천 시스템: 사용자-아이템 이분 그래프 학습
SNS: 가짜 계정 탐지, 커뮤니티 감지

---

그래프 이론의 실무 활용

그래프 이론은 이론적 도구에 그치지 않고 실제 제품과 서비스에 깊숙이 들어와 있습니다.

분야	핵심 알고리즘	활용 방식
검색 엔진	PageRank	웹페이지 중요도 순위 산정
SNS	Link Prediction, GNN	친구 추천, 가짜 계정 탐지
물류/내비게이션	Dijkstra, A*	최단 경로 탐색
금융	이상 탐지 GNN	사기 거래 패턴 탐지
신약 개발	분자 GNN	분자 구조에서 약효 예측
추천 시스템	이분 그래프 GNN	사용자-아이템 관계 학습

이 연재에서 다룬 행렬 연산, 고유값, 선형대수학이 그래프 이론의 핵심 도구입니다. 인접 행렬의 고윳값 분해로 네트워크 구조를 파악하고, 행렬 곱셈으로 다단계 연결을 계산합니다. 데이터를 표 형태로 보는 것을 넘어 관계 자체를 데이터로 보는 시각이 그래프 이론이 주는 가장 큰 통찰입니다.