ページランク

PageRank ( PR ) は、Google 検索が検索エンジンの結果でウェブページをランク付けするために使用するアルゴリズムです。これは、「ウェブページ」という用語と共同設立者のLarry Pageにちなんで名付けられました。PageRank は、ウェブサイトのページの重要性を測定する方法です。Google によると、次のようになります。

PageRank は、ページへのリンクの数と質を数えて、ウェブサイトの重要度を大まかに推定する仕組みです。その根底にある前提は、より重要なウェブサイトは他のウェブサイトからより多くのリンクを受け取る可能性が高いということです。^[1]

現在、PageRankはGoogleが検索結果を順位付けするために使用している唯一のアルゴリズムではありませんが、同社が使用した最初のアルゴリズムであり、最もよく知られています。^{[2] [3]} 2019年9月24日現在、PageRankに関連するすべての特許は期限切れになっています。^[4]

PageRank はリンク分析アルゴリズムであり、ワールド ワイド ウェブなどのハイパーリンクされたドキュメントセットの各要素に数値の重みを割り当て、セット内での相対的な重要性を「測定」することを目的としています。このアルゴリズムは、相互引用および参照を含むエンティティの任意のコレクションに適用できます。任意の要素Eに割り当てられる数値の重みは、 E の PageRankと呼ばれ、次のように表されます。 ${\displaystyle PR(E).}$

PageRank は、 cnn.comやmayoclinic.orgなどの権威ハブを考慮し、すべての World Wide Web ページをノード、ハイパーリンクをエッジとして作成するWeb グラフに基づく数学的アルゴリズムから得られます。ランク値は、特定のページの重要性を示します。ページへのハイパーリンクは、支持票としてカウントされます。ページの PageRank は再帰的に定義され、そのページにリンクしているすべてのページ (「着信リンク」)の数と PageRank メトリックに依存します。Pag​​eRank の高い多くのページからリンクされているページは、それ自体が高くなります。

Page と Brin の最初の論文以来、PageRank に関する数多くの学術論文が発表されています。^[5]実際には、PageRank の概念は操作されやすい可能性があります。誤って影響を受けた PageRank ランキングを特定するための研究が行われています。その目的は、誤って影響を受けた PageRank を持つ文書からのリンクを無視する効果的な方法を見つけることです。^[6]

ウェブページのリンクベースのランキングアルゴリズムとしては、ジョン・クラインバーグが発明したHITSアルゴリズム（Teoma、現在はAsk.comで使用）、IBM CLEVERプロジェクト、TrustRankアルゴリズム、ハミングバードアルゴリズム^[7]、SALSAアルゴリズム^[8]などがあります。

PageRank のアルゴリズムの背後にある固有値問題は、独立して再発見され、多くのスコアリング問題で再利用されました。1895 年、エドモンド ランドーは、チェス トーナメントの勝者を決定するためにそれを使用することを提案しました。^{[9] [10]}固有値問題は、科学雑誌のランキング付けを行う科学計量学に取り組んでいたガブリエル ピンスキーとフランシス ナリンによって 1976 年に提案され、 ^[11] 1977 年にはトーマス サーティによって、代替選択肢に重み付けを行う階層分析プロセスの概念の中で提案され、 ^[12] 1995 年にはブラッドリー ラブとスティーブン スロマンによって概念の認知モデルとして中心性アルゴリズムとして提案されました。^{[13] [14]}

IDD Information Services の「RankDex 」という検索エンジンは、1996 年にRobin Liによって設計され、サイトスコアリングとページランキングの戦略を開発した。^[15] Li は、この検索メカニズムを「リンク分析」と呼び、他のサイトがリンクしている数に基づいて Web サイトの人気度をランク付けするものである。^[16]ページランキングとサイトスコアリングのアルゴリズムを備えた最初の検索エンジンである RankDex は、1996 年に開始された。^[17] Li は、1997 年に RankDex の技術の特許を申請し、1999 年に認可された。^[18]彼はその後、2000 年に中国でBaidu を設立した際にこの技術を使用した。 ^{[19] [20]} Google の創設者Larry Page は、 PageRank に関する米国特許の一部で Li の研究を引用している。^{[21] [17] [22]}

