【書評・感想】Google PageRankの数理
2012-05-10-2
[BookReview][Algorithm]
ここ最近、多くのノードとリンクを持つ巨大なネットワーク構造データに対して、各ノードの重要度を求めるというタスクに興味を持っています。その際の参考書がこの本です。完全理解には程遠いんですが、とりあえず一通り全部に目を通しました。買ってから2年くらいたっちゃいましたが(原著の発売はもっと前)、理論自体が古くなることはないので問題なし。
■Amy N.Langville, Carl D.Meyer / Google PageRankの数理 --最強検索エンジンのランキング手法を求めて--
基礎から細かく解説してくれているので、内容を咀嚼しながら(Perlで実装しながら)読みました。こういうアルゴリズム系の話って、読むだけで理解するというのはすごく苦手で、必ずプログラムに落として動かさないとなんというか身に染み入らないんですよね。
とりあえず、PageRankやHITSに関しては標準的なスペックのサーバ上で百万ノード規模で数分〜十数分で計算できるPerlプログラムはできました(本書を読んで素直にPure Perlで実装したベースライン)。行列操作の一部が一番メモリを食うのでそこを工夫できればもっとノード数が多くても大丈夫かも。とはいえ、もっと大規模だとHadoopとか使わないとダメだろうなあ。
HITSについてはPerlで簡単なサンプルプログラムを書いていますのでどうぞ→[2011-11-10-1]。PageRankについてもサンプルプログラムを書き下ろす予定です。とはいえ、育児等で業務外でまとまった時間が取りづらい今日この頃ゆえ気長にお待ちくださればと。
■Amy N.Langville, Carl D.Meyer / Google PageRankの数理 --最強検索エンジンのランキング手法を求めて--
Googleはウェブ検索エンジンで世界的大企業となった。本書では,Googleのウェブ検索エンジンの基礎であるPageRankアルゴリズムや,他の代表的なHITSアルゴリズムなどを,それらの初歩から,数学的側面や関連するエピソードも含めて紹介する。基本的なアルゴリズムの解説から始め,その高速化,更新問題,そして安定性の問題,収束性の問題など,様々な角度より検索エンジンのアルゴリズムを分析しており,検索エンジンの仕組みはどうなっているか,なぜGoogleはそんなに優れているのかなどの疑問に答えている。
基礎から細かく解説してくれているので、内容を咀嚼しながら(Perlで実装しながら)読みました。こういうアルゴリズム系の話って、読むだけで理解するというのはすごく苦手で、必ずプログラムに落として動かさないとなんというか身に染み入らないんですよね。
とりあえず、PageRankやHITSに関しては標準的なスペックのサーバ上で百万ノード規模で数分〜十数分で計算できるPerlプログラムはできました(本書を読んで素直にPure Perlで実装したベースライン)。行列操作の一部が一番メモリを食うのでそこを工夫できればもっとノード数が多くても大丈夫かも。とはいえ、もっと大規模だとHadoopとか使わないとダメだろうなあ。
HITSについてはPerlで簡単なサンプルプログラムを書いていますのでどうぞ→[2011-11-10-1]。PageRankについてもサンプルプログラムを書き下ろす予定です。とはいえ、育児等で業務外でまとまった時間が取りづらい今日この頃ゆえ気長にお待ちくださればと。
この記事に言及しているこのブログ内の記事