ページランク

ページランク (PageRank) は、ウェブページの重要じゅうよう度どを決定けっていするためのアルゴリズムであり、検索けんさくエンジンのGoogleにおいて、検索けんさく語ごに対たいする適切てきせつな結果けっかを得えるために用もちいられている中心ちゅうしん的てきな技術ぎじゅつ。Googleの創設そうせつ者しゃのうちラリー・ペイジとセルゲイ・ブリンによって1998年ねんに発明はつめいされた。名称めいしょうの由来ゆらいは、ウェブページの"ページ"とラリー・ペイジの姓せいをかけたものである。

PageRankはGoogleの商標しょうひょうであり、またPageRankの処理しょりは特許とっきょが取得しゅとくされている。ただし、特許とっきょはGoogleではなくスタンフォード大学だいがくに帰属きぞくしており、Googleはスタンフォード大学だいがくから同どう特許とっきょの権利けんりを独占どくせん的てきにライセンスされている。なお、同どう大学だいがくは特許とっきょの使用しよう権けんと交換こうかんにGoogleから180万まん株かぶを譲渡ゆずりわたされているが、その株式かぶしきは2005年ねんに3億おく3,600万まんドルで売却ばいきゃくされた。

概要がいよう

発想はっそう

PageRankの動作どうさ概念がいねん図ず

PageRank アルゴリズムの発想はっそうは、引用いんように基もとづく学術がくじゅつ論文ろんぶんの評価ひょうかに似にている。

1. 学術がくじゅつ論文ろんぶんの重要じゅうよう性せいを測はかる指標しひょうとしては、被ひ引用いんよう数すうがよく使つかわれる。重要じゅうような論文ろんぶんはたくさんの人ひとによって引用いんようされるので、被ひ引用いんよう数すうが多おおくなると考かんがえられる。同様どうように、注目ちゅうもくに値あたいする重要じゅうようなウェブページはたくさんのページからリンクされると考かんがえられる。
2. さらに、被ひ引用いんよう数すうを用もちいる考かんがえ方かたに加くわえて、「被ひ引用いんよう数すうの多おおい論文ろんぶんから引用いんようされている論文ろんぶんは、重要じゅうよう度どが高たかい」とする考かんがえ方かたが以前いぜんから存在そんざいした。ウェブページの場合ばあいも同様どうように、重要じゅうようなページからのリンクは価値かちが高たかいと考かんがえられる。
3. ただし、乱発らんぱつされたリンクにはあまり価値かちがないと考かんがえられる。リンク集しゅうのように、とにかくたくさんリンクすることを目的もくてきとしている場合ばあいには、リンク先さきのウェブページに強つよく注目ちゅうもくしているとは言いい難がたい。

この発想はっそうを、数すう億おく～数すう十じゅう億おくページにのぼるウェブページのリンク関係かんけいにも適用てきようしたのが PageRank である（PageRank の登場とうじょうまで、このような大だい規模きぼなリンク関係かんけいに適用てきようするのは難むずかしかった）。

この方法ほうほうを適用てきようすることにより、仲間なかま内ないでリンクし合あっているだけのサイトの重要じゅうよう度どが上あがりにくくなり、リンク集しゅうのような多おおくのリンクを張はっているだけのサイトからのリンクの重要じゅうよう性せいを相対そうたい的てきに減へらす効果こうかがある。

方法ほうほう

以上いじょうを少すこし単純たんじゅん化かして数学すうがく的てきに表あらわすと、次つぎのような方法ほうほうが考かんがえられる。

1. 各かくページは、固有こゆうの得点とくてんを持もっている。
   各かくリンクもまた、固有こゆうの得点とくてんを持もっている。
2. あるページ X に対たいして、
   • X の得点とくてんを P とする。
   • 他たのページから X に対たいして張はられているリンクの得点とくてんをそれぞれ $I_{1},\dotsc ,I_{n}$ とする。
   • X から他たのページに張はられているリンクの得点とくてんをそれぞれ $O_{1},\dotsc ,O_{m}$ とする。
3. このとき、次つぎが成なり立たつものとする。

$I_{1}+\dotsb +I_{n}=P$

$O_{1}=\dotsb =O_{m}={\frac {P}{m}}\left(={\frac {\sum _{i=1}^{n}I_{i}}{m}}\right)$

すなわち、各かくページに「流ながれ込こむ」リンクの得点とくてんの総和そうわと、各かくページから「流ながれ出だす」リンクの得点とくてんの総和そうわが等ひとしくなるようにして、その総和そうわをそのページの得点とくてんと考かんがえるのである。 この得点とくてんが高たかいほど、そのページは重要じゅうようであると考かんがえられる。

全体ぜんたいにわたって矛盾むじゅんが生しょうじないようにうまく得点とくてんを割わり振ふる必要ひつようがあるが、これは一種いっしゅのフローの問題もんだいであり、この問題もんだいの解法かいほうについては様々さまざまな理論りろんが考かんがえ出だされている。

