Google検索エンジンにみる線型代数の応用

参考サイト

How Google Finds Your Needle in the Web's Haystack

Google 検索エンジンの基本的なアイデアは、

他のページからリンクをされていればいるほど、そのページのランキングが高くなる

というもの。要はリンクを行うことが一種の投票行為となっているのだ。我々はリンクを張ることで、ネット上の人気投票に知らず知らずのうちに参加していることになる。

ただし、一つ一つのリンクが全て同じ価値を与えるのではなくて、ランキングの高いページからのリンクは、より大きな価値を与えると考える。

このような条件を数式的に、定量的に表現する。

j番目のページ $P_j$ はリンクを張っている他のページに対して、自身の価値 $I(P_j)$ を均等に分配すると考える。例えば100のリンクを張っているページは、自身の価値を100等分してリンク先のページへ渡す。

このことを分配される側の $P_i$ から見ると次のようになる：

$I(P_i) = a_{i1} I(P_1) + a_{i2} I(P_2) + \cdots + a_{in} I(P_N)$

ここで $I(P_i)$ はページ $P_i$ のPageRankを表す。 $a_{ij}$ は重みであり、jからiへリンクが貼られているなら $l_j$ をページjの張っているリンク総数として

$\displaystyle{\frac{1}{l_j}}$

であり、jからiへリンクが無いなら０である。（自分自身から自分自身へのリンクは存在しないと考える。自分から自分への投票は出来ない！）

Nは世界に存在するwebページの総数であり、数千億とか、そういうレベルの数である。

このようなランキングの決定方法は、よくよく考えると再帰的である。実際、ページAのランキングを計算するためにはページBのランキングを知らなければならず、そのためにはページAのランキングを知らなければならない！

そこでこのように逐次的に考えるのではなく、巧妙な数学的テクニックを使おう。それは答えが既に分かっていると仮定し、それを文字で表すというものだ。

いま、全てのページのランキングが計算できたと仮定する。そしてこれを $v_1, v_2 , \cdots v_N$ と文字で表す。するとこれらの数は、上の数式に従い、連立方程式
\begin{align}
a_{11} I(P_1) + a_{12} I(P_2) + \cdots + a_{1N} I(P_N) &=P(I_1)\\
a_{21} I(P_1) + a_{22} I(P_2) + \cdots + a_{2N} I(P_N) &= P(I_2)\\
&\cdots\\
a_{N1} I(P_1) + a_{N2} I(P_2) + \cdots + a_{NN} I(P_N) &= P(I_N)
\end{align}