Reported by Kan Matsuda 第２回副テーマ中間報告 Reported by Kan Matsuda Nishimto Libratory

今回の発表について Trawling the Web for emerging cyber-communities 前回発表した論文の補足 Internet広域分散協調サーチロボットの研究開発

Trawling the Web for emerging cyber-communities Ravi Kumar, Prabhakar Rabhavan, Sridhar Ragopalan, Andrew Tomkins

Overview Web上に数千の有名ではっきり定義されたコミュニティが存在 あいまいに定義されたコミュニティをトローリングにより抽出 抽出する理由 ユーザに良い情報を供給するため Webの発達を社科学的な観点から研究可能 ターゲットを絞った広告を出すことができる。

Strongly-connected bipartite sub graphs and cores IBMとコンパックは相互リンクを張っていない 他のページでこの両方にリンクを張っているページがある 確かな価値判断ではないが、リンクの合計はページのクォリティを示す 関係の深いページどうしてはcoreを形成

Strongly-connected bipartite sub graphs and cores F C core 仮説：ｗｅｂ上のランダムで十分大きくて濃度の濃いサブグラフはコアが確実にある

Strongly-connected bipartite sub graphs and cores ノードに入ってくる枝の数iと、出て行くノードの数jからcoreかどうかを判断 Fans：リンクを張っているページ Centers：リンクを張られているページ (2,0) (2,1) (3,3) (1,1) i:入ってくるの数 j:出て行く数

