KEIS BLOGは株式会社ケイズ・ソフトウェアが運営しています。

KEIS BLOG

俺googleのページランクのアルゴリズム知ってるんだぜ!

LINEで送る
Pocket

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

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

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

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

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

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

ABC

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

要するに

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 認証 アクセストークン発行まで

LINEで送る
Pocket