概要

　Google の秘密 - PageRank 徹底解説を参考にして、PageRank を求めるプログラムを書いてみました。プログラムは 2 つに分かれていて、1 つ目は指定されたサイトを総舐めしてリンク構造を取得するためのプログラムで、2 つ目は取得されたリンク構造から各ページの PageRank を求めるプログラムになります。
　外部リンクを考慮しない PageRank の計算では、まず各ページが PageRank 1 を持つ状態から計算を始めます。PageRank はリンク関係を表した隣接行列の固有ベクトルを求めることと同じであり、今回は外部のライブラリなどを利用せずに Perl プログラム単体で動作するようにしました。計算方法にべき乗法を用いたため、計算速度は恐ろしく遅いです。ここのサイト規模では 780 近い内部リンクがあり、64bit デュアルコアの AMD Opteron 1210 プロセッサを搭載したマシンで概ね 30 分程度を要しました。

リンク構造の取得

　Perl を用いて簡単なクローラを作成し、それを用いて対象となるサイト内リンクを全て取得します(ダウンロード)　このプログラムによって、どのページからどのページへリンクが貼られているかを示す隣接行列を得ることができます。別のプログラムを使用して、当サイトの隣接行列を図示したものが次になります。

　上の図からだけでも興味深い点が幾つか見られますので簡単に解説してみます。図の黒い部分がリンクがあるところで、横方向の直線は多くのページからリンクされていることを示しています。反対に縦方向の直線は他のページに多くリンクしていることを示しています。

(A1)記事間の参照

　個別記事アーカイブページの領域で、記事内から別の記事を参照のためにリンクしている場合に密になります。”この記事を読んだ人はこんな記事も読んでいます”機能や、タグの関連度から"その他の関連する記事"を表示する機能によって貼られたリンクも含まれます。自サイト内への記事の言及が活発になると、この領域が密になります。斜めに横断している直線は、link タグの rel="prev" と rel="next" によるものです。また、横に伸びる直線は、左サイドバーにある"ショートカット"や"勝手におすすめ"コーナーのように、全てのページで共通に表示されているリンクによるものとわかります。

(A2)この記事のアーカイブ→キーワード検索

　記事ページの末端にある"この記事のアーカイブ"-"キーワード検索"によるリンクです。

(A3)自動リンクされた記事内のタグ

　このサイトでは記事内にタグを発見すると自動的にリンクを生成するようになっています。その機能によって、個別記事からタグのページにリンクが自動的に生成されています。

(B1)キーワード検索結果

　キーワードの検索結果ページから、そのキーワードを含む個別記事アーカイブページへのリンクが生成されています。

(B2)関連するキーワード

　キーワード検索の結果から、検索結果に含まれるエントリで多く使われているタグを抽出して、関連するキーワードとしてリンクを提示しているためです。

(B3)空白地帯

　自由入力が可能なキーワード検索からタグページへのリンクは難しい、または意味がないと考えたため、キーワードからタグへの移動ルートは用意されていないのがわかります。

(C1)タグ検索結果

　タグが指定された記事の一覧です。タグは手作業によって記事毎に指定されるため、機械的にリンクが生成される(B1)の領域と比べるとリンクが疎になります。

(C2)タグをキーワード検索する

　各タグの検索結果ページには、タグをフリー入力のキーワードとしてキーワード検索するためのリンクがあります。つまり(C3)の領域に居るユーザは、(C2)のリンクを介して(B2)の領域に移動できるということです。

(C3)関連するタグ

　Tagwire プラグインの機能で、現在のタグと関連するタグを求めることができます。タグ検索結果ページには、この機能を利用して、他のタグ検索結果ページに移動できるようになっています。

サイト内に限った PageRank 計算

　先のクローラによって得られたサイト内の隣接行列を用いて、サイト内に限っての PageRank を求めることができます(ダウンロード)　最終的な PageRank は、外部から張られたリンクなどによって決定されますが、それでも現在のサイト内のリンク構造によって、どのページが高い PageRank を持つかを知ることは重要です(このサイトでの計算結果の例)　サイトの内部リンクを幾ら増やしても、サイト全体のページランクの総和は変わりません。サイトの内部リンクについては、ウェブサイト内でリンク関係に基づき、PageRank が再配分されているだけと考えられます。それ故に、もしもサイト管理者があまり重要と考えていないページが高い PageRank を持つ場合には、サイト内のリンク構造を見直す必要があると云えます。

0,/,0.019096,14.818812
1,/archive/,0.019488,15.122910
2,/archive/2004/10031815/,0.000382,0.296662
3,/archive/2004/10042356/,0.000607,0.470673
4,/archive/2004/10050259/,0.000578,0.448212
5,/archive/2004/10051200/,0.000761,0.590912
6,/archive/2004/10060954/,0.000642,0.497883
7,/archive/2004/10062221/,0.000386,0.299185
8,/archive/2004/10072153/,0.000391,0.303397
9,/archive/2004/10082332/,0.000462,0.358354

rel="nofollow" を活用しよう

　リンク属性の一つである rel="nofollow" は、スパムコメントなどによるスパムサイトの宣伝的な PageRank アップを防止するために使用されることが殆どです。しかし、この属性の与えられたリンク先には PageRank が流れないという効果を上手く利用することで、サイト内のページの PageRank をある程度コントロールすることができると考えられます。ページナビゲーション上、どうしてもリンクは必要であるが、そのリンクされたページには特に PageRank を必要としない場合(例えば、全ての記事ページ)などには、リンクに rel="nofollow" と追加することで PageRank の流出を防ぐことができると考えられます。そして、本当に PageRank を必要としているページに対して、適切に PageRank が流れるようにリンクを調整すればよいのです。

参考リンク

• Google の秘密 - PageRank 徹底解説
• ページランクの定義式
• PageRank配分の最適化理論 (1) :: SEM R
• PageRank配分の最適化理論 (2) :: SEM R
• Google's PageRank and how to make the most of it :: SEM R