ページランク( Page Rank )

はじめに

ページランクの仕組み 、アルゴリズムを意外と知らない人は多いと思います。ページランクアルゴリズムはGoogleの創業者であるLawrence Page とSergey Brinにより考案されました。今や世界を支えていると言われる検索エンジンアルゴリズムはとてもシンプルな式でした。

PR(webPage_x) = (1-d) + d \times (\frac{ PR(webPage_1)}{Count(webPage_1)} + ... + \frac{ PR(webPage_n)}{ Count(webPage_n)})

PR()はページランクを表します。最初は定まっていないので初期値として全てのページに適当な値を入れますが1を入れるケースが多いです。

dは減衰率でオリジナルの論文では0.85として設定されています。

Count()はWebページが持つリンクの数です。たとえばWebPage1がリンクを10個持っていればC( WebPage1 ) は10となります。

上記式をみると、自分のページランクをリンク数で除算し分け与えているという意味となります。こんな単純なアルゴリズムから世界を変えるほどの技術となっているのは本当に驚きです。

さて実際の計算しページランクがどのように更新されるのか見てみます。

Page Rankを計算してみる

以下のようなページがあったと仮定します。

AはB,C,Dへバックリンクを貼る、BはDへ、CはA, Dへ。DはA,Cにリンクを貼る。それぞれ、Count(A) = 3, Count( B ) = 1, Count( C ) = 2, Count( D ) = 2となる。

今、4つのウェブページがあり、それぞれリンクを張っています。Aは3つ、Bは1つ、Cは2つ、Dは2つリンクを張っています。このリンクを貼られたという関係を表すと次のようになります

AからB から C から D から
Aへ0011
Bへ 1000
Cへ 1001
Dへ 1110

例えば、Aは(B,C,D)にリンクを張っていますので(B,C,D)にそれぞれ1を立てました。

続いて確率モデルの表を先の表から作成します。今Aのリンク数、Count(A)は3です。Aが他のサイト(B,C,D)への分配数はその逆数である1/3ずつが分配されます。上の表をそれぞれのリンク数で除算し,作成された表は次のとおりです。

AからB から C から D から
Aへ00\frac{1}{2}\frac{1}{2}
Bへ \frac{1}{3}000
Cへ \frac{1}{3}00\frac{1}{2}
Dへ \frac{1}{3}1\frac{1}{2}0

行列の縦軸に注目すると、合計が必ず1になっていることに気づくと思います。また、マイナスの値が入っておりません。一般的にこうした行列のことを確率行列( column-stochastic matrix)と呼びます。

ページランクベクトルを用意し、先の式に適用していくとページランクが出てきます。今、初期値のページランクを1とします。

PR(A) = 1, PR(B) = 1, PR(C)=1, PR(D)=1

準備がととのったのでページランクを計算します。わかりやすさを重視するために愚直なコード、いわゆるベタ書きコードで表します。実際のプログラムでは、100万ページがあってもエレガントに解けるようなソースコードの書き方を目指してください。

def main():
    # PageRank初期値                                                                                                                                                                                                              
    PR = {'A': 1.0, 'B': 1.0, 'C':1.0, 'D': 1.0 }
    # リンク数の逆数(確率)                                                                                                                                                                                                      
    Prob = {'A': 1/3.0, 'B': 1, 'C':1/2.0, 'D': 1/2.0 }
    # 減衰率                                                                                                                                                                                                                      
    d = 0.85
    # 10回回す                                                                                                                                                                                                                    
    for i in range( 10 ):
        new_PR_A = PR[ 'C' ] * Prob[ 'C' ] + PR[ 'D' ] * Prob[ 'D' ]
        new_PR_B = PR[ 'A' ] * Prob[ 'A' ]
        new_PR_C = PR[ 'A' ] * Prob[ 'A' ] + PR[ 'D' ] * Prob[ 'D' ]
        new_PR_D = PR[ 'A' ] * Prob[ 'A' ] + PR[ 'B' ] * Prob[ 'B' ] + PR[ 'C' ] * Prob[ 'C' ]

        PR[ 'A' ] = (1-d) + d * new_PR_A
        PR[ 'B' ] = (1-d) + d * new_PR_B
        PR[ 'C' ] = (1-d) + d * new_PR_C
        PR[ 'D' ] = (1-d) + d * new_PR_D
    # 新しい値を出力
        print( "%.4f %.4f %.4f %.4f" % (PR[ 'A' ], PR[ 'B' ], PR[ 'C' ], PR[ 'D' ] ) )
