study

ウェブページのランキングの仕組み

ランキングの必要性

現在、WWW には膨大な数のページ数があり、ユーザー の検索ワードを含むページは数万以上であることもある。 その数万というページがユーザーがより役に立つ順序に 並べることが重要である。ランキングを付ける方法にはいくつかある。

ハイパーリンクトリックとは

ハイパーリンクトリックとは、ハイパーリンクの数で ページのスコアをつける方法である。例を挙げると、A と いうページを参照しているリンクが 3 つで、B というペー ジを参照しているリンクが 1 つであるならページ A のス コアが 3、ページ B のスコアが 1 となる。よって、ペー ジ A を高く評価するということである。問題点としては、 ページを非難するためにハイパーリンクを貼ったりしても ページの評価は高くなることである。

オーソリティートリックとは

オーソリティトリックとは、ページを指しているリンク を同じようには扱わない方法である。権威の高いページか らのリンクは、権威の低いページからのリンクよりも高く 評価する。問題点としては、この方法だけでは検索エンジ ンでは役に立たないことである。つまり、権威の高いペー ジと低いページをどのように判断すればよいかという点 である。この問題はハイパーリンクトリックを用いること で解決することができるが、今度は循環参照という問題が 生じる。循環参照があるとページのスコアは無限になって しまうので、正しく評価できないという問題が生じる。図 1 の場合、スタート位置が 1 だとすると次に 3,5,4 と循環 する。

図1 循環参照の例

ランダムサーファートリックとは

これらの問題を解決するためにランダムサーファートリックを提案する。
この方法はハイパーリンクトリックとオーソリティトリックを併用するが、新たな法則が一つ増える。
それがリンクで結ばれたページにいかない確率があるということである。ハイパーリンクとオーソリティトリックを併用するときは、
リンクで結ばれたページにしかいくことができない。これによって無限に循環してしまうのである。
しかし、ある確率でリンクで結ばれていないページへジャンプすることができることによって、
無限に循環するという問題を解決することができる。

実験結果と考察

実験方法としては最初に101から116までのノードを用意する。これらのリンクのつながり方は図2を示す。スタート位置はランダムである。今回はジャンプする確率を15%としている。この試行を1000000回行う。つまりノード101から116までに訪れた回数の合計が1000000回ということである。

図2 今回の利用したノード関係

実験結果としては今回はノード111からのスタートとなった。一番訪れた回数が多いノード110で168102回と一番多かった。これは図2を見てもある程度予想ができる。ノード110へのリンクが6個もあるからである。次に多かったのがノード111であった。ノード111へのリンクは2個である。2番目に多いのがノード108へのリンク4個である。ノード108の訪れた回数は5番目に多いという結果である。このことから必ずしもリンクの数が多いことが、訪れる回数を増やしているとは言えないということである。今回のノード108とノード111の例で大きく影響を受けているのがノード110の存在である。ノード110というのは訪れた回数が1番であるのは先ほど示したが、これはつまり権威が一番大きいということも示している。ノード110のリンク先にノード111があるというのがノード111の訪れた回数を多くしている要因である。また今回の場合、ノード110のリンク先はノード111しかないというのもさらにノード111の訪れる回数増やしている。今回、ジャンプする確率が15%であるので言い換えると、ノード110からノード111へ行った回数はノード110に訪れた回数×0.85倍である。計算してみると、ノード111に訪れた回数は約142887回 である。これだけでもノード108の訪れた回数79224回を上回っている。この結果から、権威のあるノードからリンクしたノードは訪れる回数が多くなるということである。また、権威のあるノードからのリンクしたノードの数が少ないほど訪れる回数は多くなるということである。

図2 それぞれのノードの結果

結論

権威のあるノードからリンクしたノードは訪れる回数が多くなるということからハイパーリンクトリックの問題点を解決している。また、15%の確率でジャンプすることによってオーソリティトリックの問題点である循環参照が生じるという問題を解決している。よって、ランダムサーファートリックはランキングを付ける方法として最適である。