PageRank の正式な定義は、引用文献の 4 ページで定義されているように、おかしな「E」記号を使用した数式で表されます (実際、これはギリシャ文字の大文字のシグマです。シグマは、ここで表す文字「S」です)。合計のため）。
一言で言えば、この式は、ページ X の PageRank を計算するには...
このページへのすべての被リンク (= X にリンクしているすべてのページ)
次の値を計算する必要があります。
X にリンクしているページの PageRank [R'(v)]
で割った
このページで見つかったリンクの数。[Nv]
あなたが追加する
c で正規化された「ランクのソース」、[E(u)]
(その目的については後で説明します。)
そして、これらすべての値の合計を作成する必要があります [シグマのこと]
最後に、定数 [c] を掛けます。
(この定数は、PageRank の範囲を管理しやすくするためのものです)
この式の重要なアイデアは、特定のページ X にリンクするすべての Web ページがその「価値」に付加価値を与えるということです。あるページにリンクすることで、彼らはこのページに賛成して「投票」しています。ただし、この「投票」には、次の 2 つの要因に応じて、多かれ少なかれ重みがあります。
- X [R'(v)] にリンクしているページの人気度
- X にリンクしているページが他の多くのページにもリンクしているかどうか。[Nv]
これらの 2 つの要因は、非常に直感的なアイデアを反映しています。
- 一般的には、知らない人から推薦状をもらうよりも、その分野で認められている専門家から推薦状をもらうほうがよいでしょう。
- 誰が推薦するかに関係なく、他の人にも推薦を与えることで、彼らはあなたへの推薦の価値を減らしています.
X のページ範囲を知るには、X にリンクしているすべてのページの PageRank を知る必要があるため、この式は循環参照を使用しています。では、これらの PageRank 値をどのように計算しますか?...ドキュメントのセクションで説明されている収束の次の問題が発生します。
基本的に、すべてのページについて、PageRank の「ランダムな」値 (またはできれば「適切な推測」値) から開始し、上記の式を使用して PageRank を計算することにより、このプロセスを数回繰り返すと、新しく計算された値が「より良く」なります。回. 値は収束します.つまり, それぞれが実際の/理論上の値にどんどん近づいていきます. したがって, 十分な回数反復することで, 反復を繰り返しても関数によって提供される値に実用的な精度が追加されない瞬間に到達します.最後の反復。
さて...理論的には、それは素晴らしくてダンディです。秘訣は、このアルゴリズムを同等のものに変換することですが、その方がより迅速に実行できます。これと同様のタスクを実行する方法について説明している論文がいくつかあります。私はそのような参考文献を手元に持っていませんが、後で追加します。線形代数の健全な用量が含まれることに注意してください。
編集:約束どおり、ページ ランクを計算するアルゴリズムに関するリンクをいくつか示します。
PageRank の効率的な計算 Haveliwala 1999 ///
コンピューティング PR のための Web のブロック構造の活用 Kamvar et al 2003 ///
PageRank を計算するための高速な 2 段階アルゴリズム 2002年
上記のリンクの著者の多くはスタンフォード出身ですが、効率的な PageRank のような計算の探求が注目の研究分野であることを理解するのにそれほど時間はかかりません。この資料は OP の範囲を超えていることは承知していますが、基本的なアルゴリズムは大きな Web では実用的ではないという事実をほのめかすことは重要です。
非常にアクセスしやすいテキスト (詳細な情報へのリンクが多数あります) で締めくくるには、ウィキペディアの優れた記事に言及したいと思います。
この種のことに真剣に取り組んでいる場合は、数学、特に線形代数の入門/復習クラスと、グラフ全般を扱うコンピューター サイエンスのクラスを検討することをお勧めします。ところで、1806 年の講義の OCW のビデオについて、この投稿で Michael Dorfman から素晴らしい提案がありました。
これが少し役立つことを願っています...