ページランク




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


PageRankはGoogleの商標であり、またPageRankの処理は特許が取得されている[3]。ただし、特許はGoogleではなくスタンフォード大学に帰属しており、Googleはスタンフォード大学から同特許の権利を独占的にライセンスされている。なお、同大学は特許の使用権と交換にGoogleから180万株を譲渡されているが、その株式は2005年に3億3,600万ドルで売却された[4][5]。




目次






  • 1 概要


    • 1.1 発想


    • 1.2 方法


    • 1.3 グラフ理論


    • 1.4 別の定義式




  • 2 rel="nofollow"


  • 3 脚注


  • 4 参考文献


  • 5 関連項目


  • 6 外部リンク





概要



発想




PageRankの動作概念図


PageRank アルゴリズムの発想は、引用に基づく学術論文の評価に似ている。



  1. 学術論文の重要性を測る指標としては、被引用数がよく使われる。重要な論文はたくさんの人によって引用されるので、被引用数が多くなると考えられる。同様に、注目に値する重要なウェブページはたくさんのページからリンクされると考えられる。

  2. さらに、被引用数を用いる考え方に加えて、「被引用数の多い論文から引用されている論文は、重要度が高い」とする考え方が以前から存在した。ウェブページの場合も同様に、重要なページからのリンクは価値が高いと考えられる。

  3. ただし、乱発されたリンクにはあまり価値がないと考えられる。リンク集のように、とにかくたくさんリンクすることを目的としている場合には、リンク先のウェブページに強く注目しているとは言い難い。


この発想を、数億～数十億ページにのぼるウェブページのリンク関係にも適用したのが PageRank である（PageRank の登場まで、このような大規模なリンク関係に適用するのは難しかった）。


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



方法


以上を少し単純化して数学的に表すと、次のような方法が考えられる。



  1. 各ページは、固有の得点を持っている。
    各リンクもまた、固有の得点を持っている。

  2. あるページ X に対して、

    • X の得点を P とする。

    • 他のページから X に対して張られているリンクの得点をそれぞれ I1,…,In{displaystyle I_{1},dotsc ,I_{n}}{displaystyle I_{1},dotsc ,I_{n}} とする。

    • X から他のページに張られているリンクの得点をそれぞれ O1,…,Om{displaystyle O_{1},dotsc ,O_{m}}{displaystyle O_{1},dotsc ,O_{m}} とする。



  3. このとき、次が成り立つものとする。



I1+⋯+In=P{displaystyle I_{1}+dotsb +I_{n}=P}{displaystyle I_{1}+dotsb +I_{n}=P}

O1=⋯=Om=Pm(=∑i=1nIim){displaystyle O_{1}=dotsb =O_{m}={frac {P}{m}}left(={frac {sum _{i=1}^{n}I_{i}}{m}}right)}{displaystyle O_{1}=dotsb =O_{m}={frac {P}{m}}left(={frac {sum _{i=1}^{n}I_{i}}{m}}right)}


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


全体にわたって矛盾が生じないようにうまく得点を割り振る必要があるが、これは一種のフローの問題であり、この問題の解法については様々な理論が考え出されている。



グラフ理論


グラフ理論の言葉を使うなら、次のようなことである。



  1. WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。

  2. この有向グラフの隣接行列を転置したものを A =(aij) とし、行列 B = (bij) を bij=aij/∑kakj{displaystyle b_{ij}=a_{ij}{bigg /}textstyle sum _{k}a_{kj}}{displaystyle b_{ij}=a_{ij}{bigg /}textstyle sum _{k}a_{kj}} で定義する。

  3. B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。


補足すると、上の定義において、B は A の各要素をその列の非零要素の数で割ったものである。 従って、B の各列の和は 1 になっている。


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



別の定義式


Brin & Page (1998)によれば、あるページAのページランクPR(A)は、次の式で定義される[6]。


