ネットワークサイエンスのPageRankを完全理解した話

こんにちは、DeNAデータアナリストの佐々木亮です。この記事では、Googleのwebページの表示ランキングへの活用で有名になったページランク（Pagerank）のアルゴリズムと、その問題点と解決策を整理していきます。

ざっくりPageRankとは？

Googleの検索エンジン最大の成功要因の一つとして引用されるPageRank。PageRankは、ウェブページの重要性を評価するためのアルゴリズムであり、Googleの創設者であるラリー・ペイジとセルゲイ・ブリンによって開発されました。

世の中にあるwebページは無数に繋がっています。たくさんのページからリンクを繋がれている人気のページや、どのwebページにもリンクを接続しないような孤立したページまで様々です。それらのWebページは決して等価ではないと考え、その順位づけをするために開発されました。この考え方のベースには、「ウェブページの重要性は、そのページへのリンクを持つ他のページに依存する」という考え方があります。

このシンプルながらも強力なアルゴリズムは、ウェブ上の情報錯綜から価値あるページを選別するだけでなく、その他多岐にわたる領域に影響を与える核となっています。

基本的な計算はものすごくシンプル

PageRankの計算は、webページを例に考えていくとわかりやすいです。

PageRankの考え方のベースは、そのページが他のページにどれだけ推薦されているか、というものです。つまり、どれだけの被リンクを受けているかが重要になってきます。あるユーザーが、ランダムにwebページを遷移していくことを考えながら、各ページをスコアリングしていくことで、ページごとのランクを決定していきます。

基本的には以下の式で表されます。

あるnode jのページランクは、隣接するノードが持つランクを、そのnodeがもつリンク（di）で割った値の話で表します。シンプルに3つのnodeで表現すると以下のようになります。

a, y, mの3つのnodeがあります。上記のようなリンクの接続の仕方をしている場合、a,y,mそれぞれに対するpage rankの計算式は以下のようになります。

aはm, yそれぞれに対して1本ずつ、合計2本のリンクを持っていることになります。そのためy, mのpage rankの計算にはaから受けるスコアはr_a/2 （aのもつ重みが2分割されて他に渡されるイメージ）になります。それをy, mそれぞれでも行うことで、PageRankが計算できます。

実際に計算する場合、初期状態はa, y, mそれぞれ1/3のスコアを持ち、ネットワーク全体で1になるようなスコアでおきます。そこから、上記の計算を繰り返し実施していき、収束する値を探っていきます。

その結果得られるのは以下です。

しかし単純なこの計算には、いくつかの問題点があります。これらの問題を考慮することで、現実問題にも利用可能なアルゴリズムが導き出されるので、それらもここで解説しておきます。

Dead EndとSpider Trapという問題点

Dead Endとは、行き止まりになっているnodeに入ってきたスコアが、iterationを回す中で消えてしまうことを指します。aからbに1回目のrank計算で1が受けたわされた後、2回目の計算でbは渡す先を持ちません。すると、次の計算のステップで持っているrankのスコアをどこにも渡せずにただ消費してしまい、0になります。

そのため、リンクを受けているにも関わらずページbの価値はないことになってしまいます。この構造になったから価値がなくなる、というわけではないため問題です。その解決方法として提案されたのが「ランダムテレポート」です。

ランダムテレポートとは、Dead Endのnodeから、自身を含むnodeにランダムにそのスコアを分け与えることです。下の図がその具体例です。

mからa, y, mそれぞれに1/3のパスを用意しておくことで、Dead Endでスコアが消えてしまう現象を防ぐことができます。次の問題点と合わせて、PageRankのアルゴリズムをアップデートするので、まずは2つの目の問題点を整理します。

もう一点の問題であるSpider Trapとは、行き止まりのnodeにiterationを回す中でランクスコアが溜まってしまい、重要でないにも関わらず大きなスコアを持ってしまうことを指します。

こちらの問題もランダムテレポートで解消できます。

a, y, mそれぞれのnodesにランダムテレポートパスを準備しておくことで、Spider Trapが発生した時の逃げ道ができ、yやmといった末端のself-loopをもつnodeにPageRankのスコアがたまらないようにできます。

上記2点はPageRankを分析する上で考慮するべき代表的な問題点です。これらを考慮したPageRankの計算式を次で示します。

ページランクの算出方法はコレ！

基本的なページランクの計算方法（第一項）に対して、Dead-end, Spider Trapを考慮した項（第二項）を組み合わせた計算式になっています。この時、βをダンピングファクターといいます。これは、PageRankをリンクの接続に従って計算する確率です。言い換えれば、1-βは、ランダムテレポートする確率となります。

例えばダンピングファクターが0.85の場合、85%の確率で現在のページからリンクされているページへ進み、15%の確率でランダムにどこかのページにジャンプするイメージです。

計算過程では、ウェブページへの推薦の価値を評価します。具体的には、一つのウェブページから他のページへのリンクが存在すれば、そのリンク元のページはリンク先のページを推薦しているとみなします。そして、リンク元のページ自体が多数の推薦（つまりリンク）を受けているほど、リンク元のページからリンク先への推薦の価値は高まります。

この計算は、すべてのウェブページのPageRankスコアが変わらなくなるまで、つまり値が安定する（収束する）まで繰り返し行われます。最終的な各ウェブページのPageRankスコアはそのページの”重要性”を示すものとなります。

初期状態ではすべてのページのPageRankスコアは均一に設定され、（例えばウェブ全体のページ数の逆数）その後、リンク構造に基づく計算のiterationが回され、各nodeのスコアが収束するまで行っていきます。

その結果、以下の図のようにフラットなnodeの重みのネットワークに対して、重要度を付与することが可能となります。

ここでは簡易的なネットワークを例としましたが、Googleのwebページの順位付けなど大規模なネットワークでも実装されています。

ネットワークを組み上げることで、SQLなどを利用した構造化データの分析では見ることができない、直接的なつながりの先のつながりからの影響までを考慮した重要度付けが可能になる点が、ネットワークサイエンスにおけるPageRankならではのポイントと考えられます。

まとめ

以上の事例を通して、ウェブインターネットが日常生活に広範に組み込まれる現代社会において、PageRankの重要性はますます増しています。一見すると複雑なシステムに思えるかもしれませんが、ネットワークの情時に報や影響力の流れを理解し、解析するための極めて有用なツールです。そしてその基本的な原理は、「推薦・リンクの多さ＝影響力」のシンプルな思想に基づいています。その影響力は非常に広範囲に及んでおり、インターネット利用だけでない場面でも今や当たり前のように利用されていることを理解しておくといいかもしれません。

参考資料

https://snap.stanford.edu/class/cs224w-2018/

https://buildersbox.corp-sansan.com/entry/2021/12/07/110000

https://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/pagerank.pdf

https://snap.stanford.edu/class/cs224w-readings/Brin98Anatomy.pdf