ページランクと被リンク数 - データサイエンティストのひよこ

ページランクとは

　ページランク（PageRank）とは、Google 検索エンジンで利用されているWebサイトの評価指数のことである。評価方法やそのビジネス利用において、Google創業者であるセルゲイ・ブリン、ラリー・ページが大学院在学中に開発したものであって、Googleの基幹技術であることは間違いない。ページランクは、より重要なウェブページからリンクされているウェブページほど重要であるという、再帰的な定義のもとに、ウェブページの重要度が評価されている。
　ページランクによって、個々のWEBサイトの重要度が指標化され、検索結果の順位に関わってくる。一見すると、どのようなウェブページが重要と判断されているのかが見えにくいこの定義だが、Google 検索エンジンにおけるSEOにおいて、その攻略は必要不可欠となってくる。ページランクを高める方法というものが知られていて、その一つが、被リンク数をとにかく増やすという技である。
　あれっ？おかしい。重要なウェブページからリンクされているウェブページほど重要であるという定義に対して、被リンク数増やすだけって本当？と言いたくなる。ここを、数理的に振り返りたい。もちろん、Googleの実運用の中ではページランクを原点のまま利用しているはずはない。ここでは、その数理学的な背景を紹介し、データ分析方法を作る・発想するということを行いたい。

ページランクの背景

　現在は、検索エンジンがウェブでの情報収集の玄関として、欠かせない存在となっている。検索エンジンの検索結果の上位に表示されるものを、順にたどっていけば大抵の欲しい情報にたどり着ける。ところが一昔前は、この検索エンジンというものが、存在していないかほぼ機能していなかった。黎明期の検索エンジンは、検索エンジンに自分のウェブサイトを登録し、登録したカテゴリにただ表示されるだけのリンク集だった。
gigazine.net

　大量のリンクが並ぶリンク集では閲覧者を呼び込むことは難しく、不特定多数に自分のウェブサイトに来てもらうためには、有名なウェブサイトにURLを教えて、バナーリンクを張ってもらうことだった。Googleが創業したのは、「ウェブ」がこのような時期であったときだ。ただのリンク集から、ロボット型検索エンジンとよばれるウェブサイトの順位付けアルゴリズムを基軸とする検索エンジンを作ったのがGoogleであり。そして、スタンフォード大学の大学院生のセルゲイ・ブリン、ラリー・ページである。
　在学中の研究内容は次のようなものである。この内容にプラスアルファの解説と前述した被リンク数をとにかく増やすという技が意味のある行為であることを解説したい。

Brin, S. & Page, L. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems 30, 107–117 (1998).
Page, L.; Brin, S.; Motwani, Rajeev; Winograd, Terry, The PageRank Citation Ranking: Bringing Order to the Web (1999).
- http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

ページランク

「より重要なウェブページからリンクされているウェブページほど重要である」というのは、評価方法における理念的なもので、実際には数式で表される。あるウェブサイトを評価しようと考えたとき、あるウェブサイトへの流入は、あるサイトからのリンクのクリックによる流入によって決まるものと考えられたため、ウェブサイトとそのハイパーリンク関係で重要度が決まると考えたようだ。そのため、ウェブサイトとウェブサイトの関係がネットワークとして扱われている。ウェブサイトをノード、ハイパーリンク関係をリンクとして、ネット空間を表してみる*1。
f:id:TamSan:20180923234902p:plain

ネットワーク解析はこのような不均質なつながりから、重要なものを取り出し、順位付けすることができる。このようなネットワークは、通常、隣接行列 $A$ と呼ばれる行列で定義する。

$A=(A_{ij})= \begin{cases} 1 & (ノードiからノードjにリンクがある) \\ 0 & (ノードiからノードjにリンクがない) \end{cases}$

たとえば、あるウェブサイト $i$ からウェブサイト $j$ へ、リンクが張られていたら、 $A_{ij}=1$ 、そうでなければ $A_{ij}=0$ となるネット空間のウェブサイト関係を表す行列である。この隣接行列を用いて、ウェブサイト $i$ のページランク $x_i$ は次の式 $s \rightarrow \infty$ の収束値である。

$\displaystyle x_i(s+1)= \sum _{l=1}^{N} \frac{A_{li}}{k_{l}}x_{l}(s)$

