PageRank の基本概念

SEO対策研究所

Search Engine Optimization：検索エンジン最適化

BRIGHT IDEAS, NICE DESIGNS.

| HOME | PageRank の基本概念 |
ページランク
Powered by PR-Icon

SEOのプロが使用するテキストリンクサービス http://net-koukoku.biz/
安全で確実なテキストリンクで検索エンジンの上位表示アクセスアップ！

PageRank の基本概念

PageRank は、 「多くの良質なページからリンクされているページは、やはり良質なページである」 という再帰的な関係をもとに、全てのページの重要度を判定したものである。

以下に長々と続く説明では、部分的に専門用語も多く現れるから理解に苦しむ部分があるかも知れない。この章では定性的な解説に絞って平易に解説したつもりであるが、それでもどうしてもわからなかった時は、 「多くの良質なページからリンクされているページは、やはり良質なページである」 というアイデアだけでも理解してもらえればありがたい。いくつかあるポイントの中でも、これが一番重要な考え方だからだ。
さて、Google 自身による紹介ページ Googleの人気の秘密では、以下のような解説がなされている。

PageRankについて

PageRankは、ウェブの膨大なリンク構造を用いて、その特性を生かします。ページＡからページＢへのリンクをページAによるページBへの支持投票とみなし、Googleはこの投票数によりそのページの重要性を判断します。しかしGoogleは単に票数、つまりリンク数を見るだけではなく、票を投じたページについても分析します。「重要度」 の高いページによって投じられた票はより高く評価されて、それを受け取ったページ を「重要なもの」にしていくのです。 こうした分析によって高評価を得た重要なページには高いPageRank（ページ順位）が与えられ、検索結果内の順位も高くなります。PageRankは Googleにおけるページの重要度を示す総合的な指標であり、各検索に影響されるものではありません。むしろ、PageRankは複雑なアルゴリズムにしたがったリンク構造の分析にもとづく、各ウェブページそのものの特性です。 もちろん、重要度が高いページでも検索語句に関連がなければ意味がありません。 そのためにGoogleは洗練されたテキストマッチ技術を使って、検索に対し重要でなおかつ、的確なページを探し出します。

▲　ページトップへ

アルゴリズム

このアルゴリズムを具体的に見ると図のようになる。あるページの PageRank を、そのページに存在する発リンク数で割った数が、それぞれ被リンク先の PageRank に加算されるという関係になっている。

keymap.png

詳しく見てみよう。 PageRank を高くするためのポイントは、大きく分けて３つある。

被リンク数 (単純な意味での人気度の指標)
お勧め度の高いページからのリンクかどうか (裏付けのある人気かどうかの指標)
リンク元ページでのリンク数 (選び抜かれた人気かどうかの指標)

まず基本的に、多くのページからリンクが張られていればお勧め度は高くなる。「(たくさんリンクされるような)人気のあるページは、きっと良いページであるに違いない」ということだ。
被リンク数を人気度の指標の一つと見ることは自然な考え方だろう。リンクを張るという行為は、「このページを見るといい／このページは役に立つ」という推薦行為を行っていることとみなせるからだ。だが、PageRankの考え方はそれだけにはとどまっていないところがミソだ。

すなわち、単に被リンク数の多寡だけではなくお勧め度の高いページからのリンクは高く評価する。また同時に、総リンク数が少ないページからのリンクは高く評価し、総リンク数が多いページからのリンクは低く評価する。言い換えれば「(多くの推薦を集めるような)良いページが推薦するページは、同じく良いページであるに違いない」という判断と、「やたらリンクを乱発するインフレ気味なリンクに比べて、選び抜かれたリンクは良質なリンクであるに違いない」という判断を同時に行っている。 きちんと人手の入った高い水準のページからの厳選されたリンクは明確に重視する一方で、あれもこれもと関連のないところにリンクを張りまくっているだけの単なるブックマーク的ページからのリンクは、「(全然リンクされないよりはまだマシだが)ほとんど価値がない」として軽視するわけである。

したがって、Yahoo! のような PageRankがとても高いサイトからリンクされれば、それだけで PageRank はグンと上がることになるが、逆に、いくら被リンク数ばかりが多くても、無意味なつまらないページからのリンクばかりでは PageRankはいつまで経っても上がらない。 Yahoo! でなくともその分野での権威(あるいは定番)とも言えるページからリンクされていれば良いわけだが、自分達だけで相対リンクしまくっているだけの低価値なページ同士のリンクは、いわば「単なる内輪びいき」として価値のあるものとは見なされにくい仕組みになっているということでもある。世界中のWebページ全体というグローバルな視点から見て、真に価値があるかどうかを判定していることになる。

こうした指標を総合的に分析した結果、最終的な評価の高かったページは検索の時に上位に表示される仕組みになっている。