ラリー・ペイジとセルゲイ・ブリンは、1996年にスタンフォード大学で新しいタイプの検索エンジンに関する研究プロジェクトの一環として、PageRankを開発しました。スタンフォード大学のコンピュータサイエンス教授でセルゲイのアドバイザーであるヘクター・ガルシア・モリーナへのインタビュー^[23]は、PageRankアルゴリズムの開発の背景を説明しています。^[24]セルゲイ・ブリンは、Web上の情報は「リンク人気」によって階層的に並べることができると考えました。つまり、リンクが多いほどページのランクが高くなります。^[25]このシステムは、スコット・ハッサンとアラン・ステレンバーグの協力を得て開発されました。ペイジとブリンは、この2人をGoogleの開発に不可欠だったとしています。^[5] ラジーヴ・モトワニとテリー・ウィノグラッドは、ペイジとブリンと共同で、PageRankとGoogle検索エンジンの初期プロトタイプについて説明したプロジェクトに関する最初の論文を1998年に発表しました。^[5]その後まもなく、ペイジとブリンはGoogle検索エンジンを開発するGoogle Inc.を設立しました。PageRankはGoogle検索結果のランキングを決定する多くの要素の1つにすぎませんが、Googleのすべてのウェブ検索ツールの基礎を提供し続けています。^[26]

「PageRank」という名前は、開発者ラリー・ペイジの名前とウェブページの概念に由来している。^{[27] [28]}この言葉はGoogleの商標であり、PageRankのプロセスは特許を取得している（米国特許6,285,999）。しかし、この特許はGoogleではなくスタンフォード大学に譲渡されている。Googleはスタンフォード大学から特許の独占的使用権を取得している。同大学は特許の使用と引き換えにGoogleの株式180万株を受け取り、2005年に3億3600万ドルで売却した。 ^{[29] [30]}

PageRankは、 1950年代にペンシルバニア大学でユージン・ガーフィールドが開発した引用分析と、パドヴァ大学でマッシモ・マルキオーリが開発したハイパーサーチの影響を受けています。Pag​​eRankが導入されたのと同じ年（1998年）、ジョン・クラインバーグはHITSに関する研究を発表しました。Googleの創設者は、ガーフィールド、マルキオーリ、クラインバーグの論文を引用しています。^{[5] [31]}

PageRank アルゴリズムは、リンクをランダムにクリックした人が特定のページに到達する可能性を表すために使用される確率分布を出力します。 PageRank は、任意のサイズのドキュメント コレクションに対して計算できます。 いくつかの研究論文では、計算プロセスの開始時に、分布がコレクション内のすべてのドキュメント間で均等に分割されると想定されています。 PageRank の計算では、コレクション全体にわたって「反復」と呼ばれる複数のパスが必要であり、これにより、おおよその PageRank 値が理論上の真の値に近づくように調整されます。

確率は 0 から 1 までの数値で表されます。確率 0.5 は、通常、何かが起こる「50% の確率」として表されます。したがって、PageRank が 0.5 のドキュメントは、ランダムなリンクをクリックした人がそのドキュメントに誘導される確率が 50% あることを意味します。

4 つの Web ページ ( A、B、C、およびD )の小さな世界を想定します。ページからそのページ自体へのリンクは無視されます。1 つのページから別のページへの複数のアウトバウンド リンクは、1 つのリンクとして扱われます。 PageRank は、すべてのページで同じ値に初期化されます。 PageRank の元の形式では、すべてのページの PageRank の合計がその時点での Web 上のページの総数であったため、この例の各ページの初期値は 1 になります。ただし、PageRank のそれ以降のバージョンと、このセクションの残りの部分では、確率分布が0 から 1 の間であると想定しています。したがって、この例の各ページの初期値は 0.25 です。

次の反復で特定のページからそのアウトバウンド リンクのターゲットに転送される PageRank は、すべてのアウトバウンド リンク間で均等に分割されます。

システム内のリンクがページB、C、DからページAへのリンクのみである場合、次の反復で各リンクは 0.25 PageRank をAに転送し、合計は 0.75 になります。

${\displaystyle PR(A)=PR(B)+PR(C)+PR(D).\,}$

代わりに、ページBにページCとページAへのリンクがあり、ページCにページAへのリンクがあり、ページDに 3 つのページすべてへのリンクがあるとします。したがって、最初の反復で、ページB は既存の値の半分 (0.125) をページAに転送し、残りの半分 (0.125) をページCに転送します。ページC は、既存の値 (0.25) すべてを、リンク先の唯一のページAに転送します。Dには 3 つのアウトバウンド リンクがあるため、既存の値の 3 分の 1、つまり約 0.083 をAに転送します。この反復が完了すると、ページAの PageRank は約 0.458 になります。

${\displaystyle PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}.\,}$

言い換えれば、アウトバウンドリンクによって付与される PageRank は、ドキュメント自体の PageRank スコアをアウトバウンドリンクの数L( )で割った値に等しくなります。

${\displaystyle PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D) }{L(D)}}.\,}$

一般的なケースでは、任意のページuの PageRank 値は次のように表されます。

${\displaystyle PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}}$、

