Webにおけるコミュニティの発見

概要

　近年、Webの拡大に伴って、ユーザがWeb上から必要な情報を見つけ出すこ とが困難になってきている。そこで、膨大な情報の中からユーザが 必要な情報を効率良く獲得するという目的で、Web上で形成されているコミュニティ（関心や興味を共有する人々によって作成されたWebページ集合）を発見する研究が注目されている。これまでに、Webページ間のリンク構造を解析してWebコミュニティを発見する様々な手法が提案されている。
　本研究では、ユーザから与えられたキーワードから、それに関連する複数のWebコミュニティを発見する手法を提案する。

従来手法

　ユーザから与えられたキーワードを入力として、そのキーワードに関連するWebコミュニティを発見する手法として、KleinbergのHITSアルゴリズム[1]がある。
　HITSアルゴリズムは、Webページ間のリンク関係を解析して、ユーザから与えられたキーワードに対する有用な情報(authorityとhubからなるWebコミュニティ）を抽出する。authorityとは、特定のトピックに関する情報が豊富であることを表す尺度で、hubはauhtorityとしての価値が高いページへのリンクが豊富であることを表す尺度である（図1）。一般的には、特定のトピックに関する優良サイトはauthorityの評価値が高くなり、優良リンク集はhubの評価値が高くなる。

図1：authorityとhubの関係（Webコミュニティ）

　各ページpのauthorityとhubの評価値は、以下の2式を反復することにより計算される。ここで、p→qはWebページpがqにリンクしていることを示す。また、数学的には、authorityとhubの値は、反復計算で固有値問題を解くことにより求められる。

従来手法の問題点

　図2,3は、クロスエントロピーに基づく可視化手法により、キーワード"apple"におけるコミュニティ抽出の対象となるWebグラフを可視化したものである。この手法では、「リンクで接続されているノードは近くに配置し、リンクで接続されていないノードは離して配置する」という考え方に基づいてグラフを可視化している。
　同図より、一般的なキーワード"apple"に対するWebグラフは、複数の密なリンク構造を持つWebページ集合（図2,3における赤枠の円）で構成されている。 また、これらのWebページ集合は、キーワードに関連するが、それぞれ異なるトピックを扱っていると考えられる。
　HITSアルゴリズムは、Webグラフにおいて、最も密なリンク構造を持つWebページ集合の一部（図2における青枠の円）をコミュニティとして1つだけ抽出する。従って、ユーザが意図するコミュニティを常に抽出できるとは限らない。
　例えば、キーワード"apple"は、アメリカのApple Computer社やフ ルーツのappleなど複数のトピックに関係している。しかし、HITSアルゴリズムでは、最も人気のあるトピックであるアメリカのApple Computer社に関するコミュニティだけが抽出され、フルーツのappleに関するコミュニティは抽出されない。

図2：キーワード"apple"に対するWebグラフ

　提案手法では、まずWebグラフをクラスタリングすることにより複数のクラスタを生成する。そして、生成された各クラスタに対してHITSアルゴリズムを適用することにより、複数のコミュニティ(図3における青枠の円)を抽出する。

図3：キーワード"apple"に対するWebグラフ

　ここで、Webグラフをクラスタリングするためのアルゴリズムには以下の性質が求められる。

1. クラスタ内部に多数のハイパーリンクを持ち、クラスタ間には少数のハイパーリンクしか持たない
2. 計算コストが低い

提案手法

　HITSアルゴリズムとその改善手法では、キーワードに対して単一のWebコミュニティしか抽出しないため、一般的なキーワードに対しては、ユーザが意図するコミュニティを抽出できない場合があるという問題点があった。
　そこで、本研究では、グラフクラスタリング手法のMarkov Cluster Algorithm[2]をHITSアルゴリズムと組み合わせることにより、ユーザから与えられたキーワードに関連する複数のWebコミュニティを抽出する手法を提案する。

　Markov Cluster Algorithmは、グラフ上のランダムウォークに基づいたシンプルなアルゴリズムで、パラメータが少ないという特徴がある。また、リンク情報(グラフの隣接行列)だけを利用してクラスタリングを行うため、テキスト情報を利用したクラスタリング手法に比べて、計算コストが低いという利点がある。


　本研究で提案するWebコミュニティ群発見手法は次の３つの手順から成る。アルゴリズムの詳細については、論文[1][2]を参照。

1. ユーザが入力したキーワードに関連するWebページ集合をネットワーク上から収集し、Webグラフを作成する。
2. Markov Cluster Algorithm（MCL）を用いて、Webグラフをクラスタリングする。
3. 生成された各クラスタ（部分グラフ）に対して、HITSアルゴリズムを適用することにより、複数のWebコミュニティ（上位authority,hubページの集合）を抽出する。

Web Community Viewer

　Web Community Viewerは、提案手法によって抽出されたWebコミュニティ群をトピックごとに分類して表示することで、ユーザが興味のあるトピックに関する情報を効率良く発見することを目的として開発したツールである（図4）。

図4：Web Community Viewer

　ツール上部のボックスには、キーワードおよびパラメータをセットする。左側のウィンドウには、クラスタの一覧リストが表示される（括弧内の数字は、クラスタに含まれるWebページ数）。右側のウィンドウには、左側のウィンドウで選択したクラスタに対するWebコミュニティの内容（authorityとhubの上位ページ）が表示される（赤字で記されている数字は、Webページのauthorityまたはhubの値）。
　また、Web Community Viewerはブラウザ機能を持っており、URLのリンクをクリックすることで、実際にWebページの内容を確認することができる。

評価

　提案手法の有効性を確認するために、一般的なキーワードに対してWebコミュニティを発見する実験を行った。以下に、キーワード"apple"に対する提案手法のauthority上位5件を示す（URL左の数値は、authority値）。 　

図5：1st Web Community

　１番目のコミュニティにおいては、第1位のauthorityは米Apple Computer社のホームペー ジとなり、第2位以降も同社の関連ページが続いた。即ち、トピック"Apple Computer"に関するコミュニティが抽出された。

図6：2nd Web Community

　２番目のコミュニティにおいては、第1位のauthorityはアメリカ・ワシントン州りんご協会のページ、第2位はアメリカ・ニューヨーク州りんご協会のページとなり、第3位以降もアメリカを中心としたりんごの関係機関となった。即ち、フルーツの"apple"に関するコミュニティが抽出された。

図7：3rd Web Community

　３番目のコミュニティにおい ては、米Apple Computer社が開発したパソコンappleIIのファンサイトや関連サイトが上位 authorityとして抽出され、トピック"appleII"に関するコミュニティとなっ た。


　提案手法では、"Apple Computer"、フルーツの"apple", "appleII"という3つのトピックに関連するコミュニティが抽出された。この結果から、キーワードに関連するコミュニティを１つだけしか抽出できないHITSアルゴリズムとその改善手法に比べて、効率の良い情報検索が可能となることが確認できる。

参考文献

[1] Authoritative Sources in a Hyperlinked Environment
J.Kleinberg, In Proceedings ACM-SIAM Symposium on Discrete Algorithms, 1998.
[2] Graph Clustering by Flow Simulation
Stijn van Dongen, PhD thesis, University of Utrecht, 2000.

論文

[1] Web情報検索におけるMarkov Cluster algorithmを用いたクラスタリング手法
加藤一民，松尾啓志，情報処理学会第67回全国大会講演論文集， 2005.3
[2] Markov Cluster Algorithmを用いたWebコミュニティ群の発見手法
加藤一民，松尾啓志，情報処理学会研究報告 2005-NL-166，2005.3