リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究 2006年度 WINGS発表 リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究 発表者　佐々木　雄一

１．背景 WWW上には膨大な量のページ ・ 文書検索エンジンの問題 文書検索で目的にたどり着くのは難しい！ query 検索エンジン ・　文書検索エンジンの問題 query 検索エンジン answer 1 2 3 約11.5億 query 検索エンジン answer 1 2 3 4 5 6 7 ： 1万 膨大な 検索結果 文書検索で目的にたどり着くのは難しい！

１．背景 膨大な量のページをどう扱うか? どのようにWebページからグループを構成するか? ・ グループ化を行う 本研究では について扱う． ・　グループ化を行う Webページ グループ化 システム input グループB output グループA グループC 検索文字列以外の類似情報 情報の位置づけ 本研究では どのようにWebページからグループを構成するか? について扱う．

2．研究概要 ベクトル空間法 本論文ではリンク構造も考える ベクトル空間法はリンク構造を考えていない Webページからの自動的なグループ構成を行うための一般的手法 文書内容の類似度を計算する方法 ベクトル空間 文書di 2つのベクトルのコサインを計算 [x1,x2,…,xn] di [x1,x2,…,xn] θが近いほど類似 文書dj dj θ [y1,y2,…,yn] [y1,y2,…,yn] 文書内の単語の頻度 ベクトル空間法はリンク構造を考えていない 本論文ではリンク構造も考える

発表の流れ 関連研究 提案手法 実装 実験 おわりに

3．関連研究 リンク構造からのコミュニティ抽出に関する研究 リンクと文書両方の情報を用いたクラスタリング手法に関する研究 参照の共起性に基づくWebコミュニティ発見手法 [村田 01] リンクと文書両方の情報を用いたクラスタリング手法に関する研究 リンクと文書両方を考慮に入れたクラスタリングサーチエンジンHyPursuit [Weiss 96] 巨大なネットワークからのコミュニティ抽出に関する研究 ネットワーク分割に関する評価値Modularity Q を応用した高速コミュニティ発見手法 [Clauset 04]

4．提案手法 リンク構造も考慮に入れたベクトル空間法 : : : : ×α ×(1-α) Content-Linkベクトル どのように扱うのか? 文書の内容 リンク構造 文書ベクトル リンクベクトル [x1,x2,…,xn] [e1,e2,…,en] [y1,y2,…,yn] [f1,f2,…,fn] ×α ×(1-α) : : : : [z1,z2,…,zn] [g1,g2,…,gn] Content-Linkベクトル

4．提案手法 どのようにリンクベクトルを扱うのか? 村田の手法におけるWebコミュニティ 適切にリンクを用いてグループ構築ができなければならない 村田の手法の完全二部グラフ構造を拡張利用 村田の手法におけるWebコミュニティ 熱心な支持者(fans)から共通に張られているリンクを利用 fansから形成される完全二部グラフ構造をWebコミュニティとして抽出 完全二部グラフ構造 Webコミュニティ fans

4．提案手法 完全二部グラフ構造からのWebコミュニティ抽出の限界 完全二部グラフ構造という制約を緩和する必要がある 完全二部グラフ構造という制約が厳しい 現実のWebコミュニティは様々なリンク構造をもっている 完全二部グラフ構造 完全二部グラフ構造 Webコミュニティ Webコミュニティ fans fans 完全二部グラフ構造という制約が厳しい 完全二部グラフ構造という制約を緩和する必要がある

4．提案手法 リンクベクトルと完全二部グラフ構造 p1はfansからリンクを1つ介した位置にある fans Webコミュニティ p1はfansからリンクを1つ介した位置にある b1 p1 b2 fans p2 piはfansのページbjからリンクを1つ介しているという情報が与えられる b3 p3 b4 piはfansのページbjからリンクに関する情報が与えられ　　リンクベクトル　　　　　　　　　 をもつ リンクベクトル p1 [1, 1, 1, 1] すべて類似度最大 p2 [1, 1, 1, 1] p3 [1, 1, 1, 1] 完全二部グラフをもつWebコミュニティの類似性はリンクベクトルでも評価可能 リンクベクトルはすべて同じ向き

