PageRank (ページランク)

  • ページ重要度の自動判定技術
    PageRank は、 「多くの良質なページからリンクされているページは、やはり良質なページである」 
    という再帰的な関係をもとに、全てのページの重要度を判定したものである。
  • ページランクは、WWW検索エンジンの一つであるグーグルが採用している、ウェブページの重要性を測るアルゴリズム。 グーグル社の商標(PageRank™)でもある。
  • グーグル社が提供するGoogle ツールバー は、このアルゴリズムによる各ページの評価点を視覚的に表示することができる。
  • ランクの高いページとは
    • 被リンク数 (単純な意味での人気度の指標)
    • お勧め度の高いページからのリンクかどうか (裏付けのある人気かどうかの指標)
    • リンク元ページでのリンク数 (選び抜かれた人気かどうかの指標)
  • PageRank はユーザが与えた検索語句とは全く無関係なスコア量である。

特許

A computer implemented method of scoring a plurality of linked documents, comprising:, 
互いにリンクされた文書にスコア(得点)を与える計算機に装備された方法(処理内容を
宣言)

obtaining a plurality of documents, at least some of the documents being 
linked documents, at least some of the documents being linking documents, and at least
some of the documents being both linked documents and linking documents, each 
of the linked documents being pointed to by a link in one or more of the  
linking documents; 
人気度を得るために、リンク元およびリンク先文書を集める

assigning a score to each of the linked documents based on scores of the one or 
more linking documents and
リンク元の文書のスコアに基づいて、リンク先文書にスコアを与える(特徴部分)

processing the linked documents according to their scores. 
与えられたスコアを用いてリンク先文書を処理する
  • Googleの特許出願中のPageRankTM 技術
  • 出願文書全訳 :http://kotonoha.main.jp/2005/07/01google-patent.html
    • PageRankTM は、重要度を示す総合的な指標:Googleの説明
      Webの膨大なリンク構造を用いて、その特性を生かします。ページAか
      らページBへのリンクをページAによるページBへの支持投票とみなし、Googleはこの投
      票数によりそのページの重要性を判断します。しかしGoogleは単に票数、つまり
      リンク数を見るだけではなく、票を投じたページについても分析します。
      「重要度」の高い ページによって投じられた票はより高く評価されて
      それを受け取ったページを「重要なもの」にしていくのです。 
      こうした分析によって高評価を得た重要なページには高いPageRankTM (ページ順位)
      が与えられ、検索結果内の順位も高くなります。

googleの若き経営者の研究論文:歴史を回顧する

The year 1998 was a busy year for link analysis models. On the East Coast, a 
young scientist named Jon Kleinberg, an assistant professor in his second year 
at Cornell University, was working on a Web search engine project called HITS. 
His algorithm used the hyperlink structure of the Web to improve search engine 
results, an innovative idea at the time, as most search engines used only 
textual content to return relevant documents. He presented his work [74], 
begun a year earlier at IBM, in January 1998 at the Ninth Annual ACM-SIAM 
Symposium on Discrete Algorithms held in San Francisco, California.
Very nearby, at Stanford University, two Ph.D. candidates were working late 
nights on a similar project called PageRank. Sergey Brin and Larry Page, both 
computer science students, had been collaborating on their Web search engine 
since 1995. By 1998, things were really starting to accelerate for these two
scientists. They were using their dorm rooms as offices for the fledgling 
business, which later became the giant Google. By August 1998, both Brin and 
Page took a leave of absence from Stanford in order to focus on their growing 
business. In a public presentation at the Seventh International World Wide Web
conference (WWW98) in Brisbane, Australia, their paper “The PageRank citation 
ranking: Bringing order to the Web” [27] made small ripples in the 
information science community that quickly turned into waves. The connections 
between the two models are striking (see [78]) and it’s hard to say whether 
HITS influenced PageRank, or vice versa, or whether both developed 
independently. Nevertheless, since that eventful year, PageRank has emerged as 
the dominant link analysis model, partly due to its queryindependence, its 
virtual immunity to spamming and Google’s huge business success. Kleinberg 
was already making a name for himself as an innovative academic, and unlike 
Brin and Page, did not try to develop HITS into a company.
  • Sergey Brinの研究
    • Sergey Brin, Rajeev Motwani, Lawrence Page, and Terry Winograd. What can you do with a Web in your pocket? Data Engineering Bulletin, 21:37–47, 1998.
    • Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 33:107–117, 1998.
    • Sergey Brin, Lawrence Page, R. Motwami, and Terry Winograd. The PageRank citation ranking: bringing order to the Web. Technical Report 1999-0120, Computer Science Department, Stanford University, 1999.
    • Monika Henzinger, Bay-Wei Chang, Brian Milch, and Sergey Brin. Query-free news search. In The Twelfth International World Wide Web Conference, 2003.

 定義

  •  状態推移行列の固有ベクトルの値をもって、PageRank:重要度とする。
  •  行列 A:ページ i から別のページ j へリンクが張られている場合にはその成分を 1 とし、そうでない場合を 0 とする。これを 隣接行列と呼ぶ。
    行列 A の成分 aij は、
    
     aij = 1  if (ページ i からページ j へのリンクが「ある」場合)
           0  if (ページ i からページ j へのリンクが「ない」場合)
  •  次に、行列 A の列和が1となるように各列を修正する。
    • (被リンク数のスコア合計=1)
  •  その行列の転地行列をつくる。これを 基本行列:状態推移行列と呼ぶ。
    •  転置する理由は、PageRank が「どれだけリンクしているか」ではなく「どれだけリンクされているか」を重視するため
  • 基本行列の最大固有値とそれに対応した固有ベクトルを求める。
    • 各ページの重要度:固有ベクトルの値
  • N次正方行列 S に対して Sx = λx を満たす数λをAの固有値といい、x をλに属する固有ベクトルという
  • 別の言い方:グラフ論
    WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。
    このとき、このグラフの隣接行列を転倒したものを A =(aij) とし、行列 B = (bij) を 次によって定義する。
    B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。
    補足すると、上の定義に於いて、B は A の各要素をその列の非零要素の数で割ったものである。 
    従って、B の各列の和は 1 になっている。B は推移確率行列と呼ばれ、あるページからあるページへ
    リンクによってジャンプする確率を表しているものと考えられる

 固有値の求め方

  • 常識 : 最大固有値を求める問題は、下記の最適化問題と同じ
    xt S x ---> 最大化
    制約:xは長さ1 (Σ(xi)2 = 1)
    • 制約付き最適化問題は、繰り返し法で、解ける。
    • 初期値をこれまでの解 x とし、収束させていけるか。
  • 巨大Matrixの固有値問題を厳密に解くには時間がかかる。
    • よくぞ 部分分解して小規模化するにしても 解く気になったのが 素晴らしい
    • これを世界中のWebPage で求めるには、ものすごく力強いcomputerが必要でしょう

Google検索の解説

Counter: 467, today: 1, yesterday: 1

参考 リンク集


トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-08-17 (金) 13:43:00 (2163d)