그래프 이론 (Graph Theory)
쉽게 풀면
지하철 노선도를 떠올려 보세요. 각 역은 하나의 "점"이고, 역과 역을 잇는 선로는 "선"입니다. 이렇게 여러 대상(점)과 그 사이의 관계(선)로 이루어진 구조를 그래프라고 부르고, 이 구조를 다루는 이론이 그래프 이론입니다. SNS 친구 관계, 도로망, 웹페이지 간 링크, 단백질 상호작용 네트워크까지 "무언가와 무언가가 연결되어 있다"는 상황이면 전부 그래프로 표현할 수 있습니다. 점을 정점(vertex/node), 선을 간선(edge)이라 부르며, 간선에 방향이 있는지(누가 누구를 팔로우하는지)와 없는지(친구 관계처럼 상호적인지)에 따라 방향 그래프와 무방향 그래프로 나뉩니다.
왜 중요한가
관계로 이루어진 데이터를 다루는 거의 모든 연구 분야, 즉 소셜 네트워크 분석, 생물학적 상호작용 네트워크, 지식 그래프, 통신망 설계 등은 결국 정점과 간선이라는 그래프 이론의 언어로 문제를 정의합니다. 최단 경로, 연결성, 중심성 같은 그래프 이론의 기본 개념이 확립되어 있기 때문에, 새로운 데이터를 그래프로 모델링하기만 하면 이미 존재하는 알고리즘과 이론적 결과를 곧바로 활용할 수 있다는 점에서 여러 응용 논문의 출발점이 됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 "사용자와 아이템을 각각 정점으로 놓고, 둘 사이의 상호작용(구매, 클릭 등)을 간선으로 표현한 그래프 구조를 사용했다"는 뜻입니다. 그래프 이론은 추천 시스템, 소셜 네트워크 분석, 지식 그래프, 분자 구조 모델링 등 관계 데이터를 다루는 거의 모든 분야의 기초로 쓰입니다.
생물정보학 연구에서 단백질 상호작용 네트워크를 그래프로 나타내고, 그래프 이론의 중심성 개념을 이용해 중요한 노드를 찾아내는 예시입니다.
네트워크 공학 연구에서 그래프의 연결성이라는 개념을 이용해 시스템의 견고함을 정량적으로 평가한 예시입니다.
조금 더 깊게 보면
그래프 이론에서는 정점의 개수와 간선의 개수, 두 정점을 잇는 최단 경로의 길이, 한 정점에 연결된 간선 수를 뜻하는 차수(degree) 등이 그래프의 구조를 정량적으로 나타내는 기본 지표로 쓰입니다. 또한 그래프가 얼마나 촘촘히 연결되어 있는지를 나타내는 밀도, 특정 노드가 전체 네트워크에서 얼마나 중요한 위치에 있는지를 나타내는 다양한 중심성(centrality) 지표도 논문에서 자주 함께 언급되므로, 이런 지표들이 어떤 그래프 특성을 수치화하는지 알아두면 도움이 됩니다.
주의할 점
그래프 이론에서 말하는 "그래프"는 막대그래프나 꺾은선그래프 같은 통계 그래프와 전혀 다른 개념입니다. 정점과 간선으로 이루어진 관계 구조를 뜻하므로, 논문에서 "그래프"라는 단어가 나오면 문맥을 보고 구별해야 합니다. 그래프 자체의 구조를 정의하는 이 개념과 달리, 그래프를 실제로 훑어가며 탐색하는 절차는 그래프 순회라는 별도의 개념으로 다룹니다.