New Perspectives and Methods in Link Prediction(KDD 2010) 実装した

New perspectives and methods in link prediction

概要

入力としてグラフ，開始ノード，深さを入力として，からエッジが存在しそうなノード集合を返す．
使い道としては，following関係のグラフデータに使ってあるユーザに他のユーザをレコメンドするとか．

アルゴリズム

アルゴリズムの考え方としては，ノードから始まりノードで終わるステップ以下の制約付きランダムウォークの到達確率を計算し，それをエッジが存在するスコアとする．rooted PageRankに似てるとか大体言わんとしてる事はわかるけどアルゴリズムの説明少なすぎでは．

コード

一旦書いときゃ今度使う時に楽だろうと思って書いた．
karate networkで適当に試したらそれっぽく動いた．
nodeのfilteringみたいな操作は元論文の擬似コードには載ってない．この操作ではスコアの一覧から既にエッジがあるノードを削除するようにしている．
どれぐらいの規模までスケールするかは謎．

# -*- coding: utf-8 -*-
# filename: link_prediction_kdd10.rb
# usage
# ruby link_prediction_kdd10.rb input_file_name start_node depth

class Graph
  def initialize(directed = true)
    @vertexes = [ ]
    @neighbors = Hash.new{|h, k|h[k] = Array.new}
    @weights = Hash.new{0.0}

    @directed = directed
  end

  def read_file(file)
    open(file, "r"){|f|
      f.each do |l|
        # format
        # from \t to \t weight
        v_1, v_2, w = l.chomp.split("\t")
        @vertexes.push v_1
        @vertexes.push v_2
        @neighbors[v_1].push v_2
        @weights[v_1 => v_2] += w.to_f
        
        @neighbors[v_2].push v_1 if !@directed
      end
    }
    @vertexes.uniq!
  end

  def weight(v_1, v_2)
    @directed ? @weights[v_1 => v_2] : [@weights[v_1 => v_2], @weights[v_2 => v_1] ].max
  end

  def prediction(v_s, length)
    found = [ ]; found.push v_s
    new_search = [ ]; new_search.push v_s
    large_s = Hash.new{0.0}; large_s[v_s] = 1
    
    0.upto(length) do |current_degree|
      old_search = Marshal.load(Marshal.dump(new_search))
      new_search.clear
      while !old_search.empty?
        v_i = old_search.pop
        # ここが合ってるか不明
        w_v_s = large_s[v_s]
        sum_output = 0.0
        
        @neighbors[v_i].each do |v_j|
          sum_output += weight(v_i, v_j)
        end
        
        flow = 0.0

        @neighbors[v_i].each do |v_j|
          flow = w_v_s * weight(v_i, v_j) / sum_output
          large_s[v_j] += flow
          if !found.include?(v_j)
            found.push v_j
            new_search.push v_j
          end
        end
      end
    end
    # filtering
    large_s.delete(v_s)
    @neighbors[v_s].each do |v_i|
      large_s.delete(v_i)
    end
    large_s
  end
end

if __FILE__ == $0
  g = Graph.new
  g.read_file(ARGV[0])
  p g.prediction(ARGV[1], ARGV[2].to_i)
end