つまり、ページuの PageRank 値は、セットB _u (ページuにリンクしているすべてのページを含むセット) に含まれる各ページvの PageRank 値を、ページvからのリンクの数L ( v )で割った値に依存します。

PageRank 理論では、リンクをランダムにクリックしている架空のサーファーは、最終的にはクリックをやめると考えられています。どの段階でも、その人がリンクをたどり続ける確率は減衰係数dです。代わりにランダムなページにジャンプする確率は1 - dです。さまざまな研究で異なる減衰係数がテストされていますが、一般的に減衰係数は 0.85 程度に設定されると考えられています。^[5]

減衰係数は1から減算され（アルゴリズムのいくつかのバリエーションでは、その結果がコレクション内の文書数（N）で割られる）、この項は減衰係数と入力されるPageRankスコアの合計の積に加算されます。つまり、

${\displaystyle PR(A)={1-d \over N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}$

したがって、どのページの PageRank も、大部分は他のページの PageRank から算出されます。ダンピング係数は、算出された値を下げるように調整します。ただし、元の論文では次の式が示されており、混乱を招いています。

${\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}$

これらの違いは、最初の式では PageRank 値の合計が 1 になるのに対し、2 番目の式では各 PageRank にNを掛けて合計がNになることです。Pag​​e と Brin の論文にある「すべての PageRank の合計は 1 である」という記述^{[5]と、他の Google 社員の主張[32]}は、上記の式の最初の変形を支持しています。

ペイジとブリンは、彼らの最も人気のある論文「大規模ハイパーテキストウェブ検索エンジンの構造」の中で、2つの式を混同し、後者の式がウェブページ上の確率分布を形成すると誤って主張した。^[5]

Google は、Web をクロールしてインデックスを再構築するたびに PageRank スコアを再計算します。Google がコレクション内のドキュメント数を増やすと、すべてのドキュメントの PageRank の初期近似値は減少します。

この式では、ランダム サーファーが数回クリックして目的のサイトに到達し、その後ランダムなページに切り替えるというモデルを使用します。ページの PageRank 値は、ランダム サーファーがリンクをクリックしてそのページにたどり着く可能性を反映します。これは、状態がページ、遷移がページ間のリンクであるマルコフ連鎖として理解できます。これらはすべて同じ確率です。

ページに他のページへのリンクがない場合、そのページはシンクとなり、ランダム サーフィン プロセスは終了します。ランダム サーファーがシンク ページに到達すると、別のURL をランダムに選択し、再びサーフィンを続けます。

PageRank を計算する際、アウトバウンド リンクのないページは、コレクション内の他のすべてのページにリンクしているとみなされます。したがって、それらの PageRank スコアは、他のすべてのページに均等に分割されます。言い換えると、シンクではないページに対して公平を期すために、これらのランダムな遷移は Web 内のすべてのノードに追加されます。この残差確率dは通常、平均的なサーファーがブラウザーのブックマーク機能を使用する頻度から推定して 0.85 に設定されます。したがって、式は次のようになります。

${\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}$

ここで、は検討中のページ、は にリンクするページのセット、はページ の外部リンクの数、 はページの合計数です。 ${\displaystyle p_{1},p_{2},...,p_{N}}$${\displaystyle M(p_{i})}$${\displaystyle p_{i}}$${\displaystyle L(p_{j})}$${\displaystyle p_{j}}$${\displaystyle N}$

PageRankの値は、各列の合計が1になるように再スケールされた、修正隣接行列の支配的な右固有ベクトルのエントリです。これにより、PageRankは特に洗練された指標になります。固有ベクトルは

${\displaystyle \mathbf {R} ={\begin{bmatrix}PR(p_{1})\\PR(p_{2})\\\vdots \\PR(p_{N})\end{bmatrix}}}$

ここでRは方程式の解である。

${\displaystyle \mathbf {R} ={\begin{bmatrix}{(1-d)/N}\\{(1-d)/N}\\\vdots \\{(1-d)/N} \end{bmatrix}}+d{\begin{bmatrix}\ell (p_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\vdots \\\vdots &&\ell (p_{i},p_{ j})&\\\ell (p_{N},p_{1})&\cdots &&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R} }$

ここで、隣接関数は、ページjからページiへのアウトバウンドリンクの数とページjのアウトバウンドリンクの総数の比である。ページがにリンクしていない場合は隣接関数は0であり、各jについて、${\displaystyle \ell (p_{i},p_{j})}$${\displaystyle p_{j}}$${\displaystyle p_{i}}$

${\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1}$、

つまり、各列の要素の合計は 1 になるので、行列は確率行列になります (詳細については、以下の計算セクションを参照してください)。したがって、これはネットワーク分析で一般的に使用される固有ベクトル中心性測定の変形です。

上記の修正隣接行列の大きな固有ギャップのため、 ^[33] PageRank固有ベクトルの値は、わずか数回の反復で高い精度で近似することができます。

Googleの創設者たちは、オリジナルの論文^[31]で、 3億2200万のリンク（インエッジとアウトエッジ）からなるネットワークのPageRankアルゴリズムは、52回の反復で許容範囲内に収束すると報告しました。この半分のサイズのネットワークでは、収束には約45回の反復が必要でした。このデータから、彼らはアルゴリズムが非常にうまくスケーリング可能であり、非常に大規模なネットワークのスケーリング係数は、ネットワークのサイズnに対してほぼ線形であると結論付けました。 ${\displaystyle \log n}$

マルコフ理論の結果として、ページの PageRank は、多数のクリックの後にそのページに到達する確率であることが示されています。これは、ページからそのページに戻るために必要なクリック数 (またはランダム ジャンプ数) の 期待値に等しくなります。${\displaystyle t^{-1}}$${\displaystyle t}$

PageRank の主な欠点の 1 つは、古いページが優遇されることです。新しいページは、たとえ非常に優れたページであっても、既存のサイト ( Wikipediaなどの密に接続されたページのセット) の一部でない限り、多くのリンクを持つことはありません。

PageRankの計算を高速化するためのいくつかの戦略が提案されている。^[34]

検索結果のランキングを向上させ、広告リンクを収益化するために、PageRank を操作するさまざまな戦略が協調して採用されてきました。これらの戦略は、Web コミュニティで実際にどのドキュメントが評価されているかを判断することを目的とする PageRank の概念^[要出典]の信頼性に深刻な影響を及ぼしました。

Google は、有料テキストリンクを販売するサイトに対して積極的なペナルティを課し始めた 2007 年 12 月以来、リンク ファームや PageRank を人為的に高めることを目的としたその他の手法と戦ってきました。Google がリンク ファームやその他の PageRank 操作ツールを特定する方法は、Google の企業秘密です。

PageRankは反復法または代数法で計算できます。反復法は累乗反復法^{[35] [36]}または累乗法 として考えることができます。実行される基本的な数学的演算は同じです。

では、初期確率分布が仮定され、通常は ${\displaystyle t=0}$

${\displaystyle PR(p_{i};0)={\frac {1}{N}}}$。

ここで、N はページの総数であり、時刻 0 ではページ i です。 ${\displaystyle p_{i};0}$

各時間ステップで、上記の計算により、

${\displaystyle PR(p_{i};t+1)={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j};t)}{L(p_{j})}}}$

