ページランク




ページランク (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

Accessing regular linux commands in Huawei's Dopra Linux

Image
4 Backstory: I have a Huawei HG8245 router in my house and I want to change the default username/password. I've tried following this guide but the config file always gets reset. My ISP isn't helping either so I'm looking for other ways to accomplish this. The router has telnet access so this seems like a way to change the credentials. The first shell I gain access to looks like this: WAP> Pressing "?" gives me a list of available commands which I've pasted here, the two interesting ones are "su" and "shell". I can't seem to get su access, even after logging in as root (challenge password prompt, and then nothing happens), but shell gives me a proper linux shell. WAP>shell BusyBox v1.18.4 (2017-12-26 17:06:34 CST) built-in shell (ash) Enter 'hel...
Read more

Can't connect RFCOMM socket: Host is down

Image
up vote 3 down vote favorite I have bluez 5.4.3 and I am attempting to communicate with a ble device through minicom. These two deceives (my computer and a bluno nano) are alreadt paired and this has been my method so far. #bluetoothctl # pair xx:xx:xx:xx:xx:xx # exit Everything is working well so far then... #sudo rfcomm connect /dev/rfcomm0 xx:xx:xx:xx:xx:xx 1 & [1] 3665 Can't connect RFCOMM socket: Host is down Does anyone know how to resolve this issue? Any help would be very much appreciated. bluetooth bluez share | improve this question asked Feb 9 '17 at 18:46 Brandon Knape 46 2 ...
Read more

Kernel panic - not syncing: Fatal Exception in Interrupt

Image
0 Every day this error occured on my pc, kernel panic error on interrupt, what will be the problem? linux-mint share asked 6 mins ago Vinod Selvin Vinod Selvin 1 1 New contributor Vinod Selvin is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. add a comment ...
Read more