Namazu-devel-ja(旧)


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: About PageRank(TM) (Re: improvements of scoring method)



古川です。

From: Hajime BABA <baba@xxxxxxxxxxxxxxxxxxxxxx>
Subject: [namazu-devel-ja] Re: About PageRank(TM) (Re: improvements of scoring method)
Date: Sat, 17 Feb 2001 18:52:03 +0900

baba> ひとつは lnnmz.pl です。岡野さんと古川さんがお作りになって既に
baba> commitされていたものを、相対リンク対応などのためにざくざく手を入れ

ちなみに、これは現在、 pnamazu には入っていますが、namazu には
入っていません。

で、lnnmz と adnmz なんですが、これらの先頭の use strict; の直
前のブロックは、 namazu では必要ないコードなので、消しておいて
ください。

baba> そうですよね。HITS とかでも A'A や AA' の固有ベクトルがハブやオー
baba> ソリティ計算の基本になってるわけで(動的に計算するという点では 
baba> PageRank とは違いますが)、いろいろ応用も効きそうですし、遊びがいが
baba> あるとおもいます。

ちょっとだけ遊んでみました。

-- 
Rei FURUKAWA 
furukawa@xxxxxxxxxxxx

#!/usr/local/bin/octave

## pagerank で遊ぶ。
## この方法が良い、とかいうつもりは全く無く、
## ただ単に、式をこねくりまわしているに過ぎない。


## このスクリプトでは、M からでなく、A から出発する。
A = [
	0, 1, 1, 1, 1, 0, 1
	1, 0, 0, 0, 0, 0, 0
	1, 1, 0, 0, 0, 0, 0
	0, 1, 1, 0, 1, 0, 0
	1, 0, 1, 1, 0, 1, 0
	1, 0, 0, 0, 1, 0, 0
	0, 0, 0, 0, 1, 0, 0
]

## まず、馬場さんの pagerank.m と同じ計算方法

## A から M に変換する関数を定義
function a2m = a2m (X)
  a2m = ones(columns(X), 1) * (1 ./ max(1,sum(X', 1))) .* X';
endfunction

## M から pagerank を計算する関数を定義
function pagerank = pagerank(X)
  [V,D] = eig(X);
  V = V(:,find(max(abs(diag(D)))));
  pagerank = abs(V / norm(V,1));
  pagerank .*= sign(pagerank(1,1));
endfunction

M = a2m(A)
R = pagerank(M)


## 行き止まりページの扱いについて

## pagerank.html より引用:
##     > web ブラウザの「戻る」機能を用いるしかない。
##     > 人間がブラウジングするだけならばそれで済むが、
##     > PageRank 計算の上ではそれでは済まない。
## それで済ますための処理。
## あるページに n 個のリンクがあるときに、(n + 1) 番目のリンク
## として「戻る (back)」ボタンがあると考える。

## back ボタンの重みは、そこにリンクを張ったページ数で分ける。

## 後付けの理屈としては、
## 「あるページにリンクを張っていることは、
## そのページを発掘する役割を持っている点でエライ」

function a2m_with_back = a2m_with_back(X)
  a2m_with_back = a2m(X + a2m(X')');
endfunction

M = a2m_with_back(A)
R = pagerank(M)


## 相互に連関のない複数の同値類(再帰類)の扱いについて

## pagerank を計算しようとしている人は、これから、検索/ポータルサイト
## を構築しようとしているのである。

## よって、pagerank の対象に、自分 (me) も加え、そこから全ページにリ
## ンクを張っている扱いにすれば、全てのページがリンク (及び back ボ
## タン) にて到達可能になる

function a2m_with_me = a2m_with_me(X)
  a2m_with_me = a2m_with_back([X, zeros(rows(X), 1); ones(1, columns(X)), 0]);
endfunction

M = a2m_with_me(A)
R = pagerank(M)



## 処理を加えれば加えるほど、リンクの意味が薄まっていくだけのような
## 気もする…

## おしまい。