グラフ理論りろん

グラフ理論りろんの言葉ことばを使つかうなら、次つぎのようなことである。

1. WWW上じょうの各かくページをノードと見みなし、リンクをエッジと見みなした有向ゆうこうグラフを考かんがえる。
2. この有向ゆうこうグラフの隣接りんせつ行列ぎょうれつを転置てんちしたものを A =(a_ij) とし、行列ぎょうれつ B = (b_ij) を $b_{ij}=a_{ij}{\bigg /}\textstyle \sum _{k}a_{kj}$ で定義ていぎする。
3. B の最大さいだい固有値こゆうちに属ぞくする固有こゆうベクトルを求もとめる。固有こゆうベクトルの各かく要素ようその値ねが、求もとめるべき各かくページの得点とくてんである。

補足ほそくすると、上うえの定義ていぎにおいて、B は A の各かく要素ようそをその列れつの非ひ零れい要素ようその数かずで割わったものである。 従したがって、B の各かく列れつの和わは 1 になっている。

B は推移すいい確かく率りつ行列ぎょうれつと呼よばれ、あるページからあるページへリンクによってジャンプする確かく率りつを表あらわしているものと考かんがえられる。

別べつの定義ていぎ式しき

Brin & Page (1998)によれば、あるページAのページランクPR(A)は、次つぎの式しきで定義ていぎされる。

$PR\left(A\right)=\left(1-d\right)+d\sum _{i=1}^{n}{\frac {PR\left(T_{i}\right)}{C\left(T_{i}\right)}}$

• $PR\left(T_{n}\right)$：ページAにリンクしているページ$T_{n}$のページランク。仮かりにページAに対たいして3つのページがリンクしているとした場合ばあい、$T_{1}$から$T_{3}$までの各かくページを表あらわす。
• $C\left(T_{n}\right)$：ページ$T_{n}$に含ふくまれる他ほかページ（Aでも$T_{n}$でもないページ）へのリンクの総数そうすう。（注ちゅう：『他たページ』に内部ないぶリンクが含ふくまれるのか否ひかについてはstub）
• d：ダンピング・ファクター。通常つうじょう0.85に設定せっていされるが、作為さくい的てきにページランクを上あげようとする者ものに対たいしては、より小ちいさい値ねに設定せっていされる。（常つねに$0\leq d\leq 1$）

rel="nofollow"

リンクに属性ぞくせい rel="nofollow" を加くわえることで、同どうリンクをページランクの計算けいさん対象たいしょうから除外じょがいすることが可能かのうとなっている。これは、ブログにおけるコメントスパムへの対策たいさくなどを主おも目的もくてきとして、2005年ねんのはじめにGoogleにより提案ていあんされたものである。例たとえばページAからページBにリンクする場合ばあい、ページBのURLを仮かりにhttp://ja.wikipedia.org/とするならば、<a href="http://ja.wikipedia.org/" rel="nofollow"></a>とすることで、ページBがページAから受うけ取とる（便宜べんぎ的てき表現ひょうげん）ページランクは無むとなる。

なお、Wikipediaを含ふくむMediaWikiの外部がいぶリンクにはすべてこの属性ぞくせいを持もたせている。これは、Wikipedia(MediaWiki)が宣伝せんでんの道具どうぐに利用りようされるのを防ふせぐためである。

Buzzurl、del.icio.usといったソーシャルブックマークにおいても、ブックマークスパム対策たいさくとして、この属性ぞくせいが使つかわれる傾向けいこうにある。

参考さんこう文献ぶんけん

• Brin, S.; Page, L. (1998), The Anatomy of a Large-Scale Hypertextual Web Search Engine, http://ilpubs.stanford.edu:8090/361/ 
• Langville, Amy N.; Meyer, Carl D. (2011) [2006]. Google's PageRank and Beyond. Princeton University Press. ISBN 140083032X. https://books.google.com/books?id=KsHTl_2Pfl8C 
  • 邦訳ほうやく Langville, Amy N.、Meyer, Carl D. 著ちょ、岩野いわの和生かずお, 黒川くろかわ利明としあき, 黒川くろかわ洋ひろし 訳やく『Google PageRankの数理すうり』共立きょうりつ出版しゅっぱん、2009年ねん。ISBN 9784320122390。 
• Page, L.; Brin, S.; Motwani, Rajeev; Winograd, Terry (1999), The PageRank Citation Ranking: Bringing Order to the Web, http://ilpubs.stanford.edu:8090/422/ 

関連かんれん項目こうもく

• 検索けんさくエンジン最適さいてき化か - SEO。対象たいしょうページのページランクを上あげるために行おこなわれるサイト構成こうせいなどの最適さいてき化か

外部がいぶリンク

• How Google Finds Your Needle in the Web's Haystack (数学すうがく者しゃによる最もっとも平易へいいかつ信頼しんらい性せいの高たかいページランクの解説かいせつ。英文えいぶん)