우리가 SNS에서 접하게 되는 ‘친구 추천’ 기능은 단순한 우연이 아닙니다. 그 이면에는 ‘그래프 이론(Graph Theory)’이라는 강력한 수학적 도구가 숨어 있습니다. 그래프 이론은 네트워크 상의 관계와 연결을 수학적으로 모델링하고 분석하는 이론으로, 소셜미디어에서 친구 관계, 관심사, 상호작용을 기반으로 새로운 친구를 예측하는 데 핵심적으로 사용됩니다. 이번 글에서는 그래프 이론이 어떻게 SNS의 친구 추천 알고리즘에 활용되는지를 체계적으로 설명합니다.
SNS를 그래프로 모델링하기
SNS의 사용자들과 그들의 관계는 그래프에서 노드(node)와 엣지(edge)로 표현됩니다. 노드는 각각의 사용자이고, 엣지는 친구 관계, 팔로우, 좋아요 등 관계를 의미합니다.
예를 들어 사용자 A와 B가 친구라면, 두 노드 사이에 엣지가 존재하며, SNS 전체는 이처럼 수많은 사용자 노드와 관계 엣지가 얽힌 ‘사회 그래프(Social Graph)’가 됩니다. 이 그래프 구조를 분석하면 누가 누구와 연결될 가능성이 높은지를 수학적으로 추론할 수 있습니다.
공통 이웃 수 기반 추천
가장 기본적인 친구 추천 방식은 ‘공통 친구 수(Common Neighbors)’를 기준으로 합니다. 이 방식은 다음 논리를 따릅니다: “A와 B가 서로 공통된 친구를 많이 가질수록, 이 둘도 친구가 될 가능성이 높다.”
수학적으로는 다음과 같이 표현됩니다:
\[ score(A, B) = | \Gamma(A) \cap \Gamma(B) | \]
여기서 \(\Gamma(A)\)는 A의 친구 집합입니다. 이 방법은 단순하지만, 실제로 매우 직관적이고 효과적입니다.
자카드 유사도(Jaccard Similarity)
단순한 공통 친구 수는 모든 사용자가 동일한 기준으로 비교되기 때문에, 개인의 친구 수에 따라 불균형이 발생할 수 있습니다. 이를 보완하는 방법이 자카드 유사도입니다:
\[ J(A, B) = \frac{|\Gamma(A) \cap \Gamma(B)|}{|\Gamma(A) \cup \Gamma(B)|} \]
이는 공통 친구의 비율을 전체 친구 수로 나눈 값으로, 유사성이 상대적으로 높은 사용자를 추천하는 데 적합합니다.
Adamıc/Adar 지수: 희소한 친구를 더 높이 평가
친구 수가 적은 사람과의 연결은 더 큰 의미를 가질 수 있다는 가정에서 나온 방식입니다. 희소한 연결을 더 높게 평가하여 의미 있는 추천을 생성합니다.
\[ score(A, B) = \sum_{z \in \Gamma(A) \cap \Gamma(B)} \frac{1}{\log |\Gamma(z)|} \]
여기서 z는 공통 친구이며, 그 친구의 친구 수가 적을수록 점수가 높아집니다.
경로 기반 추천: 연결의 깊이를 고려
직접 연결된 친구뿐만 아니라, 경로(Path)를 통해 연결될 가능성이 높은 사람을 예측하는 방법도 있습니다. 특히 ‘2단계 친구'(friend of friend)는 친구 추천의 주요 대상이 됩니다.
이 때 그래프의 ‘최단 경로(shortest path)’, ‘랜덤 워크(random walk)’, ‘확산(diffusion)’ 개념이 활용됩니다. 예를 들어 랜덤 워크 방식에서는 임의의 노드에서 시작하여 무작위로 이동한 후 도달한 노드를 추천 대상으로 삼습니다.
링크 예측(Link Prediction) 알고리즘
그래프 이론에서는 아직 연결되지 않은 두 노드 사이의 연결 가능성을 예측하는 문제를 ‘링크 예측’이라고 부릅니다. 이 문제를 해결하기 위한 다양한 알고리즘이 있으며, SNS 친구 추천은 바로 이 링크 예측 문제의 실제 응용입니다.
링크 예측은 다음과 같은 요소들을 종합적으로 고려합니다:
- 공통 이웃 수
- 경로의 수와 길이
- 노드의 중심성
- 네트워크의 지역 구조
머신러닝 기반으로 학습된 모델은 이러한 지표를 조합하여 더욱 정교한 추천을 수행합니다.
하이퍼그래프와 다차원 관계의 분석
현대 SNS는 친구 관계 외에도 ‘좋아요’, ‘댓글’, ‘공유’, ‘태그’ 등 다양한 상호작용이 존재합니다. 이러한 복잡한 다중 관계를 분석하기 위해 ‘하이퍼그래프(Hypergraph)’ 또는 ‘멀티그래프(Multigraph)’ 구조가 사용되기도 합니다.
이 구조에서는 하나의 관계가 여러 노드를 동시에 연결하거나, 관계의 유형별로 구분된 그래프 계층을 구성해 추천 정확도를 향상시킵니다.
결론
그래프 이론은 SNS 친구 추천 알고리즘의 핵심 수학적 기반입니다. 사용자 간 관계를 노드와 엣지로 모델링함으로써, 공통 이웃, 유사도, 경로, 확률적 연결 등 다양한 방식으로 미래의 연결 가능성을 예측할 수 있습니다.
단순한 공통 친구 수부터 자카드 유사도, Adamic/Adar 지수, 링크 예측 알고리즘까지, 이러한 수학적 접근은 실제로 SNS 사용자 경험을 개선하고, 네트워크 성장을 가속화하는 데 기여하고 있습니다.
앞으로는 멀티그래프나 딥러닝 기반 그래프 신경망(GNN) 등을 통해 더욱 정교한 추천 시스템이 등장할 것이며, 이 모든 것은 그래프 이론을 바탕으로 작동합니다.