The PageRank Citation Ranking
こちらの論文を読んだのでまとめます。(http://ilpubs.stanford.edu:8090/422/)
Google検索エンジンのアルゴリズムに関する論文です。
Googleの起源に迫ることができます。
1. Introduction and Motivation
この論文では、全てのwebページに対してグローバルな"重要性"ランキングを作るために、webのネットワーク構造を利用する。このランキングを"PageRank"とよび、これを用いるとユーザーはworld wide webの複雑な入り混じりを理解することができる。
1.1 Diversity of Web Pages
web pages と academic publications（いわゆる論文）の違い
- webページはprogrammingを使うことで大量に作成可能
- webページのrankingを、ページ内の特徴で計算する仕組みにすると、不正が起こりやすい
- 論文は形式や目的がおおよそ決まっているが、webページは様々な形式及び目的
→ページ外の要素、つまりwebページのネットワーク構造を用いることで相対的な"重要性"を算出できる
2. A Ranking for Every Page on the Web
2.1 Related Work
多くの検索エンジンでは、backlinkの数（あるwebページに対して飛んでいるlinkの数,論文なら引用数）を用いることでページの重要性やクオリティを測っている。しかし、このシンプルな方法をwebページの検索エンジンに対して用いると問題が発生する。
2.2 Link Structure of the Web
※A,B,Cはwebページで、赤線はCのbacklink（A,Bのforwardlink)を表している。
シンプルなbacklinkの数とそのページの重要性が一致しないケースが、webページにおいてはよく起きる。
(ex.yahoo.comからのlinkが一本だけついているpageは重要性が高そうだけど、backlink数は１本のみ）
2.3 Propagation of Ranking Through Links
じゃあどうすればいいか。
PageRankの考え方は以下で集約される。
「backlinkのrankの総和が高ければ、そのページのrankも高い」
どういうことかは追々わかるだろう。
2.4 Definition of PageRank
以下のように定式化する（文字の説明はめんどくさいので画像ないの英語見てください）
・各ページのrankは、そこから出ているforward linkに等しく等分されている
・各ページのrankは、そのページに入ってくるbacklinkのrankの総和である
この二点を抑えておけばよい（上図を見て実際に確かめて欲しい）
結果から言うとc<1になるのだが、これに関しては2.7を参照して欲しい。
この式は再帰的であるが、初期値を与えて計算しまくるとRの値がそのうち収束していく。
計算がわかりやすいように行列で表す。（ここもめんどくさかったので英語読んでください）
要はノード間の関係を隣接行列Aで表して転置し、その行列の最大固有値に対する固有ベクトルを求めてあげるとそれがPageRankになっているよ、というお話です。
初期ベクトルを適当に用意してあげてそれにAをかけまくると収束していってRベクトルがもとまります。（冪乗則で検索！）
このシンプルなモデルには問題がある。
上図のように「流れ込むlinkはあっても出ていくlinkがないwebページの集まり」が存在したとき、計算を進めるにつれてこのwebページの集まりにrankの値が蓄積されていく（出ていかないので）。結果として他のページのrankがゼロになり、この集まりないのページのrankが∞になってしまう。
これを"rank sink"と呼ぶ。
この問題を解決するために、a source of rankを導入する。下の式のE(u)がそれ。
rank sourceとは、webグラフ状の全てのwebページに与える一定のpageRankの値である。
先ほどと同じように行列表現すると以下。
2.5 Random Surfer Model
一つ目にあげた式（rank sourceを含まない方）はどのようなモデルを想定しているかというと、「現在見ているページのアウトリンクを辿って次のページに遷移する」モデル。
しかし、実際に人間がネットでページを見るときの動きを考えると、「現在見ているページのアウトリンクを辿って次のページに遷移する」に加えて、「現在のページ内のアウトリンクに関係なくランダムに選んだページに遷移する」ことも考えられる。（ex.programmingの勉強でいろんなサイトを遷移して学んでいたけど、飽きたのでyoutubeをみよう！みたいな感じ)
この動きをうまく表しているのが二つ目の式（rank sourceを含む方）のE(u)である。
Section6で後述するが、このEという値を用いることでpageRankを個人の好みにカスタマイズすることもできる。
2.6 Computing PageRank
冪乗則を用いてRを計算。dは正規化に用いられている。
2.7 Dangling Links
Dangling Linksとは、「outlinkを持たないwebページに対して飛んでいるlink」である。著者は「とりあえず全てのpagerankを算出するまではDangling Linksは除外して、計算が終わったらDangling Linksも考慮して調整しなおそう、まあいずれにせよDangling Linksはそんなに影響を与えないでしょう」とのことです。
3. Implementation
3.1 PageRank Implementation
それぞれのURLをユニークな整数に変換してハイパーリンクをデータベースに格納する
ステップ１. リンク集合をリンクのParentIDでsort
ステップ2. dangling linksを取り除く
ステップ３. ページの初期の重みを設定する（ここの工夫によって時間が節約できる）
ステップ４. 現在のページの重みはmemoryに、過去のはdiskに線形に保存されてる
ステップ5. ステップ1でソートしたからdisk内の行列Aの要素にも順番に取りに行けるよ（ ソートしてない時よりスピード早いよ）
ステップ6. 各ページの重みが収束するまで回すよ、収束条件を緩めると当然時間も短くなるよ
ステップ７. dangling linksを戻して、dangling linksを取り除くのに要した回数と同じだけ計算を回す
4. Convergence Properties
PageRankの計算はスケールできる。計算時間はおおよそlognに比例している。
ノードの"重要性"ランキングとは、本質的に「十分な時間が経過した後にランダムウォーカーがそのノードにいるかどうかの極限確率分布」である。
また、PageRankの計算がlog時間で終わる（収束する）のは、ランダムウォークがrapid-mixingであることやリンク構造がよいexpansion factorを有しているのと同値。
5. Searching with PageRank
PageRankは、曖昧なクエリに対して絶大な効果をはっきする。
5.1 Title Search
クエリがtitleに含まれるかどうか+PageRankという単純な組み合わせでも、Altavistaに比べると高い性能を示している。
5.2 Rank Merging
5.3 Some Sample Results
5.4 Common case
PageRankの目標の一つとして、「common case(みんながよく使うページ)に対するクエリをうまく扱う」ことである。common caseであるという情報をページ内から推測することはよろしくない（ページ管理者はアクセス数を稼ぎたいのでみなcommon caseになりたがる）
common caseページを探し当てることと、たくさんの情報を持っているページを探し当てることは全く異なるタスクである、そしてどちらのタスクも大切である。本論文では前者のcommon caseを探し当てることに焦点を当てる。
5.5 Subcomponents of Common Case
PageRankは、common caseを優先的に検索できるだけではなくて、権限や信頼の協調的概念も表現できる。
6 Personalized PageRank
rank sinkに対処するために導入されたrank source E(u)は、他に、PageRankを個人個人にカスタマイズできるという役割もある。
Eを全webページで一様にする、という方法は概ね成功するが、少し問題点もある。コピーライトなどのそこまで重要ではないけどリンクが多く飛んできているページが高く評価されてしまっていることである。
逆に、Eが一つのページにしか分布していない極端な例を考える。
Eを、自分がよく使用するwebページに重点的に分布させることで、一様に分布させたときに比べてそのwebページのPageRankが高くなることがわかっている。Eをうまく設定することで、検索エンジンを自分仕様にカスタマイズできるのだ。
6.1 Manipulation by Commercial Interests
7 Applications
7.1 Estimating Web Traffic
ポルノサイトへのアクセスは多いのに、これらのサイトのページランクは低いそうですwww
まあ、ポルノサイトへアウトリンク飛ばす人あんまりいないですもんね。。。
7.2 PageRank as Backlink Predictor
PageRankは、citation countingに比べて、将来の引用数を予測する性能が高いらしい。
counting citationは、内輪のページ群でつまりやすい（例えばStanfordのCS関連のページ群を捜索していると、その中のページばかり見てしまい、外に行きにくい）
7.3 User Navigation:The PageRank Proxy
サイトとサイトのページランクを一緒にのせたプロキシアプリケーションは、使用者がサイトをクリックする前に情報を得られるので便利だよ。（怪しいサイトを踏まなくてもすみそう）
7.4
8. conclusion
PageRankとは、ページの内容に関係なく、webのグラフ構造の位置に基づいた全てのページに関するグローバルなランキングである。
後半雑になってすみません...(大事なのは３章くらいまでなので...)
追加（蛇足）
PageRankに対する改善策
1. Rank Sourceを個人の趣向にカスタマイズ
これはすでに論文中でやっている
2. Forward linkをevenlyに分割せずに、重み付けをする
現在のノード内のアウトリンクのうち、サーファーが興味・関心のあるノードへのアウトリンクを優先的に選択して遷移させる
3. バックボタンの考慮
ダングリングノードに遷移した場合に、戻るボタンで一つ前に閲覧していたwebページに戻る可能性がある。