ネットワークサイエンスのPageRankを完全理解した話
概要
- Googleの検索エンジンで使われている(た)PageRankについての解説記事
- 考え方としては「あるページが他のページによってどれくらい推薦されているか」
- ユーザがランダムにページを変移していくというiterationを複数回回して、以下の値が収束するまで続ける
- あるノードのランクは隣接するノードが持つランクをエッジ数で割った値にする
- 初期値は単純に1をノード数で割った値などにする
- 上のに対してさらに以下のような問題を解決して改良していく
- 終端ノードではどこにもpathがないので、終端ノードの価値が0になってしまうのを防ぐために、randomにテレポートする
- 終端ノードで自己回帰のpathがある場合、重要でもないに関わらずrank scoreが溜まってしまい大きな値を持ってしまう。これもrandomにテレポートすることで解決する。
- 最終的には以下のような式
- はどれくらい存在するエッジだけで遷移を行うかのパラメータでダンピングファクターという
- 色々なページから遷移されるページは重要度が高いはずだという仮説を元に作られている指標なので、そのような仮説が成り立つ場合に使う。