2部グラフの用途とは？Web検索やSNS分析への活用例を解説

2部グラフとは何か

2部グラフ（二部グラフ）とは、頂点を互いに素な2つの集合に分割できるグラフです。このとき、すべての辺は必ず一方の集合の頂点と、もう一方の集合の頂点を結びます。

AllElectronicsの顧客購買データを例にとると、一方の頂点集合は「ユーザー」を表し、各頂点が1人のユーザーに対応します。もう一方の集合は「製品」を表し、各頂点が1つの製品に対応します。そして、ユーザーと製品を結ぶ1本の辺は、「そのユーザーがその製品を購入した」という関係を示しています。

このような構造を持つ2部グラフには、実務でも役立つさまざまな応用分野があります。以下、代表的な活用例を紹介します。

2部グラフの主な応用例

Web検索エンジンでの活用

Web検索エンジンでは、検索ログがアーカイブされ、ユーザーの検索クエリと、それに対応するクリックスルーデータが保存されています。クリックスルーデータとは、検索結果として表示されたページのうち、ユーザーがどのページをクリックしたかを記録したものです。

このクエリとクリックスルーのデータは、2部グラフとして自然に表現できます。2つの頂点集合がそれぞれ「クエリ」と「Webページ」に対応し、ユーザーが特定のクエリを入力した際にあるWebページをクリックすれば、そのクエリとページをつなぐ辺が張られます。

このクエリ・Webページ間の2部グラフに対してクラスタ分析を行うことで、価値ある知見を得ることができます。たとえば、言語は異なるものの意味が同じである複数のクエリを、クリックスルーパターンが類似していることに着目して特定できます。

また、Web上のページ群は「Webグラフ」と呼ばれる有向グラフとして捉えることもできます。各Webページが頂点となり、各ハイパーリンクが発信元ページからリンク先ページへ向かう辺となります。このWebグラフに対するクラスタ分析によって、コミュニティの検出、ハブページや権威あるページの発見、さらにはWebスパムの識別まで可能になります。

ソーシャルネットワーク分析での活用

ソーシャルネットワークとは社会的構造の一種であり、グラフとして定義できます。頂点は個人または組織を表し、頂点同士をつなぐ接続は、友情、共通の関心、協力活動といった相互依存関係を表します。

AllElectronicsの利用者も一つのソーシャルネットワークを形成しており、各ユーザーが頂点となり、互いに知り合いであるユーザー同士が辺で結ばれています。

顧客関係管理の担当者にとっては、AllElectronicsのソーシャルネットワークに対するクラスタ分析を通じて、有用な情報を発見することが重要です。分析により、互いに顔見知りである、あるいは共通の友人を持つユーザーからなるクラスタを抽出できます。

同一クラスタ内のユーザーは、購買意思決定の際に互いに影響を及ぼし合う傾向があります。さらに、各クラスタの「中心的存在（ヘッド）」に働きかけるためのコミュニケーション経路を構築すれば、プロモーション情報を短期間で広く浸透させることができます。

重み付きグラフとしての拡張

ネットワークは重み付きグラフとして扱うこともできます。たとえば、2人の著者をつなぐ辺に重みを持たせ、共著論文の本数など、両者の共同作業の強さを数値化できます。これにより、単なる「つながりの有無」ではなく、つながりの濃淡を考慮したより精緻な分析が可能になります。