完全二部グラフの構造を引継ぎ，さらに柔軟に解釈できる 4．提案手法 完全二部グラフ構造を柔軟に解釈したWebコミュニティ抽出 b1,b2,b3,b4からをリンクを1つ介している [1, 1, 1, 1] b1 p1 [1, 1, 1, 1] b2 fansから与えられるリンクベクトル fans p2 b3 p3 b4 [1, 1, 1, 2] b4からをリンクを2つ介している 得られる類似度の表 p1 p2 p3 ― 1.0 0.945 p1とp2は酷似している p1とp3はp1とp2に比べて似ていない リンクベクトルを用いることで 完全二部グラフの構造を引継ぎ，さらに柔軟に解釈できる

4．提案手法 基準ページの配置 p1とp3の類似度が1 p1とp2とp3はWebコミュニティを構成 様々な位置に基準ページを配置 基準ページの問題 同じ向き b5 基準ページ [1, 1, 1, 1] b8 [2, 2, 2, 2] b1 p1 b2 p3 b1 fans p2 p1 b3 b2 p3 p2 b4 b3 p1とp3の類似度が1 b4 b7 本当? b6 p1とp2とp3はWebコミュニティを構成 多くの視点を基にグループ構築を判断することができる 完全二部グラフを与えるようなWebページだけを基点にするのは適切ではない

4．提案手法 リンクベクトルの提案 リンクベクトル pi = bj のときfn(pi,bj)=0とし 基準ページもリンクベクトルの式に含む 1 リンクベクトルの提案 b 1 1 1 Webページpi，基準ページbj 基準ページの総数k個 bjからpiに到達するまで辿る最短のリンクの数fn(pi,bj) 1 4 2 2 2 3 3 3 3 リンクベクトル 3 pi = bj のときfn(pi,bj)=0とし 基準ページもリンクベクトルの式に含む

4．提案手法 リンクベクトルのカスタマイズ 標準リンクベクトル リンク介した数を要素をとしてもつリンクベクトル 標準リンクベクトル　リンク介した数を要素をとしてもつリンクベクトル score 1 score 2 +1 1つリンクを介す度にベクトルの構成要素が1ずつ加算される score 3 +1 +1 カスタマイズ1　リンクの次数を考慮に入れた要素をもつリンクベクトル score x score x + (1/ki+1/kj) 次数が高いほどリンクを介する加算値が小さくなる コミュニティの周りのページがグループを構成しやすくなる 次数重みベクトルと呼ぶことにする +(1/ki+1/kj) 複数のスコアが与えられるような状況の場合，スコアはその中の最小の値をとる． 次数kj 次数ki カスタマイズ2　リンクを介した数に重みをつけたリンクベクトル リンクを辿るほど加算値が小さくなる リンクを辿る数を少なくしてもグループ構成への影響を小さくできる 距離重みベクトルと呼ぶことにする score 1 score 1+r score 1+r+r2 +r2 +r r < 1.0 +r2

5．実装 リンク構造からグループを構築するための実装 実装言語はJavaで， グラフ構造を扱うためJavaパッケージのJUNGを使用した 提案手法の実装 　　‐　リンクベクトルの実装 　　‐　カスタマイズされたリンクベクトルの実装 クラスタリング手法の実装 　　‐　初歩的な階層クラスタリング手法である単連結法と完全連結法の実装 単連結法 完全連結法 最も類似した頂点を併合に用いる 最も類似していない頂点を併合に用いる

6．実験 実験設定 リンクベクトルがWebページに対してどのようなグループ構成をするのかを調べる 実験に使う手法 単連結法を用いた距離重みなしベクトル 単連結法を用いた次数重みベクトル 単連結法を用いてr=0.8としたときの距離重みベクトル 　完全連結法を用いた距離重みなしベクトル 距離重みなしベクトルとは，標準のリンクベクトルと同じ