ここで、 $x_i(s+1)$ 、 $x_i(s)$ はページランクを計算するための仮想的なウェブサイト $i$ の重要度である。収束値がウェブサイト $i$ のページランク $x_i$ として意味を持つ。 $k_{l}$ はノード $l$ の出次数、つまりウェブサイト $l$ から張られるリンクの数である。式の右辺は $\frac{x_{l}(s)}{k_{l}}$ は、ある時点で重要度が $x_{l}(s)$ であるウェブサイト $l$ において、張られるリンクの数 $k_{l}$ で割って、一本の出ていくリンクを伝って、 $\frac{x_{l}(s)}{k_{l}}$ の量の重要度が分配されている意味になっている。つまり、ウェブサイト $i$ が、ウェブサイト $l$ からのリンクを通して、 $\frac{x_{l}(s)}{k_{l}}$ を得る。総量として $\displaystyle \sum _{l=1}^{N} \frac{A_{li}}{k_{l}}x_{l}(s)$ を受け取り、これが重要度 $x_i(s+1)$ と再帰的に定義される。
　実際のウェブサイト間の遷移関係は、リンクをたどるクリックだけのものではなくて、検索窓に入力して、非リンク的な遷移もある割合で存在することも考慮できる。

$\displaystyle x_i(s+1)= r \sum _{l=1}^{N} \frac{A_{li}}{k_{l}}x_{l}(s) +\frac{1-r}{N}$

以上のモデルが適切なのだが、今回は最も簡単なモデルのみ扱おう。つまり、 $r=1$ 。すべてリンクのクリックでウェブサイト間の遷移が起きるケースのみ考える。
　適当な初期値 $x_i(s) \equiv \frac{1}{N}$ を与えて、この重要度の分配（出リンク数で割って、等分配したものを隣接ノードに渡す）を行うと、値は徐々に収束していき、ページランクが得られるというものである。

f:id:TamSan:20180919004605p:plain

上図の例を見てもらえばわかるように、初期値として適当な値を設定したが、分配を繰り返すごとに各ノードの値は収束に向かっていくことが分かる*2。結果として、ページランクは収束値として、左上から時計回りに0.31、0.42、0.06、0.21と得られる。このように重要なものからリンクされているものほど重要であるという評価を再帰式で表し、数値として表すことができた。統計モデルとはちがい、何かの式を使ってあぶりだすというより、自分の評価基軸で式を作って、そこから数値を得るという過程がわかってくれただろうか。自分でモデルを作るというのは複雑系ではこういうことになる。

ページランクの特徴

ページランクの求め方を簡単に説明した。興味を持ってくれると、たくさん書いたかいがある。世界中の研究者もページランクの研究に興味を持ち、数学的、物理的、情報科学的、工学的に爆発的に研究された。

数学的
- 再帰式の収束性やその条件の明確化。
物理的
- ネットワーク上の拡散現象との等価性の発見。
- 複雑ネットワーク上のランダムウォークの拡張理論の発見。
情報科学
- 収束値の求値方法
工学的
- 中心性指標の改良
- 特許、論文などの書誌計量方法への応用

まだまだあるだろう。さて、特徴を知るために、この定義式から、性質を数理的に導いてみよう。最も簡単なのは、平均場近似という方法だ。平均場というのは、「自分以外がすべて平均的な傾向しか示さない環境」であり、自分以外は全部同じと仮定してしまうことだ。たとえば、ウェブサイト $i$ のページランク $x_i(\infty)$ に注目しているとき、そのウェブサイト以外のページランクや次数をすべて全体の平均値 $\bar{x}(\infty)$ 、 $\bar{k}$ に置き換えてしまうことだ。

$\displaystyle x_i(\infty) = \sum _{l=1}^{N} \frac{A_{li}}{k_{l}}x_{l}(\infty) \sim \sum _{l=1}^{N} \frac{A_{li}}{\bar{k}} \bar{x}(\infty) \sim \frac{\bar{x}(\infty)}{\bar{k}} \sum _{l=1}^{N} A_{li} \sim \frac{\bar{k}}{\bar{x}(\infty)} k_{i}^{in}$

つまり、ページランクは入次数に比例する量となるのだ。

$\displaystyle x_i(\infty) \sim k_{i}^{in}$

…。本当にこんな雑な近似で結論を言っていいのだろうか。もともと平均場近似は、厳密な計算が実行不可能なので、計算できるところまで簡単にして計算するためのものだ。この結果を用いて、厳密な結論を述べたり、批判したりするのはあまり意味がない。しかし、平均場近似は非常に特別で、必ずしも厳密解を与えるわけではないが、まったくの嘘でもない*3ということだけは言っておこう。以上の結論だけで言えば、ページランクを高めるためには、被リンク数を増やせばよいという結論が得られている。
　実際に、ネットワークの構造と得られるページランクの関係を見てみよう。ネットワークは適当な生成モデルから作ったものだ。横軸が被リンク数、縦軸がページランクである。灰色の各点が、あるノードの被リンクとページランクを表す点、黒点が横軸を区切って、代表値で表した点。赤線は総リンク数の逆数が係数の比例の直線である。