PR(A)=(1−d)+d∑i=1nPR(Ti)C(Ti){displaystyle PRleft(Aright)=left(1-dright)+dsum _{i=1}^{n}{frac {PRleft(T_{i}right)}{Cleft(T_{i}right)}}}PRleft(Aright)=left(1-dright)+dsum _{{i=1}}^{n}{frac {PRleft(T_{i}right)}{Cleft(T_{i}right)}}



  • PR(Tn){displaystyle PRleft(T_{n}right)}PRleft(T_{n}right)：ページAにリンクしているページTn{displaystyle T_{n}}T_{n}のページランク。仮にページAに対して3つのページがリンクしているとした場合、T1{displaystyle T_{1}}T_{1}からT3{displaystyle T_{3}}T_{3}までの各ページを表す。


  • C(Tn){displaystyle Cleft(T_{n}right)}Cleft(T_{n}right)：ページTn{displaystyle T_{n}}T_{n}に含まれる他ページ（AでもTn{displaystyle T_{n}}T_{n}でもないページ）へのリンクの総数。（注：『他ページ』に内部リンクが含まれるのか否かについてはstub）

  • d：ダンピング・ファクター。通常0.85に設定されるが、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。（常に0≤d≤1{displaystyle 0leq dleq 1}{displaystyle 0leq dleq 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といったソーシャルブックマークにおいても、ブックマークスパム対策として、この属性が使われる傾向にある。



脚注


[ヘルプ]




  1. ^ Langville & Meyer 2011, Glossary - PageRank.


  2. ^ Brin & Page 1998.


  3. ^ アメリカ合衆国特許第6,285,999号


  4. ^
    Lisa M. Krieger (2005年12月1日). “Stanford Earns $336 Million Off Google Stock”. San Jose Mercury News, cited by redOrbit. 2009年2月25日閲覧。


  5. ^
    Richard Brandt. “Starting Up. How Google got its groove”. Stanford magazine. 2009年2月25日閲覧。


  6. ^ Brin & Page 1998, 2.2.1 Description of PageRank Calculation.




参考文献




  • 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年。.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
      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 (数学者による最も平易かつ信頼性の高いページランクの解説。英文)




















-

Popular posts from this blog

サソリ

Image
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。 （ 2019年1月 ） 「 サソリ 」のその他の用法については「サソリ (曖昧さ回避)」をご覧ください。 「 スコーピオン 」と「 スコルピオン 」はこの項目へ転送されています。その他の用法については「スコーピオン」をご覧ください。 サソリ目 生息年代: 430–0 Ma PreЄ Є O S D C P T J K Pg N シルル紀前期-現世 ダイオウサソリ（ Pandinus Imperator ） 分類 界 : 動物界 Animalia 門 : 節足動物門 Arthropoda 亜門 : 鋏角亜門 Chelicerata 綱 : クモガタ綱 Arachnida 目 : サソリ目 Scorpiones 学名 Scorpiones C. L. Koch, 1837 英名 Scorpion 上科 Pseudochactoidea キョクトウサソリ上科 Buthoidea Chaeriloidea Chactoidea Iuroidea Scorpionoidea サソリ （ サソリ類 、 蠍 、 蝎 、 scorpion ）は、鋏角亜門・クモガタ綱の サソリ目 （ Scorpiones ）に属する節足動物の総称である。体の前端に鋏型の触肢、後端に毒針を有する捕食者である。 1700種以上を含め、最古の化石記録は4億3千万年前のシルル紀まで遡る。有毒生物として広く知られるが、人間の命にかかわる毒を持つものはごく一部の種類に過ぎない。 目次 1 形態 1.1 前体 1.2 後体 1.2.1 中体 1.2.2 終体 2 雌雄 3 生態 3.1 天敵 3.2 生殖 4 分布 5 毒 6 蛍光現象 7 分類
Read more

広島県道265号伴広島線

Image
一般県道 広島県道265号伴広島線 路線延長 km 起点 広島県広島市安佐南区伴東7丁目 終点 広島県広島市中区榎町 接続する 主な道路 （記法） 広島県道38号広島豊平線 広島県道71号広島湯来線 山陽自動車道五日市IC 国道183号（ 国道261号重複） ■テンプレート（■ノート ■使い方） ■PJ道路 広島県道265号伴広島線 （ひろしまけんどう265ごう ともひろしません）は広島県広島市安佐南区から広島県広島市中区を結ぶ一般県道である。 目次 1 路線データ 2 通過する自治体 3 見どころ 4 接続道路 4.1 本線 4.2 旧道 5 別名 6 関連項目 路線データ 本線 起点：広島市安佐南区伴東7丁目・大原下橋南詰交差点（広島県道38号広島豊平線（本線・旧道）交点） 終点：広島市中区榎町・十日市交差点（国道183号（国道261号重用）交点） 総延長： 旧道 起点：広島市安佐南区伴東4丁目・新細坂交差点（広島県道38号広島豊平線交点） 終点：広島市安佐南区伴中央4丁目・寺組橋(南)交差点（広島県道265号伴広島線（本線）交点） 総延長： 通過する自治体 広島県 広島市（安佐南区、佐伯区、西区、中区） 見どころ 広島高速交通広島新交通1号線（アストラムライン） 広島広域公園 広島広域公園陸上競技場（広島ビッグアーチ） 己斐峠 己斐橋（太田川放水路） 天満橋（天満川） 接続道路 本線 広島県道38号広島豊平線（本線・旧道）（広島市安佐南区伴東7丁目・大原下橋南詰交差点〔起点〕） 広島県道71号広島湯来線（本線）（広島市安佐南区伴中央2丁目・伴交番入口交差点 - 広島市安佐南区伴中央4丁目・寺組橋(南)交差点間で重用） 広島県道71号広島湯来線（旧道）（広島県道265号伴広島線（旧道）重用）（広島市安佐南区伴中央4丁目・寺組橋(南)交差点） 広島県道71号広島湯来線（広島市安佐南区伴中央4丁目・寺組橋(南)交差点 - 広島市佐伯区五日市町石内・五月が丘(南)交差点間で重用）
Read more

Setup Asymptote in Texstudio

Image
0 Good time of the day! I am trying to compile the following file: documentclass[12pt]{article} usepackage[inline]{asymptote} begin{document} Here is a venn diagram produced with Asymptote, drawn to width 4cm: defA{A} defB{V{B}} begin{figure} begin{center} begin{asy} size(4cm,0); pen colour1=red; pen colour2=green; pair z0=(0,0); pair z1=(-1,0); pair z2=(1,0); real r=1.5; path c1=circle(z1,r); path c2=circle(z2,r); fill(c1,colour1); fill(c2,colour2); picture intersection=new picture; fill(intersection,c1,colour1+colour2); clip(intersection,c2); add(intersection); draw(c1); draw(c2); //draw("$A$",box,z1)
Read more