if __name__ == '__main__':
    main()

10回ぶん回した結果は次のとおりです。段々と値が安定しているのがわかります。

ページ数や構造がシンプルな例でページランクの計算方法をみてみましたが、実装がシンプルであり、とてもわかり易いアルゴリズムであると思います。ただ、世の中のモデルがこのように単純な問題であるとは限りません。例えばリンクを貼られていないページがあるとどのような問題がでてくるのでしょうか。

Rank Sinks問題

あるページがリンクを全く持っていない問題のことをRank sinks 問題と呼びます。例えば次のようなケースの場合です。

Dが最後になっている場合、Rank Sinksと言われています。流しのシンクのようになっているからです。Dはリンクを持っていないので移動する確率は0であり、周りからページランクをもらうだけです。Dは必然とページランクが上がる一方で、他に配る宛もなく、これは公平ではありません。

この場合はシンクDの移動確率は、全ページ数の逆数を利用することで問題解決を図ります。今(A,B,C,D)と総ページ数4ですので1/4がDの移動確率として定義されます。

AからB から C から D から
Aへ00\frac{1}{2}\frac{1}{4}
Bへ \frac{1}{3}00\frac{1}{4}
Cへ \frac{1}{3}00\frac{1}{4}
Dへ \frac{1}{3}1\frac{1}{2} \frac{1}{4}

全ページ数の逆数である理由は、最後にたどり着いたページからランダムに別のページに行く確率は等確率である、という仮定に基づいています。

注意(ページランクのもう一つの式

ページランクの式としてはNで割る場合もあります。

PR(A) = \frac{(1-d)}{N} + d \times (\frac{ PR(webPage_1)}{Count(webPage_1)} + ... + \frac{ PR(webPage_n)}{ Count(webPage_n)})

最初の項目でNという項目が入っただけです。Nはページ数を表しており、先の例であれば4が入ります。この修正された式の理由は全てのページランクの合計は1である、つまり確率モデルとして正しい形を求めた為です。従って本質的な意味の違いはありません

ところで、PageRankのアルゴリズムはマルコフ連鎖であるといわます。マルコフ連鎖とはざっくりいうと、次の状態は前の状態からのみ決定されるというものです。ページランクのアルゴリズムを観ると分かる通り、一つ前の状態からしか次のページランクは影響をうけません。そのため、マルコフ連鎖を仮定してという言い方がされます。

ページランクの仕組みは理解できましたでしょうか?当サイトが皆さんの知識の工場に役立ってもらえれば幸いです。

参考サイト

関連記事

投稿者: 等々力 康弘

画像処理エンジニア。組み込みソフト出身。 株式会社モルフォにてR&D部門、主に機械学習業務に携わり、顔認識&顔検出のアルゴリズム開発に従事。国内特許数件、国際特許1件。 モルフォ社退社後、株式会社Dynaptico創業(CEO)。アメリカ人、スウェーデン人と3名とフードデリバリーサイトmaishoku.comを立ち上げる。社長業の他、開発業務においてバックグラウンド関連全般(Djangoを用いいたバックエンドサーバ&APIサーバーの作成、 リバースプロキシなどの負荷分散サーバ関連、OCRプログラムの作成、CISCOルータの管理, 、seleniumを用いたテストサーバーの構築、Androidアプリの開発等々)に携わる。 2019年DynapticoのCEOを辞職。 2020年2月にComputer Scienceに特化した株式会社OctOpt創業。 OSはUbuntu。Appleが苦手。Swiftのバージョンアップ対応とか死ぬほど嫌い。 Python/C++/C Twitter: @rocky_house シフト自動調整スケジュールサイトをVue.js+graphene djangoで構築. https://www.allshifter.com

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です