Data source and resource データは1年半以上前の若干古いもの HTMLデータのみ1テラバイト分 約2億ページ分のデータ(やや少ない） PⅡ300MHz、Linuxで2週間未満の実験

Fans fans=hubsと考える 最低でも6個のリンクを持っているページ リンク以外の情報は捨てる リンクのみの情報での効果的な改善が図れるか？ i,jが3~9の間で本当のコミュニティを見つけだせることを立証するため Fans:HITSやClever等のアルゴリズムにより発見された潜在的なfans 500以上の良好なCleveｒの結果をfansとみる

Mirrors and shingles ミラーサイトがあると偽りのcoreが見つかってしまう→ミラーサイトを見つけ除去する必要がある 見つける方法 http://assoft.co.at/~schaller/shop 2千4百万ぺージのfansで約60%ページ数が減少 減り過ぎのような気がしたのでいくつか拾い上げて確認したが、やはりミラーだった

In-degree distribution 最大で410のリンクを張られたサイトをプロット それ以上リンクを張られる確率は100万分の1以下 カーブのスロープは約１/2 i個の入力を持つ確立は約1/i2

Pruning centers by in-degree 参照の多いページを削除 製作者のブックマークとして使われているページなどを除去するため 明らかに有名なページは40以上のリンクが張られていることが経験的に知られている 有名なページは興味の対象外なので、リンクが50以上張られているページは除去

Trawling algorithm and system これだけ刈り込んでも6千万を超えるリンク、約2千万以上の潜在的なcentersそして数百マンのfansが存在する 更なる刈り込みが必要

Iterative Pruning メインメモリに入るリンクの数は約4千万で不足している→刈り込みを繰り返して対応 Fansをソートするときにリンクの数の少ないものを削除 Centersのリンクの少ないものを削除 1,2を繰り返す

Inclusion-exclusion pruning 抱合されている集合は除去する fans centers iは5以上 iは6以上 jは5以上 jは6以上

Finixhing　it　off 約13万5千のcoreが発見される （３．３）の場合で約7万5千のｃｏｒｅが存在

Evaluation of communities 得られたcoreの中から無作為に400((3.3)、(3.5))のcoreを選ぶ 現在のweb上で同じcoreが存在するかを調査 400中130(約35%)のcoreが現存

Internet広域分散協調サーチロボット の研究開発 早稲田大学 村岡洋一

概要 Jpドメインのみでもデータを集めきるのに1ヶ月以上かかる 24時間以内にjpドメインのデータを集めきることを目的とする研究の報告書 7個所に分散されたプロトタイプで103のWWWサーバーを対象に収集実験を行い、有効性を確認 ランダムな分散をした場合で2.6から10.6倍、負荷均一化を行なうと5.5から22倍の高速化が可能であることを確認　

はじめに Internet広域分散協調サーチロボットの研究 期待される成果 WWWロボットをネットワーク上に分散して複数配置 分散したロボットが担当するサーバーを自動的に決定させ、かつ協調動作させる 期待される成果 24時間以内に収集可能 最新データによる質の高い検索 国レベルおよび世界レベルでの協調収集した場合、ロボットによる負荷を大幅に削減可能

WWWロボットの問題 検索サービス毎にロボットを使用→サーバーへの負担 WWWページの取得に時間がかかる 収集データの陳腐化

分散協調サーチロボットのプロトコルの検討

モデル説明 PRSM Web server Search Service Server(SSS) PRS サイト間距離 Web server 制御 Search Service Server(SSS) 制御 PRS サイト間距離 Web　server PRS Web　server

PRSとPRSMのプロトコル設計 プロトコル (P1)担当するサーバーのリスト配布プロトコル (P2)発見したサーバーリストの配布プロトコル

PRSとPRSMの動作 動作 担当サーバーリストを送信(P1) WWWページを収集 WWWページを解析して道のWWWサーバをPRSMに通知(P2) ページ収集情報(サイズ,転送時間)をPRSMに通知(P3) PRMSはPRSからの情報を元に次の担当サーバリストを作成

RPSの動作 PRSの動作 PRSMにアクセスし担当リストを取得 担当分を収集する 平日午前2時から午前8時、土日は午前2時から午後10時まで収集 100個のサーバーに同時にアクセス 1つのサーバーに対し20秒おきにアクセス 午前9時ごろ収集ログをPRSMに転送

PRSMの動作 現在はプロトタイプのためサーバーリストの更新は行なわず、手動で設定したリストをPRSへ送っている 次節で分散エリアを決定する方法について述べる

分散エリア決定法の検討 「負荷均等化アルゴリズム」の提案 負荷均等化の有用性を示す 当初ｐｉｎｇによる時間を利用する予定 実際にサーバにアクセスし50ファイルをｈｔｔｐにより収集したほうが良いことが判明

Web空間のモデル化 Web空間の構成要素 スケーラビリティを考えホストを接点とした連結有効グラフとして表現 ＨＴＭＬで記述されたＷｅｂページ Ｗｅｂサーバーが動作している計算機 インターネット スケーラビリティを考えホストを接点とした連結有効グラフとして表現

ロボットのモデル化 ロボット：HTTPクライアントの一種 ロボットが保持する情報 負荷の均一化を行なうためにロボット間の通信が必要 自分が収集を担当しているホストのリスト 収集したWebページのデータ 各ホストのドキュメント量(KBytes) 各ホストの収集に要した時間 負荷の均一化を行なうためにロボット間の通信が必要 ロボットの数が増えるとパフォーマンスが落ちる ロボット間の距離を枝の重みとし,最小木をつくり、情報交換

パラメータの定義 Ｗｅｂ空間にロボットがm個所あるとし、その集合を とし、ロボットは最小木をなしているとする 収集対象となるホスト

コストの定義 ロボットのコストは収集にかかった時間で定義 ロボットriの担当ホストHi=(hi1,hi2,…hini)に属するページを収集するのに要した時間tij(j=1,2,…,ni)(単位はmsec) 当然成り立つこと

距離の定義 ネットワーク的な距離 ＝収集に要した時間/ドキュメント量 距離によるコスト ｗ:hに含まれる総ドキュメント量、ｄ：ｒからｈまでの距離

アルゴリズム プリムのアルゴリズムにより最小木を構築 プリム法はたいへん効率の良いアルゴリズムとして知られている。

隣接ロボット間のコスト均等化1 ロボットは担当ホストでの収集を終えるとコストを計算 隣接ロボット間でコストの均等化を行なう

隣接ロボット間のコスト均等化2 A E A E 4 2 10 D 12 10 D 12 C C 2 2 4 4 F B 6 F B 6 8 3.5 -4.5 -2.5 C 2 2 10.5 4 F B 8 1.5 F B 6 -0.5 7.5 -2.5 8 8 10

隣接ロボット間のコスト均等化3 コストはロボットとホストの距離に依存する コストの均等化に注目している 隣接ロボットにホストを渡した結果かえってコストが増加することがある 複数ステップ先のホストで距離が短くなる場合も考えられる →複数ステップ先のコストを知る必要がある