こんにちは、最近子供の夜泣きがひどくて夜なかなか眠れない松野です。

夜眠れないので、今は使われてないといわれるgoogleのランクページについていろいろ調べてました。

googleのランクページと呼ばれるものがあることは、ITにかかわる皆さんなら知ってると思いますが
じゃあどんなアルゴリズムなのか、具体的に説明できる人って少ないと思います。

そんな人のために、寝る間も惜しんで（夜泣きで眠れなかったので。。。）アルゴリズムをわかりやすく書きました！

ページランクというのは、google社（正確にはスタンフォード大学）が開発したwebページの重み付けシステムのことです。
ここに、A, B, Cという3つのWEBサイトがあります。（世界中にこの3つのサイトしかないと仮定してください）
それぞれの基本的なページの重みは、最初は1です。

AからはB, Cへリンクが。BからはCへリンクが。CからはAへリンクが張ってあるとします。

基本的には、重み / リンク数 を、それぞれのページに割り当てる　これを繰り返すだけになります。

要するに

Aからは2つのリンクが出ている為、リンクの重みは1つ0.5（Bへ0.5、Cへ0.5ずつ加算）
Bからは1つのリンクが出ている為、リンクの重みは1つ1.0（Cへ1.0加算）
Cからも1つのリンクが出ている為、リンクの重みは1つ1.0（Aへ1.0加算）

まずこの段階で1STEPです。
この重みを計算すると

AはCからのリンク1つで1.0
BはAからのリンク1つで0.5
CはA, Bからのリンクで0.5 + 1.0

つまり、A:1.0, B:0.5, C:1.5になります。

ページランク算出は、これを繰り返します。
A:1.0からは2つのリンクが出ている為、リンクの重みは1つ0.5（Bへ0.5、Cへ0.5ずつ加算）
B:0.5からは1つのリンクが出ている為、リンクの重みは1つ0.5（Cへ0.5加算）
C:1.5からも1つのリンクが出ている為、リンクの重みは1つ1.0（Aへ1.5加算）

AはCからのリンク1つで1.5
BはAからのリンク1つで0.5
CはA, Bからのリンクで0.5 + 0.5

これを繰り返すと、
A:0.4
B:0.2
C:0.4
に収束します（ここからは変化ありません）

この最終的に収束した値が、ページランクの値になります！

これさえ覚えていれば、合コンで　俺googleのアルゴリズム知ってるんだぜフフフン！って知ったかぶりもできちゃうかも！

 

【関連記事】
ハニーポットについて （1）サーバーを立てる
ハニーポットについて （2）アクセスログ有効活用方法
TopCoderをやろう！
TopCoderをやろう 等差数列の問題
今月はTopcoderじゃなくてCodeIQ！
俺googleのページランクのアルゴリズム知ってるんだぜ！
サメの種類と生態
プログラマならできて当たり前、fizzbuzz問題
OAuth1 認証 アクセストークン発行まで