ここでdは減衰係数であり、

または行列表記で

ここで、およびは1 のみを含む 長さの列ベクトルです。${\displaystyle \mathbf {R} _{i}(t)=PR(p_{i};t)}$${\displaystyle \mathbf {1} }$${\displaystyle N}$

行列は次のように定義される。 ${\displaystyle {\mathcal {M}}}$

${\displaystyle {\mathcal {M}}_{ij}={\begin{cases}1/L(p_{j}),&{\mbox{if }}j{\mbox{ links to }}i\ \\0,&{\mbox{otherwise}}\end{cases}}}$

つまり、

${\displaystyle {\mathcal {M}}:=(K^{-1}A)^{T}}$、

ここで、は グラフの隣接行列を表し、は対角線に出次数を持つ対角行列です。 ${\displaystyle A}$${\displaystyle K}$

確率計算は各ページに対してある時点で行われ、次の時点で繰り返される。計算は、ある小さな${\displaystyle \epsilon }$

${\displaystyle |\mathbf {R} (t+1)-\mathbf {R} (t)|<\epsilon }$、

つまり、収束が想定される場合です。

行列が遷移確率、すなわち列確率であり、が確率分布（すなわち、、ここではすべて1の行列）である場合、式（2）は次式と同等である。 ${\displaystyle {\mathcal {M}}}$${\displaystyle \mathbf {R} }$${\displaystyle |\mathbf {R} |=1}$${\displaystyle \mathbf {E} \mathbf {R} =\mathbf {1} }$${\displaystyle \mathbf {E} }$

したがって、PageRankは の主固有ベクトルです。これを計算するための高速で簡単な方法は、べき乗法を使用することです。任意のベクトル から始めて、演算子を連続して適用します。つまり、 ${\displaystyle \mathbf {R} }$${\displaystyle {\widehat {\mathcal {M}}}}$${\displaystyle x(0)}$${\displaystyle {\widehat {\mathcal {M}}}}$

${\displaystyle x(t+1)={\widehat {\mathcal {M}}}x(t)}$、

それまで

