WWW上の効率的な ハブ探索法の提案と実装 北陸先端科学技術大学院大学 知識科学研究科 ○松久保 潤，林 幸雄
概要 有益なページを優先して収集 未探索かつ最大のIn-degreeをもつ ページを優先して収集 クローラによる探索実験 Webコミュニティ内の重要なページを 経由しながら探索しているように動作
背景 Webページの総数は急激に増加 Lawrence’99では約8億 山名’03では約70億 Googleの推定カバー率は約40% すべてのページをカバーするのは困難 できるだけ有益なページを優先
多くの興味・関心を集めているページを できるだけ多く収集する 目的 オーソリティ Ａ ハブ Ｈ 高いIn-degreeをもつページは 多くの興味・関心を集めている 多くの興味・関心を集めているページを できるだけ多く収集する
従来法(1/2) Cho, et al ’98 更新されたページの再探索を効率化するため 高い重要度をもつページを優先して探索 ページの内容とIn-degreeやOut-degree 及びPageRankなどを組み合わせて評価 Web全体のリンク構造を使用
従来法(2/2) Adamic, et al ’00 無向グラフ上で任意の二頂点間の経路長が できるだけ短くなるように探索する 高い次数をもつ頂点を経由すると 任意の二頂点間の経路長が比較的短くなる 最大の次数をもつ最近傍を優先する 最近傍の正確な次数が既知である
提案手法 適宜，最大のIn-degreeをもつ 未探索ページを優先的に探索 発見された未探索ページが全て探索候補 探索の優先順位は適応的に変化 以下，本提案手法を入次数優先探索 (In-degree First Search; IFS)と表記
クローラの動作 探索URL pに探索開始URLを格納 pのソースのダウンロード・構文解析を行い URLを抽出 探索キューW内のURLと重複しない場合 Wに格納 重複する場合 そのURLの優先順位を更新 W内の最大のIn-degreeをもつURLをpに格納 ②に戻る
探索実験 入次数優先探索(In-degree First Search; IFS) と幅優先探索(Breadth First Search; BFS) の比較 比較項目 オーソリティの累積獲得数 低い次数をもつページの累積獲得数
オーソリティだけでなくハブも効率的に収集 A及びHの累積獲得数 IFS BFS IFS BFS 図3 オーソリティの累積獲得数 図4 ハブの累積獲得数 IFSで収集したページがもつ次数の 上位0.1%に含まれる最小の次数 オーソリティだけでなくハブも効率的に収集
図6 低いOut-degreeをもつページの 次数の低いページの累積獲得数 IFS BFS IFS BFS 図5 低いIn-degreeをもつページの 累積獲得数 図6 低いOut-degreeをもつページの 累積獲得数 次数が低い頂点の累積獲得数が少ない
次数に対するページ数の分布 Pennock’02 特定のトピックを扱うページの分布が 対数正規分布に従う IFS BFS IFS BFS 図1 In-degreeに対するページ数 図2 Out-degreeに対するページ数 Pennock’02 特定のトピックを扱うページの分布が 対数正規分布に従う
最近傍の結合相関 nn k <kin > BFS IFS
コミュニティ間の移動の様子 IFS BFS IFSを用いた場合，A及びHが含まれるドメイン内の頁が 重点的に収集されている．
考察 Newman, et al ’03, Vázquez ’02 社会的ネットワークでは高い次数をもつ 頂点同士の結合頻度が高い H コミュニティの核となるオーソリティやハブを 経由しながらWeb上を探索している
Þコミュニティの核となるオーソリティやハブを 経由しながらWeb上のページを収集 まとめ 探索中に適宜，最大のIn-degreeをもつ未探索ページを 優先して探索する手法を提案し，クローラを実装した 実験結果 幅優先探索を用いた場合よりも効率的に オーソリティを収集できた 収集したページのリンク構造上で高い次数をもつ ページ同士の結合頻度が高くなっていた Þコミュニティの核となるオーソリティやハブを 経由しながらWeb上のページを収集
最近傍の結合相関(Out-degree) IFS BFS 入次数優先探索を用いた場合の方が 平均出次数が全体的に高くなっている
結果6:次数に対する最近傍の 平均次数(無向グラフ) IFS BFS 図11 入次数優先探索を用いた場合 図12 幅優先探索を用いた場合 どちらの場合も高い入次数をもつページに対する最近傍の平均出次数が低くなる傾向がある 幅優先探索を用いた場合の方が上述の傾向が強い
クローラの実装 <A>のHREF属性， <META>の転送を 他のページへのリンクとして扱う <FRAME SRC>で参照されるページ内の リンクは元のページからのリンクとして扱う 拡張子htm, html, asp, jsp, php, cfmをもつ ページへのURLをリンクとする 全てのcgi，及びhttp，https以外のプロトコルを用いるURLはリンクとして扱わない
クローラの実装 Wから最大の入次数をもつURLを取り出し pに格納する 探索URL pに探索開始URLを格納する pを探索済みリストSに追加する pのソースをダウンロードする 構文解析を行ってS内のURLと重複しないように URLを抽出する 抽出されたURLが探索キューW内のURLと 重複する場合にそのURLの入次数を1だけ増やす 重複しない場合にはWに格納する Wから最大の入次数をもつURLを取り出し pに格納する ②に戻る