WWW上の効率的な ハブ探索法の提案と実装

Presentation on theme: "WWW上の効率的な ハブ探索法の提案と実装"— Presentation transcript:

1 WWW上の効率的な ハブ探索法の提案と実装
北陸先端科学技術大学院大学 知識科学研究科 ○松久保 潤，林 幸雄

2 概要 有益なページを優先して収集 未探索かつ最大のIn-degreeをもつ ページを優先して収集 クローラによる探索実験
Webコミュニティ内の重要なページを 経由しながら探索しているように動作

3 背景 Webページの総数は急激に増加 Lawrence’99では約8億 山名’03では約70億 Googleの推定カバー率は約40%
すべてのページをカバーするのは困難 できるだけ有益なページを優先

4 多くの興味・関心を集めているページを できるだけ多く収集する
目的 オーソリティ Ａ ハブ Ｈ 高いIn-degreeをもつページは 多くの興味・関心を集めている 多くの興味・関心を集めているページを できるだけ多く収集する

5 従来法(1/2) Cho, et al ’98 更新されたページの再探索を効率化するため 高い重要度をもつページを優先して探索
ページの内容とIn-degreeやOut-degree 及びPageRankなどを組み合わせて評価 Web全体のリンク構造を使用

6 従来法(2/2) Adamic, et al ’00 無向グラフ上で任意の二頂点間の経路長が できるだけ短くなるように探索する
高い次数をもつ頂点を経由すると 任意の二頂点間の経路長が比較的短くなる 最大の次数をもつ最近傍を優先する 最近傍の正確な次数が既知である

7 提案手法 適宜，最大のIn-degreeをもつ 未探索ページを優先的に探索 発見された未探索ページが全て探索候補
探索の優先順位は適応的に変化 以下，本提案手法を入次数優先探索 (In-degree First Search; IFS)と表記

8 クローラの動作 探索URL pに探索開始URLを格納 pのソースのダウンロード・構文解析を行い URLを抽出
探索キューW内のURLと重複しない場合 Wに格納 重複する場合 そのURLの優先順位を更新 W内の最大のIn-degreeをもつURLをpに格納 ②に戻る

9 探索実験 入次数優先探索(In-degree First Search; IFS)
と幅優先探索(Breadth First Search; BFS) の比較 比較項目 オーソリティの累積獲得数 低い次数をもつページの累積獲得数

10 オーソリティだけでなくハブも効率的に収集
A及びHの累積獲得数 IFS BFS IFS BFS 図3 オーソリティの累積獲得数 図4 ハブの累積獲得数 IFSで収集したページがもつ次数の 上位0.1%に含まれる最小の次数 オーソリティだけでなくハブも効率的に収集

11 図6 低いOut-degreeをもつページの
次数の低いページの累積獲得数 IFS BFS IFS BFS 図5 低いIn-degreeをもつページの 累積獲得数 図6 低いOut-degreeをもつページの 累積獲得数 次数が低い頂点の累積獲得数が少ない

12 次数に対するページ数の分布 Pennock’02 特定のトピックを扱うページの分布が 対数正規分布に従う IFS BFS IFS BFS
図1 In-degreeに対するページ数 図2 Out-degreeに対するページ数 Pennock’02 特定のトピックを扱うページの分布が 対数正規分布に従う

13 最近傍の結合相関 nn k <kin > BFS IFS

14 コミュニティ間の移動の様子 IFS BFS IFSを用いた場合，A及びHが含まれるドメイン内の頁が 重点的に収集されている．

15 考察 Newman, et al ’03, Vázquez ’02 社会的ネットワークでは高い次数をもつ 頂点同士の結合頻度が高い
H コミュニティの核となるオーソリティやハブを 経由しながらWeb上を探索している

16 Þコミュニティの核となるオーソリティやハブを 経由しながらWeb上のページを収集
まとめ 探索中に適宜，最大のIn-degreeをもつ未探索ページを 優先して探索する手法を提案し，クローラを実装した 実験結果 幅優先探索を用いた場合よりも効率的に オーソリティを収集できた 収集したページのリンク構造上で高い次数をもつ ページ同士の結合頻度が高くなっていた Þコミュニティの核となるオーソリティやハブを 経由しながらWeb上のページを収集

17 最近傍の結合相関(Out-degree)
IFS BFS 入次数優先探索を用いた場合の方が 平均出次数が全体的に高くなっている

18 結果6:次数に対する最近傍の 平均次数(無向グラフ)
IFS BFS 図11 入次数優先探索を用いた場合 図12 幅優先探索を用いた場合 どちらの場合も高い入次数をもつページに対する最近傍の平均出次数が低くなる傾向がある 幅優先探索を用いた場合の方が上述の傾向が強い

19 クローラの実装 <A>のHREF属性， <META>の転送を 他のページへのリンクとして扱う
<FRAME SRC>で参照されるページ内の リンクは元のページからのリンクとして扱う 拡張子htm, html, asp, jsp, php, cfmをもつ ページへのURLをリンクとする 全てのcgi，及びhttp，https以外のプロトコルを用いるURLはリンクとして扱わない

20 クローラの実装 Wから最大の入次数をもつURLを取り出し pに格納する 探索URL pに探索開始URLを格納する
pを探索済みリストSに追加する pのソースをダウンロードする 構文解析を行ってS内のURLと重複しないように URLを抽出する 抽出されたURLが探索キューW内のURLと 重複する場合にそのURLの入次数を1だけ増やす 重複しない場合にはWに格納する Wから最大の入次数をもつURLを取り出し pに格納する ②に戻る