f:id:TamSan:20180924134802p:plain

　もちろん、基本的な理論には誤差がつき物だが、平均場近似解は実際の数値計算結果の傾向を非常によく表している。結局のところ、ページランクが以上のような定義であるうちは、良いウェブサイトからのリンク以上に、ただたくさん被リンクを増やすことで、ページランクを高めてしまうのである*4。
　あまりにも雑なのでもう少しそれっぽく解いてみよう。ページランクの定義式は、ウェブサイトネットワーク上の重要度のランダムウォークと考えられる*5。あるウェブサイトの重要度が出次数に等分配されて流れているということは、無限に小さい重要度が等確率で、ある一本の出次数を選んで、流れ出ていることになる。今度は、「詳細釣り合い」とよばれる平衡状態を特徴付ける状態を仮定して解く。

　少し話を単純化するためにすべてのリンクは相互リンクとしてしまう。あるウェブサイト $i$ からあるウェブサイト $j$ へ、 $t$ ステップでたどり着くための経路 $i \rightarrow l_1 \rightarrow l_2 \rightarrow \cdots \rightarrow l_{t-1} \rightarrow j$ を考えよう。「詳細釣り合い」とは、平衡状態において、 $i \rightarrow j$ の流れと、 $j \rightarrow i$ の流れが等しくなっていることである。
　 $i$ から $l_1$ に流れ出すある1単位の重要度は次のようになる。

$x_{i \rightarrow l_1} = \frac{A_{il_1}}{k_{i}}$

　 $i$ から $l_1$ に流れ込んだ重要度で $l_2$ に流れ出すものは次のようになる。

$x_{i \rightarrow l_1 \rightarrow l_2} = \frac{A_{il_1}}{k_{i}}\frac{A_{l_1l_2}}{k_{l_1}}$

　このように考えると、 $i \rightarrow l_1 \rightarrow l_2 \rightarrow \cdots \rightarrow l_{t-1} \rightarrow j$ と伝っていき、ウェブサイト $j$ に行きつくある1単位の重要度は、等分配が連鎖されている式となる。

$x_{i \rightarrow l_1 \rightarrow l_2 \rightarrow \cdots \rightarrow l_{t-1} \rightarrow j}=\frac{A_{il_1}}{k_{i}}\frac{A_{l_1l_2}}{k_{l_1}} \cdots \frac{A_{l_{t-2}l_{t-1}}}{k_{l_{t-2}}}\frac{A_{l_{t-1}j}}{k_{l_{t-1}}}$

　経路の任意性を考慮して、始点と終点とステップ数のみになるように経路を足し上げよう。

$\begin{align} x_{i \rightarrow j | t} &= \sum _{l_1=1}^{N} \sum _{l_2=1}^{N} \cdots \sum _{l_{t-1}=1}^{N} x_{i \rightarrow l_1 \rightarrow l_2 \rightarrow \cdots \rightarrow l_{t-1} \rightarrow j} \\ &=\sum _{l_1=1}^{N} \sum _{l_2=1}^{N} \cdots \sum _{l_{t-1}=1}^{N} \frac{A_{il_1}}{k_{i}}\frac{A_{l_1l_2}}{k_{l_1}} \cdots \frac{A_{l_{t-2}l_{t-1}}}{k_{l_{t-2}}}\frac{A_{l_{t-1}j}}{k_{l_{t-1}}} \end{align}$
一方で、逆方向の流れについても書いてみよう。

$\begin{align} x_{j \rightarrow i | t} &= \sum _{l_{t-1}=1}^{N} \cdots \sum _{l_2=1}^{N} \sum _{l_1=1}^{N} x_{j \rightarrow l_{t-1} \rightarrow \cdots \rightarrow l_2 \rightarrow l_1 \rightarrow i} \\ &= \sum _{l_{t-1}=1}^{N} \cdots \sum _{l_2=1}^{N} \sum _{l_1=1}^{N} \frac{A_{jl_{t-1}}}{k_{j}}\frac{A_{l_{t-1}l_{t-2}}}{k_{l_{t-1}}} \cdots \frac{A_{l_2l_1}}{k_{l_2}}\frac{A_{l_1i}}{k_{l_1}} \end{align}$