${\displaystyle |x(t+1)-x(t)|<\epsilon }$。

式（３）の右辺の括弧内の行列は次のように解釈できること に注意されたい。

${\displaystyle {\frac {1-d}{N}}\mathbf {E} =(1-d)\mathbf {P} \mathbf {1} ^{t}}$、

ここで、は初期確率分布である。現在のケースでは ${\displaystyle \mathbf {P} }$

${\displaystyle \mathbf {P} :={\frac {1}{N}}\mathbf {1} }$。

最後に、にゼロ値のみを持つ列がある場合、それらを初期確率ベクトル に置き換える必要があります 。言い換えると、 ${\displaystyle {\mathcal {M}}}$${\displaystyle \mathbf {P} }$

${\displaystyle {\mathcal {M}}^{\prime }:={\mathcal {M}}+{\mathcal {D}}}$、

ここで行列は次のように定義される。 ${\displaystyle {\mathcal {D}}}$

${\displaystyle {\mathcal {D}}:=\mathbf {P} \mathbf {D} ^{t}}$、

と

${\displaystyle \mathbf {D} _{i}={\begin{cases}1,&{\mbox{if }}L(p_{i})=0\ \\0,&{\mbox{otherwise}}\end{cases}}}$

この場合、上記の 2 つの計算は、結果が正規化された場合にのみ同じ PageRank を生成します。 ${\displaystyle {\mathcal {M}}}$

${\displaystyle \mathbf {R} _{\textrm {power}}={\frac {\mathbf {R} _{\textrm {iterative}}}{|\mathbf {R} _{\textrm {iterative}}|}}={\frac {\mathbf {R} _{\textrm {algebraic}}}{|\mathbf {R} _{\textrm {algebraic}}|}}}$。

 numpyを npとして インポートする

def  pagerank ( M ,  d :  float  =  0.85 ): 
"""反復回数を明示的に指定した PageRank アルゴリズム。隣接行列内のノード (ページ) のランキングを返します。    

    パラメータ
    ---------- 
    M : numpy 配列
        隣接行列。ここで、M_i,j は 'j' から 'i' へのリンクを表し、すべての 'j' について
        sum(i, M_i,j) = 1 となります
    。d : float、オプションの
        減衰係数、デフォルトは 0.85

    戻り値
    ------- 
    numpy配列
        v_iが[0, 1]からi番目の順位であるような順位のベクトル。

    """ 
    N  =  M . shape [ 1 ] 
    w  =  np . ones ( N )  /  N 
    M_hat  =  d  *  M 
    v  =  M_hat  @  w  +  ( 1  -  d ) 
    while ( np . linalg . norm ( w  -  v )  >=  1e-10 ): 
        w  =  v 
        v  =  M_hat  @  w  +  ( 1  -  d ) 
    return  v

M  =  np .配列([[ 0 ,  0 ,  0 ,  0 ], 
              [ 0 ,  0 ,  0 ,  0 ], 
              [ 1 ,  0.5 ,  0 ,  0 ], 
              [ 0 ,  0.5 ,  1 ,  0 ]]) 
v  = ページランク( M ,  0.85 )

無向グラフ のPageRankは、統計的にはグラフの次数分布に近いが^[37]、一般的には同一ではない。が上で定義したPageRankベクトルで、が次数分布ベクトルである 場合${\displaystyle G}$${\displaystyle G}$${\displaystyle R}$${\displaystyle D}$

${\displaystyle D={1 \over 2|E|}{\begin{bmatrix}\deg(p_{1})\\\deg(p_{2})\\\vdots \\\deg(p_{N})\end{bmatrix}}}$

ここで、は頂点の次数、はグラフの辺集合を表す。すると、 を用いて、^[38]は次のことを示す。 ${\displaystyle \deg(p_{i})}$${\displaystyle p_{i}}$${\displaystyle E}$${\displaystyle Y={1 \over N}\mathbf {1} }$

${\displaystyle {1-d \over 1+d}\|Y-D\|_{1}\leq \|R-D\|_{1}\leq \|Y-D\|_{1},}$

つまり、無向グラフの PageRank は、グラフが正則である場合、つまりすべての頂点の次数が同じである場合にのみ、次数分布ベクトルに等しくなります。

相互作用する2つのオブジェクトグループをランク付けする場合のPageRankの一般化は、Daugulisによって説明されました。^[39]アプリケーションでは、重み付き関係がオブジェクトペアに定義されている2種類のオブジェクトを持つシステムをモデル化する必要がある場合があります。これは、二部グラフの検討につながります。このようなグラフでは、頂点分割セットに対応する2つの関連する正または非負の既約行列を定義できます。両方のグループのオブジェクトのランキングを、これらの行列の最大正の固有値に対応する固有ベクトルとして計算できます。ノルムされた固有ベクトルが存在し、ペロン定理またはペロン–フロベニウスの定理によって一意です。例: 消費者と製品。関係の重みは、製品の消費率です。

