Rubyでもっとも重要なライブラリは何か？PageRankで計算してみた

最近、PageRankを計算するPHPソースコードを公開している人がいたので、Rubyで書き直してみました。
PHPからRubyへは移植というよりほとんど写経のような感じでそのままポーティングできます。

#!/usr/bin/ruby
# original PHP source http://phpir.com/pagerank-in-php

def calculatePageRank(linkGraph, dampingFactor = 0.15)
    pageRank = Hash.new
    tempRank = Hash.new
    nodeCount = linkGraph.length

    linkGraph.each {|node, outbound|
        pageRank[node] = 1/nodeCount
        tempRank[node] = 0
    }

    change = 1
    i = 0
    while change > 0.00005 && i < 100
        change = 0
        i += 1

        linkGraph.each {|node, outbound|
            outboundCount = outbound.length
            outbound.each {|link|
                tempRank[link] ||= 0
                tempRank[link] += pageRank[node] / outboundCount
            }
        }

        total = 0
        linkGraph.each {|node, outbound|
            tempRank[node] = (dampingFactor / nodeCount) + (1-dampingFactor) * tempRank[node]
            change += (pageRank[node] - tempRank[node]).abs
            pageRank[node] = tempRank[node]
            tempRank[node] = 0
            total += pageRank[node]
        }

        pageRank.each {|node, score|
            pageRank[node] /= total
        }
    end

    return pageRank
end

サンプルプログラム

#!/usr/bin/ruby
require 'pagerank'

links = {
    1 => [5],
    2 => [4, 7, 8],
    3 => [1, 3, 4, 7, 9],
    4 => [1, 2, 4, 8],
    5 => [1, 6, 7, 9],
    6 => [1, 5, 8],
    8 => [3, 4],
    9 => [1, 4, 6, 8]
}

result = calculatePageRank(links).each{|key, value|
    puts "[#{key}] => #{value}"
}

実行結果

>ruby calc.rb
[1] => 0.170847568163539
[2] => 0.0601385970930411
[3] => 0.0952706260288316
[4] => 0.173082449470077
[5] => 0.204222665888343
[6] => 0.0868310142219586
[8] => 0.124761846070846
[9] => 0.0848452330633637

さて、このPageRankプログラムを使ってさっそく何か計算してみましょう。
今回は、Ruby標準ライブラリの依存関係についてPageRankを計算してみることにしました。つまりこういうことです。

沢山のライブラリからrequireされているライブラリは重要
重要なライブラリからrequireされているライブラリは重要

最近のプログラミング言語は標準で山のようにライブラリがついてくるので、それらのソースを読むだけでも一苦労ですね。（いやまあ別に読まなくても良いんですが）
ライブラリの重要度がわかれば、重要なものから順にソースを読んで把握していけば良いはずです。PageRankによるスコアリングがそういったRuby学習者の一助となることは間違いないでしょう。

プログラム

#!/usr/bin/ruby
require 'pagerank'

def makeLibGraph(path)
    graph = Hash.new
    if FileTest.directory?(path)
        Dir.glob("#{path}/**/*.rb").each{|filename|
            File.open(filename, "r") {|file|
                begin
                    require_statements = file.readlines.grep(/^\s*require/)
                rescue
                    require_statements = {}
                end
                if require_statements.count > 0
                    current_lib_name = filename.sub(path + "/", "").sub(".rb", "")
                    graph[current_lib_name] = Array.new
                    require_statements.each {|require_statement|
                        required_lib_name = /require\s+["'](.+)["']/.match(require_statement).to_a[1]
                        graph[current_lib_name] << required_lib_name
                    }
                end
            }
        }
    end

    return graph
end

Encoding.default_external = 'UTF-8'
libGraph = makeLibGraph('C:/ruby/lib/ruby/1.9.1')
result = calculatePageRank(libGraph).sort{|a, b| b[1] <=> a[1] }
result.each {|libname, score|
    puts "#{libname}, #{score}"
}

結果(Ruby1.9)

結果(Ruby1.8)

(´・ω・｀)
えーと、なんというか、ごめんなさい。
実用を考えるならいろいろとチューニングが必要な気がします。