6．実験 実験設定 実験対象のデータ アメリカの政治に関するブログのリンク構造データ その他の実験設定 1490のWebページのリンク構造に関するデータをもつ 1490のページのうち，758個が民主党，732個が共和党寄りのWebページ 91%のリンクは同一コミュニティと結びついている その他の実験設定 200個のWebページが併合される毎に，サイズ10以上のグループのデータを記録した すべてのWebページを基準ページとした

6．実験 実験結果１ 単連結法を用いた距離重みなしリンクベクトルから得られる結果 併合ページ数200 併合ページ数600 併合ページ数769 民主の数 共和の数 民主の数 共和の数 民主の数 共和の数 24 1 212 7 316 9 22 2 5 214 10 413 11 1 15 68 15 2つのメイングループが併合され1つになる直前 11 12 民主党のグループができた リンクベクトルを用いることで民主党，共和党のどちらかが大半を占めるグループが構成された 良い 混在するグループができた 悪い

6．実験 実験結果2(カスタマイズ手法との比較) 2つのメイングループが併合されるまでのページ併合数 max 距離重みなしベクトル 次数重みベクトル 距離重みベクトル 併合ページ数769 併合ページ数441 併合ページ数661 民主の数 共和の数 民主の数 共和の数 民主の数 共和の数 147 62 316 9 262 14 11 108 9 334 21 30 10 413 17 10 10 次数重みベクトルを用いることにより，ハブ構造をもつWebページ同士の類似度が大きくなり，メイングループの構成要素であるハブ構造をもったWebページがつながったため生じた． 距離重みなしベクトル　769 max 同一コミュニティに属するWebページをより多く含んでいる 次数重みベクトル　441 距離重みベクトル　661 次数重みベクトルでは早い段階でメイングループが併合した 原因 異なるコミュニティに属するハブ構造をもつWebページ同士の類似度が高くなったため

6．実験 実験結果2(カスタマイズ手法との比較) 距離重みなしベクトルと距離重みベクトルの比較 ページ併合数 距離重みなしベクトル r=0.8とした距離重みベクトル 民主の数 共和の数 民主の数 共和の数 400 32 2 65 1 30 1 33 2 2 112 2 149 600 212 7 241 10 5 214 5 247 r=0.8の距離重みベクトルは距離重みなしベクトルに比べて大きなグループを構成した 原因 リンクを辿るほどリンクベクトルのスコアの特徴が失われたため

6．実験 実験結果3(単連結法と完全連結法の比較) ■ 単連結法と完全連結法の特徴を強く示した結果が得られた ■　単連結法と完全連結法の特徴を強く示した結果が得られた － 単連結法の特徴　大きなグループがさらに大きなグループを構築しやすくなる － 完全連結法の特徴　大きなグループ同士が結びつきにくくなり，過剰にグループができる ページ併合数 単連結法が構成する グループ数 完全連結法が構成する 200 5 4 400 7 600 13 800 1 22 989 ■　完全連結法では最後の方まで2つのメイングループは併合されなかった 2つのメイングループが併合されるまでのページ併合数 単連結法　769 同一コミュニティに属するWebページを十分含んでいる max 完全連結法　960 実験では最も良い結果を得ている

6．実験 実験結果4(単連結法と完全連結法の比較) メイングループが1つになる直前 単連結法を用いた実験結果 完全連結法を用いた実験結果 　メイングループが1つになる直前 －　四角は民主党，丸は共和党を表す －　同じ色は同一グループを表す 単連結法を用いた実験結果 完全連結法を用いた実験結果

7．おわりに まとめ Content-Linkベクトル提案 リンクベクトルの設計 リンクベクトルのカスタマイズ 　リンクベクトルのカスタマイズ 　Webページのリンク構造への実験と考察

7．おわりに 今後の課題 計算量の改善 基準ページの選択とWebページのグループ構成への影響に関する実験調査 クラスタリング手法の検討 　計算量の改善 　基準ページの選択とWebページのグループ構成への影響に関する実験調査 　クラスタリング手法の検討 　他手法との実験比較 　文書内容の導入 　多くのデータに対する応用 　コンテンツ内容の調査