Sarma らは、ネットワーク内のノードの PageRank を計算するための2 つのランダムウォークベースの分散アルゴリズムについて説明しています。 ^[40] 1 つのアルゴリズムは、任意のグラフ (有向グラフまたは無向グラフ) で高い確率でラウンドを実行します。ここで、n はネットワーク サイズ、 はPageRank 計算で使用されるリセット確率 (減衰係数と呼ばれる) です。彼らはまた、無向グラフでラウンドを実行するより高速なアルゴリズムも提示しています。両方のアルゴリズムでは、各ノードはラウンドごとに、ネットワーク サイズ n の多重対数であるビット数を処理して送信します。 ${\displaystyle O(\log n/\epsilon )}$${\displaystyle \epsilon }$${\displaystyle 1-\epsilon }$${\displaystyle O({\sqrt {\log n}}/\epsilon )}$

Googleツールバーには長い間、訪問したページの PageRank を 0 (最も人気がない) から 10 (最も人気がある) までの整数で表示する PageRank 機能がありました。Google はツールバー PageRank 値を決定する具体的な方法を公表していませんでした。これはウェブサイトの価値の大まかな指標に過ぎないと考えられていました。「ツールバー PageRank」は、Google ウェブマスター ツール インターフェースを通じて、認証されたサイト管理者に提供されていました。しかし、2009 年 10 月 15 日、Google の従業員は、同社がウェブマスター ツール セクションから PageRank を削除したことを確認し、「私たちは長い間、PageRank にあまり重点を置くべきではないと人々に伝えてきました。多くのサイト所有者は、PageRank が追跡すべき最も重要な指標であると考えているようですが、これはまったく事実ではありません」と述べました。^[41]

「ツールバーの PageRank」はめったに更新されませんでした。最後に更新されたのは 2013 年 11 月です。2014 年 10 月、マット カッツは、今後は目に見える PageRank の更新は行われないことを発表しました。^[42] 2016年 3 月、Google はこの機能のサポートを終了し、基盤となる API はまもなく動作を停止すると発表しました。^[43] 2016 年 4 月 15 日、Google は Google ツールバーでの PageRank データの表示を無効にしましたが、^[44] PageRank は引き続き内部的に検索結果のコンテンツのランク付けに使用されました。^[45]

検索エンジン結果ページ(SERP) は、キーワード クエリに応じて検索エンジンによって返される実際の結果です。SERP は、関連するテキスト スニペット、有料広告、おすすめのスニペット、Q&A を含む Web ページへのリンクの一覧で構成されています。Web ページの SERP ランクは、SERP 上の対応するリンクの配置を指し、配置が高いほど SERP ランクが高くなります。Web ページの SERP ランクは、PageRank だけでなく、比較的大規模で継続的に調整される一連の要素 (200 以上) の関数です。^{[46] [信頼できない情報源? ]} 検索エンジン最適化(SEO) は、Web サイトまたは Web ページ セットの SERP ランクに影響を与えることを目的としています。

キーワードに対する Google の SERP でのウェブページの順位は、関連性と評判、つまり権威と人気によって決まります。Pag​​eRank は、ウェブページの評判に対する Google の評価を示す指標です。キーワードに固有のものではありません。Google は、ウェブページとウェブサイトの権威を組み合わせて、キーワードを競うウェブページの全体的な権威を判断します。^[47]ウェブサイトのホームページの PageRank は、Google が提供するウェブサイトの権威に関する最良の指標です。^[48]

Google Placesが主流のオーガニック検索結果ページに導入されて以来、PageRankに加えて数多くの他の要素がローカルビジネスの結果におけるビジネスのランキングに影響を及ぼしています。^[49] Googleが2016年3月のQ&AでPageRank廃止の理由を詳しく説明したとき、リンクとコンテンツがトップランキング要素であると発表しました。RankBrainは2015年10月に第3位のランキング要素として発表されていたため、トップ3要素はGoogleによって正式に確認されました。^[50]

GoogleディレクトリのPageRank は 8 単位の測定でした。緑色のバーにマウスオーバーすると PageRank の数値が表示される Google ツールバーとは異なり、Google ディレクトリではバーのみが表示され、数値は表示されませんでした。Google ディレクトリは 2011 年 7 月 20 日に閉鎖されました。^[51]

