PageRankの計算 in Ruby DouKaku?

ページランク - Wikipediaを求めるプログラムを作ってください。(PageRankはGoogleの商標です)

詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、簡単に説明すると

ページがn枚ある場合、n×nの2次元配列を用意する。
ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
出力された固有ベクトルから合計が1になるようなPageRankを算出する

という流れになります。

Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので何百行ものコードになってしまった場合はきっとお題の趣旨から外れていると思います。このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、自力で固有値の計算を実装することは求められていません。

data = {
    1: [2, 3, 4, 5, 7],
    2: [1],
    3: [1, 2],
    4: [2, 3, 5],
    5: [1, 3, 4, 6],
    6: [1, 5],
    7: [5],
}

?????

print pagerank
# [0.303514376997, 0.166134185304, 0.140575079872,
#  0.105431309904, 0.178913738019, 0.0447284345048,
#  0.0607028753994]

このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。

rb-gslやnarrayのインストールを試みましたが，
エラーが出て面倒になってきた
(ちなみに使っている環境はCygwin)ので
PageRankを求めるアルゴリズムを自分で
実装しました．

一応行列演算のために標準添付されている
Matrixクラスを使っていますが，
論旨に反してごめんなさい．

require "matrix"
require "pp"

def map_to_mat( map )
  size = map.keys.length
  
  con_mat = Array.new( size ) {
    Array.new( size ) { 0.0 }
  }
  
  map.each {| key, val |
    length = val.length
    
    val.each {| i |
      con_mat[ key - 1 ][ i - 1 ] = 1.0 / length
    }
  }
  
  Matrix[*con_mat]
end

def eigen_values( mat, time = 100 )
  time.times {| i |
    mat *= mat
    
    mat_ary = mat.to_a
    mat_ary.map! {| row |
      sum = row.inject( 0.0 ) {| e, t | e + t }
      row.map! {| val | val / sum }
    }
    mat = Matrix[*mat_ary]
  }
  
  mat.to_a[0]
end

## 以下テスト

data = {
  1 => [2, 3, 4, 5, 7],
  2 => [1],
  3 => [1, 2],
  4 => [2, 3, 5],
  5 => [1, 3, 4, 6],
  6 => [1, 5],
  7 => [5],
}

matrix = map_to_mat( data )
pp matrix.to_a

pp eigen_values( matrix )

存在する確率の初期ベクトルを等確率と置いて
収束させる方法の方が，#2339より効率的で正攻法ですね．

なんで行列をそのまま回そうと思ったんだろう…

ということで直してみました↓

require "matrix"
require "pp"

def map_to_mat( map )
  size = map.keys.length
  
  con_mat = Array.new( size ) {
    Array.new( size ) { 0.0 }
  }
  
  map.each {| key, val |
    length = val.length
    
    val.each {| i |
      con_mat[ key - 1 ][ i - 1 ] = 1.0 / length
    }
  }
  
  Matrix[*con_mat]
end

def eigen_values( mat, time = 100 )
  size = mat.row_size
  vec = Vector[ *Array.new( size ) { 1.0 / size } ].covector
  
  time.times {| i |
    vec = vec * mat
  }
  
  vec.to_a[0]
end

## 以下テスト

data = {
  1 => [2, 3, 4, 5, 7],
  2 => [1],
  3 => [1, 2],
  4 => [2, 3, 5],
  5 => [1, 3, 4, 6],
  6 => [1, 5],
  7 => [5],
}

matrix = map_to_mat( data )
pp matrix.to_a

pp eigen_values( matrix )

Ruby/GSL版(> GSL-1.9)
Cygwin版Rubyで確認．

require 'gsl'

data = {
  1 => [2, 3, 4, 5, 7],
  2 => [1],
  3 => [1, 2],
  4 => [2, 3, 5],
  5 => [1, 3, 4, 6],
  6 => [1, 5],
  7 => [5],
}

mat = GSL::Matrix.zeros(data.size)
data.each do |k, v|
  v.each do |j|
    mat[j-1, k-1] = 1.0 / v.size
  end
end

# 非対称行列の固有値計算はGSL-1.9以上が必要らしい
eigvals, eigvecs = mat.eigen_nonsymmv
eigvec = eigvecs.abs.get_col(eigvals.abs.max_index)

pagerank = (eigvec / eigvec.sum).to_a
puts pagerank

DouKaku?

PageRankの計算

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq