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の更新によって探索の優先順位は適応的に変化以下，本提案手法を入次数優先探索 (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 図3 オーソリティの累積獲得数 IFS BFS 図4 ハブの累積獲得数 IFSで収集したページがもつ次数の上位0.1%に含まれる最小の次数オーソリティだけでなくハブも効率的に収集次数の低いページの累積獲得数 IFS BFS 図5 低いIn-degreeをもつページの累積獲得数 IFS BFS 図6 低いOut-degreeをもつページの累積獲得数次数が低い頂点の累積獲得数が少ない次数に対するページ数の分布 IFS BFS IFS BFS 図1 In-degreeに対するページ数図2 Out-degreeに対するページ数 Pennock’02 特定のトピックを扱うページの分布が対数正規分布に従う最近傍の結合相関 k IFS nn <kin > BFS コミュニティ間の移動の様子 BFS IFS IFSを用いた場合，A及びHが含まれるドメイン内の頁が重点的に収集されている．考察 Newman, et al ’03, Vázquez ’02 社会的ネットワークでは高い次数をもつ頂点同士の結合頻度が高い A A H H A H コミュニティの核となるオーソリティやハブを経由しながらWeb上を探索しているまとめ探索中に適宜，最大のIn-degreeをもつ未探索ページを優先して探索する手法を提案し，クローラを実装した実験結果幅優先探索を用いた場合よりも効率的にオーソリティを収集できた収集したページのリンク構造上で高い次数をもつページ同士の結合頻度が高くなっていた コミュニティの核となるオーソリティやハブを経由しながらWeb上のページを収集最近傍の結合相関(Out-degree) IFS BFS 入次数優先探索を用いた場合の方が平均出次数が全体的に高くなっている結果6:次数に対する最近傍の平均次数(無向グラフ) IFS 図11 入次数優先探索を用いた場合 BFS 図12 幅優先探索を用いた場合 • どちらの場合も高い入次数をもつページに対する最近傍の平均出次数が低くなる傾向がある • 幅優先探索を用いた場合の方が上述の傾向が強いクローラの実装 • <A>のHREF属性， <META>の転送を他のページへのリンクとして扱う • <FRAME SRC>で参照されるページ内のリンクは元のページからのリンクとして扱う • 拡張子htm, html, asp, jsp, php, cfmをもつページへのURLをリンクとする • 全てのcgi，及びhttp，https以外のプロトコルを用いるURLはリンクとして扱わないクローラの実装 ① 探索URL pに探索開始URLを格納する ② pを探索済みリストSに追加する ③ pのソースをダウンロードする ④ 構文解析を行ってS内のURLと重複しないように URLを抽出する ⑤ 抽出されたURLが探索キューW内のURLと重複する場合にそのURLの入次数を1だけ増やす ⑥ 重複しない場合にはWに格納する ⑦ Wから最大の入次数をもつURLを取り出し pに格納する ⑧ ②に戻る