ツールバーに表示される PageRank は簡単に 偽装できることが知られていました。HTTP 302応答または「Refresh」メタ タグを介して 1 つのページから別のページにリダイレクトすると、ソース ページは宛先ページの PageRank を取得します。したがって、PR 0 でリンクがまったくない新しいページは、Google ホームページにリダイレクトすることで PR 10 を取得できます。偽装は通常、ソース URL の Google 検索を実行することで検出できます。結果にまったく別のサイトの URL が表示された場合、後者の URL がリダイレクト先を表している可能性があります。

検索エンジン最適化の目的で、一部の企業はウェブマスターに高ページランクのリンクを販売することを提案しています。^[52]高 PR ページからのリンクはより価値があると考えられるため、より高価になる傾向があります。トラフィックを促進し、ウェブマスターのリンク人気を高めるために、質の高い関連サイトのコンテンツ ページでリンク広告を購入することは、効果的で実行可能なマーケティング戦略になる可能性があります。ただし、Google は、ウェブマスターがページランクと評判を与える目的でリンクを販売している、または販売していることが判明した場合、そのリンクは価値が下げられる (他のページのページランクの計算では無視される) と公に警告しています。売買の慣行^[53]は、ウェブマスター コミュニティ全体で激しく議論されています。Google は、有料リンクにnofollow HTML 属性値を使用するようにウェブマスターにアドバイスしました。Matt Cuttsによると、Google はシステムを操作して Google 検索結果の品質と関連性を低下させようとするウェブマスターを懸念しています。^[52]

2019年にGoogleは、PageRankを渡さず、SEOリンク操作に価値がない新しいタイプのタグを提供しました。コメントなどのユーザー生成コンテンツ用のタグとしてrel="ugc"、広告やその他の種類のスポンサーコンテンツ用のタグとしてrel="sponsored"です。^[54]

PageRankはSEOの目的においてそれほど重要ではなくなったが、より人気のあるウェブサイトからのバックリンクの存在は、ウェブページを検索ランキングの上位に押し上げ続けている。^[55]

よりインテリジェントなサーファー。サーファーが探しているページの内容とクエリ用語に応じて、確率的にページ間を移動する。このモデルは、クエリに依存するページの PageRank スコアに基づいており、その名前が示すように、これもクエリの関数である。複数用語のクエリ が与えられると、サーファーは何らかの確率分布 に従ってを選択し、その用語を使用して多数のステップで動作を誘導する。次に、分布 に従って別の用語を選択して動作を決定する、というように繰り返す。訪問したウェブページ全体の分布の結果が QD-PageRank である。^[56]${\displaystyle Q=\{q1,q2,\cdots \}}$${\displaystyle q}$${\displaystyle P(q)}$

PageRankの数学は完全に一般化されており、あらゆる分野のあらゆるグラフやネットワークに適用できます。そのため、PageRankは現在、書誌学、ソーシャルおよび情報ネットワーク分析、リンク予測および推奨に頻繁に使用されています。また、道路ネットワークのシステム分析、生物学、化学、神経科学、物理学でも使用されています。^[57]

PageRank は研究者の科学的影響力を定量化するために使用されています。基礎となる引用とコラボレーション ネットワークは、PageRank アルゴリズムと組み合わせて使用​​され、個々の著者に伝播する個々の出版物のランキング システムを作成します。Pag​​eRank インデックス (Pi) と呼ばれる新しいインデックスは、h インデックスが示す多くの欠点を考慮すると、h インデックスよりも公平であることが実証されています。^[58]

生物学におけるタンパク質ネットワークの解析にはPageRankも有用なツールである。^{[59] [60]}

どのような生態系でも、PageRankの修正版は環境の継続的な健全性に不可欠な種を特定するために使用できる可能性がある。^[61]

PageRankの同様の新しい用途は、博士課程の卒業生を教員に採用した実績に基づいて、学術博士課程をランク付けすることです。Pag​​eRankの用語では、学術部門は、お互いに（そして自分自身から）教員を採用することで、互いにリンクしています。^[62]

PageRankのバージョンは、従来の科学情報研究所（ISI）のインパクトファクター^[63]の代わりとして最近提案され、EigenfactorとSCImagoで実装されました。ジャーナルへの引用数を単に合計するのではなく、各引用の「重要性」がPageRank方式で決定されます。

神経科学では、ニューラルネットワーク内のニューロンのPageRankは、その相対的な発火率と相関関係にあることがわかっています。 ^[64]

パーソナライズされたPageRankはTwitterによって、ユーザーがフォローしたいと思われる他のアカウントを提示するために使用されます。^[65]

Swiftypeのサイト検索製品は、各ウェブサイトの重要性のシグナルを調べ、ホームページからのリンクの数などの要素に基づいてコンテンツを優先順位付けすることで、「個々のウェブサイトに固有のPageRank」を構築します。^[66]