2つの式をよく見比べてみると、順方向と逆方向で単純な関係が成り立っていることが分かるだろう。

$\begin{align} \frac{x_{j \rightarrow i | t}}{k_i} = \frac{x_{i \rightarrow j | t}}{k_j} \end{align}$

ここで、 $t \rightarrow \infty$ として、十分長い時間のもとでの関係を考えると、出発点の依存性は消えてしまう。

$\begin{align} & \frac{x_{i | \infty}}{k_i} = \frac{x_{j | \infty}}{k_j} \\ \leftrightarrow & \frac{x_{i | \infty}}{k_i} = \frac{x_{j | \infty}}{k_j} \\ \leftrightarrow & \frac{x_{i}(\infty)}{k_i} = \frac{x_{j}( \infty)}{k_j} \\ \leftrightarrow & \frac{x_{i}(\infty)}{k_i} = Const. \\ \leftrightarrow & x_{i}(\infty) \sim k_i \end{align}$

いきなり数式が出てきて、驚いたかもしれない。ただ、「ページランクはリンク数に比例する量となる」ということである。

　ちなみに、今回の解き方をもう一度振り返ろう。今回は、ページランクとリンク数が比例の関係にあるということを導くのに最低限の理屈だけを紹介した。数学的にはもっと細かいことを説明したうえで、今回の議論に入らなければならない。たとえば、ページランクがそもそも計算可能であるためには、ページランクが、与えた行列で収束し、一意の解を持つことである。今回の平均場近似も詳細釣り合いも、収束すること、一意の解を持つことを前提で話している。そのため、行列に条件が付いたり、分配が線形の性質を持つ条件を付加しなければならない。

ページランクのまとめ

　この結論見て、思った人いるだろう。ほぼリンク数で決まるなら次数中心性と変わらなくない？ということ。そのとおりである。
　どこかで分析の質問会したとき、「ページランクってほぼ次数に比例した量になりますよね」という私のコメントに対して、「ページランクは優良な被リンクを評価する効果入ってますよ」という返答が帰ってきた。もちろん、そのとおりだが、ページランクでは被リンク獲得の効果は、平均的にはリンクの優良性よりも数が評価されてるという事実がここにある。優良サイトから被リンクを獲得することは、同じ被リンク数のウェブサイト同士のなかでは優位に立てるが、被リンク数をやたらめたら稼いでいるウェブサイトに勝てないのである。

結局、ページランクとはなんだったのか

　ページランクは、まるで持ち上げて落としたかのような紹介になってしまったが、この功績は評価されるべきである。
　ページランクは、複雑ネットワーク上のランダムウォークであり、２次元や３次元で拡散方程式を解いていただけの物理のモデルをネットワーク上の拡散モデルとして拡張したことである。これによって、物性物理においては複雑な格子や結合の間での電子の拡散などがモデル化されたり、社会現象における拡散のモデル化にも利用されている。
　また、単純なランダムウォークでもネットワーク構造が変わると、その再帰性や再帰時間といった統計的性質が変わる面白さもあり、数学的にもかなり深く計算されている。さらに、非線形を持たせることでの局在性や解の分岐などがまさしく私の専門だった。

次回以降書くこと

じゃあ、ページランクモデルを拡張しよう、被リンク数効果以上に優良サイト効果が考慮されるにはこうしよう。というのを次回以降どこかで書いていきたい。

ネットワークとは
ネットワーク中心性
ページランクをどう改善すればいいか
ネットワーク上の線形輸送の収束
ネットワーク上の線形輸送と相関
ネットワーク上の非線形輸送
ネットワーク上の流れのモデル化
番外グラフアルゴリズム

　これ全部書いたら、教科書にでもなりそうだな･･･。むしろいずれ本書きたい。

*1:The Opte projectによるWeb空間の可視化

*2:収束値がどんなときも得られるのかとか収束値を得るためにはどのようにモデル改変すればよいかについては、別に書くつもりだ。

*3:平均場近似は高次元であれば厳密解を与えることができる。我々の存在している１，２，３次元は平均場近似では解くことはできないが、ネットワークのような不思議な次元（高次元であったり、無限次元といわれる空間。ただし、べき指数の議論ははずせない）については、かなり正確な関係を与えてしまうこともある

*4:同じリンク数をもつウェブサイト同士なら、いいウェブサイトからリンクもらっているウェブサイトほどページランクが高い傾向にあるということは確かだ

*5:ランダムウェブサーファという解釈もできる