従来は、ページの重要度としてそのページの被リンク数だけを単純に用いることがあったが、PageRank方式だと機械的に生成されたリンクの影響を受けにくいという利点がある。つまり、PageRankを上げるためには良質なページからリンクされる必要がある。たとえば Yahoo! に登録依頼を出して通ればイッキに上がる。だがそのためには内容の充実に努めなければならない。このように、PageRankを上げるための近道 (あるいは裏道)は基本的に無いことになるのである。 PageRankに限らない(Clever や HITS などでも同じことだ)が、リンク構造を利用したランキングシステムには、従来の単純な SPAM 手法は通用しない。これは大きな利点であり、 Google の使い勝手を良くしている最大の理由になっている。 (最大の理由ではあるが、唯一の理由でないことには注意したい。)

ここで、 PageRank自体はユーザが与えた検索式に与えた語句とは全く無関係な、すでに定まった量であることに注意しよう。後に述べるように、PageRank自体の計算式には検索語句は現れない。どのような検索語句を与えても一定の、文書固有のスコア量である。

PageRankの定性的な説明はこのようなものでだいたい尽きる。だが、実際にランキングを計算して順位を比較するためにはもっと定量的な議論が必要である。次章以下で詳しく説明しよう。

どうやって PageRank を求めるか

我々が興味があるのは、ハイパーリンク構造のような相互参照関係があるときに、どのページがもっとも「重要」であるかを定量的に知りたいということだ。これは「どのページから読み始めるべきか」の指標を厳密に計算する、と大胆に言い換えてみても大きくは違わないだろう。誰も見ないようなマイナーページから読みはじめてもしょうがないからだ。

さて、一般的に言って、Web のようなハイパーリンク構造をランキングに反映させるためには、ハイパーリンク構造を計算機上でモデル化し数値化してやる必要がある。どのようにモデル化するかは実装者の方針によるので一概に言えないが、ハイパーリンク構造をグラフ理論の応用と見た場合、それは線形代数の考え方に帰着されることが多い。 PageRank も同様である。

計算方法の原理

もっとも基本的な考え方として、リンク関係を行列の形で表わしてみよう。あるページ i から別のページ j へリンクが張られている場合にはその成分を 1 とし、そうでない場合を 0 とする。すなわち、行列 A の成分 aij は、

aij = 1 if (ページ i からページ j へのリンクが「ある」場合)
0 if (ページ i からページ j へのリンクが「ない」場合)

で表わされるとしよう。 文書数を N とするとこの行列は N×N のN次正方行列になる。 これは、グラフ理論で「隣接行列」と呼ばれるものに相当する。すなわち、Web のリンク関係を有向グラフ S と見なし、その隣接関係を取ったものである。要するに、リンクが張られていれば隣接関係があるわけである。

現実に適用する際の問題

PageRank の基本的な考え方自体は難しいものではない。実用的な効果が絶大な割には複雑怪奇なアルゴリズムでもなんでもなく、簡単な線形変換を行うだけであり、むしろ簡明で直感的に理解しやすい部類に属するだろう。 だが、実際の Web ハイパーリンク構造を使って PageRank を計算するとなると、さすがに口で言うほどには易しいものではない。その困難は主に二つある。一つには、純粋に仮想的な数値モデルと現実世界との相違に由来するものであり、もう一つは、実際に数値計算する上での(もっぱら技術的な)困難である。

Personalized PageRank の基本的な性質

MHonArc や latex2html あるいは PowerPoint のようなツールを用いて HTML に変型することは良く行われることであるが、このような人工的に作ったHTMLリンク群に対して PageRank を求めると、ほとんどすべてのページのスコアが同じ(～1/N)になる。 隣接行列を考えればほとんど全ての成分が 1 であるか対角成分付近が全て 1 である。このような推移確率行列の固有ベクトルは (1,1,…,1) になるからである。

あるいは、sitemap.html のようにツリー状になっている場合は、 sitemap.html にスコアが集中する。全体の9割を占めることも珍しくない。

これらから言えることは、意味のある PageRank を計算するためには、機械的に生成したリンク関係はできるだけ排除してやる必要があるということである。これはリンク関係を推薦関係と見なせば容易に是認できるだろう。

▲　ページトップへ


Sponsored Link

PageRank に対する個人的見解

PageRank のようなハイパーリンクを利用したランキング手法が有効であることには疑いの余地はないだろう。

ただ、その論文を見ればいろいろ考えることもある。そこで、PageRank に対する個人的な見解をいくつか挙げる。見解と言ってもあくまで方法論に対するものである。間違っていることも多々あることに注意して頂きたい。

dangling page については考えているのに その逆を考慮しないのはなぜか

一定の変異確率を考えることで「たまたま」既約になっているから 考慮していないだけなのか。それとも何か見落としていることがあるのか。 ちょっとわからないでいる。

推移確率行列の改善の可能性

