僕も Ruby と Python で pagepank をやってみた

はじめに

上記URLにあります、PythonのコードをRubyでやってみようと思います。

result.py

M = np.array([[0, 0, 0, 0, 1],
              [0.5, 0, 0, 0, 0],
              [0.5, 0, 0, 0, 0],
              [0, 1, 0.5, 0, 0],
              [0, 0, 0.5, 1, 0]])
v = pagerank(M, 100, 1)
print(v)

# output
[[0.26658293] 
 [0.13322816] 
 [0.13322816] 
 [0.20009761] 
 [0.26686313]]

ここでは、ダンピング・ファクターを1とします。

問題の整理（AtCoder風）

ノード数Nの有向グラフがある。
高橋くんはノード1からスタートして100回ランダムな遷移を行います。
遷移後、高橋くんがどのノードにいるかを答えてください。

入力
N M
A1 B1
.
.
.
Am Bm

入力例
5 7
1 2
1 3
2 4
3 4
3 5
4 5
5 1

Ruby

n, m = gets.split.map(&:to_i)
ab = Array.new(n){ Array.new(n, 0) }
m.times do
  a, b = gets.split.map(&:to_i)
  ab[a - 1][b - 1] = 1
end
ab.each_with_index do |x, i|
  s = x.sum
  x.each_with_index do |_, j|
    ab[i][j] /= s.to_f
  end
end
m_hat = ab.transpose

v = n.times.map{ rand(0...1.0) }
vs = v.sum
v.map!{ _1 / vs }
100.times do
  vd = v.dup
  n.times do |i|
    v[i] = 0
    n.times do |j|
      v[i] += m_hat[i][j] * vd[j]
    end
  end
end
puts v

# output
0.2662026143788123
0.13329803377108196
0.13329803377108196
0.20040578221512312
0.2667955358639006

ふう、TLEにならなければよいのですが。

[追記] Python

import networkx as nx

N, M = map(int, input().split())
G = nx.DiGraph()
for _ in range(M):
    A, B = map(int, input().split())
    nx.add_path(G, [A, B])

pr = nx.pagerank(G, alpha=0.95, max_iter=100)
print(pr)

# output
{1: 0.26261033194706523, 2: 0.13473925873325307, 3: 0.13473925873325307, 4: 0.20200447126193546, 5: 0.26590667932449313}

いやー、python便利、networkx便利ですね。
ちなみに、ダンピング・ファクターであるalphaは0.95を超えるとエラーになる様です。

まとめ

• pegerankに詳しくなった