이분 그래프(bipartite graph)는 정점들을 서로 겹치지 않는 두 개의 집합으로 나눌 수 있고, 모든 간선이 한쪽 집합의 정점과 다른 쪽 집합의 정점을 연결하는 그래프입니다.
예를 들어 AllElectronics의 고객 구매 데이터를 살펴보겠습니다. 한쪽 집합의 정점은 사용자를 나타내며(정점 하나당 사용자 한 명), 다른 쪽 집합의 정점은 제품을 나타냅니다(정점 하나당 제품 하나). 그리고 간선은 사용자와 제품을 연결하여, 해당 사용자가 그 제품을 구매했음을 의미합니다.
이러한 이분 그래프는 다양한 분야에서 실질적으로 활용되고 있습니다.
1. 웹 검색 엔진
웹 검색 엔진에서는 검색 로그를 저장하여 사용자의 검색 질의(query)와 이에 따른 클릭스루(click-through) 데이터를 기록합니다. 여기서 클릭스루 데이터란, 검색 결과로 제시된 페이지 중 사용자가 실제로 클릭한 페이지가 무엇인지를 알려주는 정보입니다.
이 질의와 클릭스루 데이터는 이분 그래프로 모델링할 수 있습니다. 두 정점 집합은 각각 '검색 질의'와 '웹 페이지'에 해당하며, 사용자가 어떤 질의를 입력했을 때 특정 웹 페이지를 클릭했다면 해당 질의와 웹 페이지 사이에 간선이 연결됩니다.
이렇게 구성된 질의–웹 페이지 이분 그래프에 군집 분석(cluster analysis)을 수행하면 매우 유용한 정보를 얻을 수 있습니다. 예를 들어, 서로 다른 언어로 작성되었지만 의미가 동일한 검색 질의들을 식별할 수 있습니다. 각 질의에 대한 클릭스루 데이터가 같다면, 그 질의들이 본질적으로 같은 의도를 담고 있다고 판단할 수 있기 때문입니다.
또한 웹상의 문서들은 방향 그래프, 즉 '웹 그래프(web graph)'를 형성합니다. 각 웹 페이지가 정점이 되고, 하이퍼링크는 출발 페이지에서 도착 페이지를 향하는 간선이 됩니다. 웹 그래프에 대한 군집 분석을 통해 온라인 커뮤니티를 파악하고, 허브(hub) 역할을 하는 페이지와 권위 있는(authoritative) 웹 페이지를 발견하며, 웹 스팸까지 식별할 수 있습니다.
2. 소셜 네트워크
소셜 네트워크(social network)는 일종의 사회적 구조로, 그래프로 표현할 수 있습니다. 정점은 사람이나 조직을 나타내며, 간선은 정점 간의 상호 의존 관계, 즉 우정, 공통의 관심사, 협력 활동 등을 나타냅니다.
AllElectronics의 사용자들 역시 하나의 소셜 네트워크를 형성합니다. 각 사용자는 정점이 되고, 두 사용자가 서로 아는 사이라면 두 정점 사이에 간선이 연결됩니다.
고객 관계 관리자의 입장에서는 군집 분석을 통해 AllElectronics의 소셜 네트워크에서 유용한 통찰을 얻는 데 큰 관심이 있을 것입니다. 네트워크에서 군집을 발견하면, 같은 군집에 속한 사용자들은 서로 아는 사이이거나 공통 친구를 두고 있는 경우가 많습니다.
이런 군집 내부의 사용자들은 구매 결정 과정에서 서로에게 상당한 영향을 미칠 수 있습니다. 나아가 각 군집의 '핵심 인물'에게 다가갈 수 있는 커뮤니케이션 채널을 구축하면, 홍보 정보를 네트워크 전반에 빠르게 확산시키는 마케팅 전략도 가능해집니다.
3. 가중 그래프로의 확장
소셜 네트워크는 가중 그래프(weighted graph)로 확장할 수도 있습니다. 예를 들어 학술 협업 네트워크에서 두 저자를 잇는 간선에는 협업의 강도를 나타내는 가중치를 부여할 수 있으며, 이 가중치는 두 저자가 함께 집필한 논문의 수로 정의할 수 있습니다. 이처럼 관계의 세기를 수치화하면, 단순한 연결 여부를 넘어 관계의 밀접함까지 분석에 반영할 수 있습니다.