更に Ruby で pagepank をやってみた

はじめに

前回の記事を投稿後、Ruby版networkxがあったので、更にやってみた。

問題の整理[再掲]

ノード数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版networkx

require_relative './networkx_graph'
require_relative './networkx_pagerank'

n, m = gets.split.map(&:to_i)
g = NetworkX::Graph.new
m.times do
  a, b = gets.split.map(&:to_i)
  g.add_edge(a - 1, b - 1)
end
v = n.times.map{ rand(0...1.0) }
vs = v.sum
v = n.times.map{ |i| [i, v[i] / vs] }.to_h
puts NetworkX.pagerank(g, v, 0.95)


# output
0.2141053207395146
0.14561400379973355
0.21308767736061818
0.2141053207395146
0.21308767736061818

ぐぬぬ、値が違う。

原因追究

graph.rb

    def add_edge(node_1, node_2, **edge_attrs)
      add_node(node_1)
      add_node(node_2)

      edge_attrs = (@adj[node_1][node_2] || {}).merge(edge_attrs)
      @adj[node_1][node_2] = edge_attrs
      @adj[node_2][node_1] = edge_attrs  # 問題の行
    end

最後の@adj[node_2][node_1] = edge_attrsをコメントアウトしたら、それらしい数値になりました。
恐らく、この行で有向グラフから無向グラフになっていると考えられます。

追記

よくよく見ると

class	グラフ種別
NetworkX::Graph	無向グラフ
NetworkX::DiGraph	有効グラフ
NetworkX::MultiGraph	マルチ無向グラフ
NetworkX::MultiDiGraph	マルチ有向グラフ

とあり、今回はDiGraphを使用するのが正しいです。

修正.rb

require_relative './networkx_graph'
require_relative './networkx_digraph'
require_relative './networkx_pagerank'

n, m = gets.split.map(&:to_i)
g = NetworkX::DiGraph.new      # 有向グラフ
m.times do
  a, b = gets.split.map(&:to_i)
  g.add_edge(a - 1, b - 1)
end
v = n.times.map { |i| [i, 1.0 / n] }.to_h  # 乱数でなくてもよくね
puts NetworkX.pagerank(g, v, 0.95)

また、初期値はどうせ収束するし乱数でなくてもよさそうです。

まとめ

• pegerank に更に詳しくなった