Clique: 그래프 이론 개념을 데이터 분석에 활용하기

Context

여러 데이터 소스 결과를 합쳐서 n~m개로 구성된 상품 세트를 추출하는 파이프라인을 설계하다가, clique를 활용하는 방법을 써봤다. CS 교재에서만 보던 개념이 실전 데이터 분석에 이렇게 쓰일 수 있다는 게 신기했다.

What I Learned

Clique란 그래프에서 모든 노드 쌍이 서로 연결된 완전 부분 그래프(complete subgraph)다. 즉, 클리크 안의 모든 노드는 서로 edge로 이어져 있다.

A - B
|\ /|
| X |   → {A, B, C, D}가 clique
|/ \|
C - D

상품 세트 추출에 적용한 파이프라인

Pair 추출 — 각 데이터 소스(예: 구매 이력, lift 분석 등)에서 함께 등장하는 상품 쌍(pair)을 추출
그래프 구성 — 강한 연관성을 가진 pair를 edge로 연결해 그래프 생성
k-clique 탐색 — 크기 k인 clique를 찾아 “서로 강하게 연관된 상품 묶음” 후보 도출
Hybrid 검증 — clique 후보를 실데이터로 검증해 최종 세트 확정

왜 clique인가

단순히 “같이 자주 팔린 상품”을 모으면 약한 연결이 섞여들 수 있음
clique는 그룹 내 모든 쌍이 강하게 연결되어 있음을 보장 → 세트로서의 응집도가 높음
n~m개 범위의 세트를 추출할 때 k값을 조절해 크기 조건을 자연스럽게 적용할 수 있음

Note

그래프 이론 알고리즘이 CS 이론에서만 쓰이는 게 아니라 실제 데이터 파이프라인 설계에도 유용하게 쓰인다. clique 탐색은 NP-hard 문제라 데이터가 커지면 근사 알고리즘이 필요하지만, 실전에서는 후보를 먼저 좁혀두고 검증하는 Hybrid 방식으로 충분히 쓸 만하다.