そもそも、PageRank の一意性を保証するためには、 推移確率行列が既約であること(ないしは有向グラフが強連結であること) が保証されればよいのであって、全ての要素 aij を 非零にする必要は別にないはずである。 実際、webブラウジングで トヨタ自動車のサイトを見た直後にポルノサイトに跳び、 続いてホワイトハウスに跳んで２ちゃんねるに跳ぶ、というような ヘンな挙動を示す人はほとんど誰もいないだろう。 (あくまで、時間的に連続した形で、という意味であることに注意)。 従って、実用的な意味でどの程度使い勝手が改善されるかは別として、 アルゴリズム的には改良を加える余地は残されているはずである。

「滞留確率」を考慮してはどうか

PageRank の考え方によれば、一定の時間後には必ずリンクをたどって どっか別のページに飛ぶか、あるいは突然変異的・ワープ的に その他のページに飛ぶかである。 だが現実のwebブラウジングモデルに照らし合わせるなら、 一定の滞留確率も考慮する方が良いのではないか。 具体的に言えば、推移確率行列の対角成分に (1-c)/N しか取らないのは 小さすぎるのではないかということである。 どうせなら、すべて一定の遷移確率よりも重みづけしてはどうか。 つまんないページからはあっという間に別ベージに遷移するはずであるし、 逆に重要なページには長い時間滞留するはずだからだ。

確率論の応用と考えればいろいろ考えられるはず

このような考え方を、実現性は度外視してもう少し進めてみる。 確率論には、 消滅確率・あるいは固定確率と呼ばれるものがある。 PageRank の考え方における単純かつ一様な移転確率よりも、 これらの考え方を導入する方がより望ましい結果を生むことが当然期待される。 マルコフ連鎖には、分枝過程という考え方が知られている。 これは遺伝子の突然変異を考えるときのモデルの一つであり、 すなわち、一定の時間が経てば淘汰を起こす可能性を説明するモデルである。 この考え方は、おそらく取り入れることが可能であろうとおもわれる。 制限付き確率(タブー確率)の考え方を導入してはどうか。 すなわち、状態 i から状態 j へ n 回の推移で移動し、 その間に状態 k には行かないという確率を導入することに相当する。 web ブラウジングの性質を考えれば当然の仮定となり得るのではないか。

非マルコフ過程(ないしは m次の多重マルコフ過程)として考えられないか

マルコフ過程とは、過去の履歴とは関係なく現在の状態のみから 未来の確率法則が決定される確率過程のことである。 マルコフ過程は1ステップ前の過程に依存するだけである。 この過程には過去の記憶はないし、過去の履歴に依存する要素はない。 PageRank は単純マルコフ過程の時間的定常状態で求められるとして 計算されたものである。 だが、すべからく人間の知的行動は非マルコフ過程によって表現される。 複雑な過程は何らかの形で過去を引きずっているものである。 したがって、単にどのページからたどりついたかというだけでなく、 どういう経路をたどってそのページにたどりついたかを分析すれば、 より有用なランキングシステムになる可能性があると考えられる。 計算量の爆発をおさえこめる範囲で、非マルコフ過程の考え方を 取り入れることを検討してみるのもおもしろいかもしれない。
いろいろ考えては見た中には、実装するのはそれほど難しくないものもあるし、言ってみただけでどうやったら実装できるかよくわからないものもあるものの、いずれにしても、その効果を定量的に評価するのは極めて難しい。なんとかできないものだろうか。

PageRank 技術はどれほどのものか

評判の高い PageRank 技術にしても、基本的なアイデアとしては枯れた数値解析的手法を用いるだけで実現されていることがわかるだろう。 だが、私がここで説明したような事柄は、専門の研究者から見ればまったく自明の、毒にも薬にもならない程度のことでしかないのである。規模の点を克服するだけで一つの専門的な研究分野ができるだろう。それくらい、専門分野の奥は深く果てしないと考えた方が良い。 実際、私のやったことは、たかだか「ごくごく小規模な問題であれば、教科書的な手法であってもそこそこの計算量で満足できる結果を得られるようだ」ということを示したに過ぎない。

それにも関わらず、たかだか概要の上っ面を撫でただけで口先だけで「なんだ基本的にはそんな程度の技術か」などと知ったかぶって言う人が一部にいるようだが、そのような浅薄な見方は 根本的にまったく間違っていることをここで改めて強調しておきたい。

むろん、PageRank 手法のすばらしい点は、「多くの良質なページからリンクされているページはやはり良質なページである」という、わかってしまえば簡単なアイデアを出したことにある。だがさらに言えば、本当にすばらしい点は、単に考えついただけでなくて、アイデアを定常状態遷移の確率分布で定式化し、その有効性を実証するために実際にインプリメントし、現実のフィールドでもうまく動作することを実地に証明したことにある。この全ての段階において成功をおさめたことこそが、真に称賛されてしかるべきものなのである。