招待講演「大規模Webアーカイブの時空間分析とその実際」

1月22・23日に人工知能学会・知識ベースシステム研究会と電子情報通信学会の知能ソフトウェア工学研究会の共催で研究会があったのだが，「Web情報処理」特集と共に，東京大学から豊田正史助教授を招いて招待講演を企画させて頂いた．豊田助教授は，情報大航海プロジェクトと情報爆発プロジェクトの中心人物である喜連川教授の研究室に属していることからわかるように，これらのプロジェクトの技術的基盤を支える人物の一人でもある．この招待講演のスライドは以下の場所で公開されているので，興味がある人は見て頂きたい．

http://www.tkl.iis.u-tokyo.ac.jp/~toyoda/bib/papers/kbse-jsai-kbs.pdf

講演に関しては，口頭でかまわないから，普段論文やプレゼン資料に書かないようなこと…たとえば実装の詳細とか，実際の処理時間とか，このようなデータを扱うノウハウとか…も喋って頂くようにお願いした．残念ながら，資料に書かれていない部分もあるので，私の拙い記憶を辿ってメモ的に若干補いたい．逆に論文を読んだ方がよいようなことはあえて書かないので，興味がある研究者や開発者のみなさんは，ぜひホームページで公開されている論文を読んで頂きたい．

http://www.tkl.iis.u-tokyo.ac.jp/~toyoda/

当日の発表内容は，Web空間のコミュニティ構造と，その時間的変化の二段階に分けられ，デモもそれに準じたものであった．なお，豊田先生の研究室に行けば，資料中にあるような巨大なディスプレイを使って，巨大なネットワーク構造の詳細な部分まで見ることができる．
研究対象としているのは，Webでも日本のWebページであり，規模は資料中に示されているように数千万ページとのこと．昔の我々が提供していたサーチエンジンと，似たような規模である．
この「日本のWebページ」というのが結構難しい．現在サーチエンジンで検索できるのは数百億ページであるが，さすがにこの規模で収集して分析するためには，Google並のインフラが必要になる…たとえば，現在早稲田大学の山名教授は収集した約100億ページのリンク情報を作ろうとして苦労しているようだ．そこで，Web空間のサンプリングをおこなうわけだが，日本の重要なWebサイトであってもjpドメイン以外にある場合が多く，せっかく日本に特化したデータセットを作っても意味がなくなる．そこで，豊田先生の方法は，文字符号化を手がかりに日本語と判定されたページの少し先まで収集するという手法のようである．なお，我々が昔行っていた方法は，jpドメイン以外に日本語のアンカーテキストでリンクされているWebページを収集するという方法であった．こうすれば，日本に特化したサーチエンジンでも，よくリンクされる海外の重要サイトも検索できることになる．
この分野では，どの程度の規模のデータを処理すれば妥当だとされるのかという質問もあったが，現在公開されている評価用のWebアーカイブデータの規模は同じようなものだった気がする．これを大きく超えてしまうと，本格的な分散処理インフラを構築する必要があるだろう．
インフラに関しては，8CPUのItanium2サーバを使っており，リンク情報は独自のデータベース，題名やアンカーなどはBerkely DBを使っているとのことであった．この程度の規模のデータであれば，計算速度的には十分（もちろん，使っているアルゴリズムが軽いこともあるが）で，ディスク容量は全体的には確保できているそうだが，なにしろデータサイズが大きい上に，数年間のデータを全部保存しているものだから，空き容量を見ながらデータを移したりする手間が馬鹿にならないとのことであった．このような場合には，やはり柔軟・自動的なファイル配置ができるGoogle ファイルシステムのようなファイルシステムが欲しくなる．
Webグラフの表示には，ネイティブライブラリを用いて独自にばねモデルを実装して使っているそうだが，だいたい数千ノードまでなら問題なくリアルタイム表示できるとのことであった．ネットワーク構造の可視化では，巨大なデータの場合にはオフラインで座標位置を計算するのだが，リアルタイムに数千ノードを表示できるのは素晴らしい．
Webコミュニティチャートの生成で，私が目を開かされたのは，三角形構造を重ね合わせていくところである．ネットワーク構造をクラスタリングする手法は数多くあるのだが，大規模なネットワーク構造に適用するには重いものが多い．三角形構造はクラスタリング係数などでも着目される構造であり，それを使って半日！で生成することを最初聞いた時には，私のような石頭の研究者にとっては目から鱗であった．
やはり豊田助教授の素晴らしいところは，研究開始当時から収集したスナップショットを保存していることだ．研究費が少ないからという理由から，せっかく収集したデータを毎回消してはいけない（苦笑）
ただし，当然考えられるのは，Webロボットで収集した時に，必ずしも毎回同じWebページを収集してくれないところ．サーチエンジンを運用していた時には，データベースを更新すると「私のページが検索されなくなりました！」という苦情がちらほら舞い込んだものだが，これは解析においては障害にならないだろうか？…と思ったが，どうもそうではないようである．たとえば，ネットワーク分析の分野では，クラスタリング結果の不安定性…たとえばリンク構造がちょっと変化しただけで結果が大きく異なる…ことがあるのだが，たとえばコミュニティ構造を抽出する場合は，弱いエッジから切る方法と，重要なノード群を抽出する方法があり，どちらかと言えば後者に属するからではないかと推測している．アルゴリズムの時間的変化に対する安定性の分析は，今後同様なデータセットが充実していけば，興味深いテーマになりそうと思っている．
しかし，Webページがいつ作られたのか…という情報を判定するのは，スナップショットにも欠落があるのだから難しい．Webサーバだって，まともにLast-Modifiedなんて付けてくれないもの．…と思っていたら，デモを見てびっくりした…というのは，なんと豊田先生はアーカイブを解析して，Webページの新しさを求める方法を実現していたのだった．つまり，制約のあるデータを使っても自由に過去に遡れるWebタイムマシンを目の前に見せてくれたのだった．なお，当日も質問があったが，当然未来には行けないのであしからず（笑）この論文はWorld Wide Web Conference 2006で発表され， http://www2006.org/programme/item.php?id=571 で読むことができる（実は，詳しく読んでない…すみません（爆））．

講演して頂いた豊田助教授には，感謝したい．なお，今後もこのような講演をいろいろな場で企画したいと思うので，その際はここを読んでいる人にもぜひ聞きに来て貰いたい．