Éû¥Æ¡¼¥ÞÃæ´ÖÊó¹ð

副テーマ中間報告
1.
Development of a Scale Web Crawler
By hajime TAKANO and Nobuya KUBO
2.
Trawling the Web for emerging cyber-communities
Ravi Kumar, Prabhakar Rabhavan, Sridhar
Ragopalan, Andrew Tomkins
Reported by Kan Matsuda
Development of a Scale Web Crawler


NECの検索サービスNETPLAZAで用いら
れている検索サービスのweｂロボット
“Nexplorer”の製作、実験について
実際に検索サービスに利用し検証
2000年11月9日
副テーマ中間報告
INTRODUCTION
検索サービスの主な機能は次の三つから成る．
１.WWWのページを集める．
２.データベース内の集めたページを蓄え，管理する．
３.ユーザーが要求するページを探してくる．



Web crawler:WWWのページを集めてくるエージェ
ントシステム
Webページは大量→素早い収集・最適化可能な
基本構造が必要
Nexplorer:これらの要求を満たすWeb crawler
2000年11月9日
副テーマ中間報告
REQUIREMENTS FOR WEB
CRAWLER
1ホスト100枚とすると
約4億3千万の
ホスト
Web crawlerの基本的な機能

Web


約430億のWebページ
JPドメイン
約2億枚
HTMLからURLを見つける→それらのURLへ行ってドキュメ
ントを得る
crawlerの設計
ハードウェア：複数のCPUを用いる
ソフトウェア：並列処理ができる構成にする
2000年11月9日
副テーマ中間報告
Functional Requirements







WWWページを出来るだけ早く集める
重要なサイトに優位性を加える
重要でないサイトの優位性を下げる
コンテンツの種類によりページをフィルタリングする
巡回するサイトを選ぶ
予約語を含むページを除去する
深いディレクトリまたは特殊なものは無視する
2000年11月9日
副テーマ中間報告
BULDING A SERCH SERVICE

NexplorerをNETPLAZAで使用




CGIでキーワードを入力する
JPドメインからWWWのページを集めてくる
サーバを増やせば効率が良くなる
ｇｏｏ等に負けないスピードを実現
2000年11月9日
副テーマ中間報告
CONCLUSION




Nexplorerを作成
NETPLAZAで検索サービスとして利用し、
検索サービスに十分な速さを実現している
より小さな規模へ適用し、スケーラビリティ
を確かめたい
より戦略的なクルーリングへの機能拡張
2000年11月9日
副テーマ中間報告
Trawling the Web for emerging
cyber-communities
Ravi Kumar,
Prabhakar Rabhavan,
Sridhar Ragopalan,
Andrew Tomkins
Overvew



Web上に数千の有名ではっきり定義された
コミュニティが存在
あいまいに定義されたコミュニティをトローリ
ングにより抽出
抽出する理由
1.
2.
3.
ユーザに良い情報を供給するため
Webの発達を社科学的な観点から研究可能
ターゲットを絞った広告を出すことができる。
2000年11月9日
副テーマ中間報告
Strongly-connected bipartite
subgraphs and cores




IBMとコンパックは相互リンクを張っていな
い
他のページでこの両方にリンクを張っている
ページがある
確かな価値判断ではないが、リンクの合計
はページのクォリティを示す
関係の深いページどうしてはcoreを形成
2000年11月9日
副テーマ中間報告
Strongly-connected bipartite
subgraphs and cores
F
C
core
仮説：ｗｅｂ上のランダムで十分大きくて濃度の
濃いサブグラフはコアが確実にある
2000年11月9日
副テーマ中間報告
Data source and resource




データは1年半以上前の若干古いもの
HTMLデータのみ1テラバイト分
約2億ページ分のデータ(やや少ない）
PⅡ300MHz、Linuxで2週間未満の実験
2000年11月9日
副テーマ中間報告
Trawling system
ノードに入ってくる枝の
数iと、出て行くノードの数
jからcoreかどうかを判断
Yahooなどのサイトは排
除する
(3,3)
(2,1)
(2,0)
(1,1)
i:入ってくるの数
j:出て行く数
2000年11月9日
副テーマ中間報告
Finixhing it off
約13万5千のcoreが発
見される
（３．３）の場合で約7万5
千のｃｏｒｅが存在
2000年11月9日
副テーマ中間報告
Evaluation of communities



得られたcoreの中から無作為に400((3.3)、
(3.5))のcoreを選ぶ
現在のweb上で同じcoreが存在するかを調
査
400中130(約35%)のcoreが現存
2000年11月9日
副テーマ中間報告

Download Report