困難になってきている。必要な情報を効率良く獲得するという目的で、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など複数のトピックに関係している。Computer社に関するコミュニティだけが抽出され、フルーツのappleに関するコミュニティは抽出されない。図2:キーワード"apple"に対するWebグラフ提案手法では、まずWebグラフをクラスタリングすることにより複数のクラスタを生成する。生成された各クラスタに対してHITSアルゴリズムを適用することにより、複数のコミュニティ(図3における青枠の円)を抽出する。図3:キーワード"apple"に対するWebグラフここで、Webグラフをクラスタリングするためのアルゴリズムには以下の性質が求められる。クラスタ内部に多数のハイパーリンクを持ち、クラスタ間には少数のハイパーリンクしか持たない計算コストが低い提案手法HITSアルゴリズムとその改善手法では、キーワードに対して単一のWebコミュニティしか抽出しないため、一般的なキーワードに対しては、ユーザが意図するコミュニティを抽出できない場合があるという問題点があった。Algorithm[2]をHITSアルゴリズムと組み合わせることにより、ユーザから与えられたキーワードに関連する複数のWebコミュニティを抽出する手法を提案する。Algorithmは、グラフ上のランダムウォークに基づいたシンプルなアルゴリズムで、パラメータが少ないという特徴がある。リンク情報(グラフの隣接行列)だけを利用してクラスタリングを行うため、テキスト情報を利用したクラスタリング手法に比べて、計算コストが低いという利点がある。本研究で提案するWebコミュニティ群発見手法は次の3つの手順から成る。アルゴリズムの詳細については、論文[1][2]を参照。ユーザが入力したキーワードに関連するWebページ集合をネットワーク上から収集し、Webグラフを作成する。Algorithm(MCL)を用いて、Webグラフをクラスタリングする。生成された各クラスタ(部分グラフ)に対して、HITSアルゴリズムを適用することにより、複数のWebコミュニティ(上位authority,hubページの集合)を抽出する。Viewerは、提案手法によって抽出されたWebコミュニティ群をトピックごとに分類して表示することで、ユーザが興味のあるトピックに関する情報を効率良く発見することを目的として開発したツールである(図4)。Viewerツール上部のボックスには、キーワードおよびパラメータをセットする。左側のウィンドウには、クラスタの一覧リストが表示される(括弧内の数字は、クラスタに含まれるWebページ数)。右側のウィンドウには、左側のウィンドウで選択したクラスタに対するWebコミュニティの内容(authorityとhubの上位ページ)が表示される(赤字で記されている数字は、Webページのauthorityまたはhubの値)。Viewerはブラウザ機能を持っており、URLのリンクをクリックすることで、実際にWebページの内容を確認することができる。提案手法の有効性を確認するために、一般的なキーワードに対してWebコミュニティを発見する実験を行った。以下に、キーワード"apple"に対する提案手法のauthority上位5件を示す(URL左の数値は、authority値)。ジとなり、第2位以降も同社の関連ページが続いた。Computer"に関するコミュニティが抽出された。Community2番目のコミュニティにおいては、第1位のauthorityはアメリカ・ワシントン州りんご協会のページ、第2位はアメリカ・ニューヨーク州りんご協会のページとなり、第3位以降もアメリカを中心としたりんごの関係機関となった。フルーツの"apple"に関するコミュニティが抽出された。"appleII"という3つのトピックに関連するコミュニティが抽出された。この結果から、キーワードに関連するコミュニティを1つだけしか抽出できないHITSアルゴリズムとその改善手法に比べて、効率の良い情報検索が可能となることが確認できる。