ウェブクローラーは、ウェブのクロール中にどの URL にアクセスするかを決定するために使用する重要度指標の 1 つとして PageRank を使用することがあります。Googleの創設に使用された初期のワーキング ペーパー^{[67]の 1 つに}「URL 順序付けによる効率的なクロール」があります。^[68]では、Google がサイトをどの程度深く、どの程度クロールするかを決定するために、さまざまな重要度指標を使用することが説明されています。Pag​​eRank はこれらの重要度指標の 1 つとして提示されていますが、URL のインバウンド リンクとアウトバウンド リンクの数、サイトのルート ディレクトリから URL までの距離など、他の指標も挙げられています。

PageRank は、ブログ圏のようなコミュニティが Web 全体に及ぼす明らかな影響を測定する方法論としても使用できます。したがって、このアプローチでは、スケールフリー ネットワークパラダイムを反映して、PageRank を使用して注目度の分布を測定します。^{[引用が必要]}

2005年、パキスタンで行われたパイロットスタディ「構造的ディープデモクラシー」では、持続可能な農業グループのコンタクトユースにおけるリーダー選出にSD2 ^{[69] [70]が使用された。SD2は推移的代理投票の処理に}PageRankを使用するが、投票者1人につき少なくとも2人の初期の代理を義務付けるという制約が追加され、すべての投票者が代理候補者となる。SD2の上に、専門家代理や特定の問題に対する直接投票を追加するなど、より複雑なバリアントを構築することもできるが、基礎となる包括的システムとしてのSD2では、常に一般代理を使用することが義務付けられている。

スポーツの分野では、PageRankアルゴリズムは、米国のナショナルフットボールリーグ（NFL）のチーム、^[71] サッカー選手個人、^[72]ダイヤモンドリーグのアスリートのパフォーマンスをランク付けするために使用されています。^[73]

PageRankは、空間や道路をランク付けして、個々の空間や道路に何人の人（歩行者または車両）が来るかを予測するために使用されてきました。^{[74] [75]}語彙意味論では、Word Sense Disambiguationや^[76] 意味的類似性の実行に使用され、^[77]また、WordNet synsetsを、肯定性や否定性などの特定の意味的特性をどの程度強く持っているかに応じて自動的にランク付けするためにも使用されています。^[78]

交通システムがどのように動作モードを変えるかは、交通流の相関構造における準定常状態間の遷移によって説明できます。Pag​​eRankは、交通システムにおけるこれらの準定常状態の中で支配的な状態を識別し、調査するために使用されてきました。^[79]

2005年初頭、GoogleはHTMLのリンクとアンカー要素のrel属性に新しい値「 nofollow」^{[80]を実装しました。これにより、ウェブサイト開発者や}ブロガーは、 GoogleがPageRankの目的で考慮しないリンクを作成できるようになりました。これらのリンクは、PageRankシステムで「投票」を構成しなくなりました。nofollow関係は、スパムデクシングに対抗する試みとして追加されました。

たとえば、以前は、自分のウェブサイトへのリンクを含む掲示板の投稿を多数作成して、PageRank を人為的に高めることができました。nofollow 値を使用すると、掲示板の管理者はコードを変更して、投稿内のすべてのハイパーリンクに「rel='nofollow'」を自動的に挿入し、特定の投稿が PageRank に影響しないようにすることができます。ただし、この回避方法には、正当なコメントのリンク値を減らすなど、さまざまな欠点もあります。(参照:ブログのスパム#nofollow )

ウェブサイト内のページ間の PageRank の流れを手動で制御するために、多くのウェブマスターは PageRank Sculpting ^[81]と呼ばれる手法を実践しています。これは、ウェブサイトの特定の内部リンクに nofollow 属性を戦略的に配置し、ウェブマスターが最も重要とみなしたページに PageRank を集中させる行為です。この戦術は nofollow 属性の導入以来使用されていましたが、Google が nofollow で PageRank の転送をブロックしても、その PageRank が他のリンクにリダイレクトされないと発表したため、もはや効果的ではない可能性があります。^[82]

• 注意力の不平等
• チェイランク
• ドメイン権限
• EigenTrust — 分散型 PageRank アルゴリズム
• Google 爆撃
• Google ハミングバード
• Google マトリックス
• グーグルパンダ
• Googleペンギン
• Google検索
• ヒルトップアルゴリズム
• カッツ中心性- ページランクと密接に関連する 1953 年のスキーム
• リンク構築
• 検索エンジン最適化
• SimRank — ランダムサーファーモデルに基づくオブジェクト間の類似性の尺度
• トラストランク
• VisualRank - Google の画像検索への PageRank の応用
• ウェブグラフ