co_hits.rb

# -*- coding: utf-8 -*-

#Generalized Co-HITSを計算するスクリプト

#A Generalized Co-HITS Algorithm and Its Application to Bipartite Graphs 
#Hongbo Deng* The Chinese Univ. of Hong Kong; Michael Lyu The Chinese University of Hong Kong; IRWIN KING Chinese University of Hong Kong
#http://portal.acm.org/citation.cfm?id=1557051

#入力は
#u_1 \t v_1 \t count
#u_2 \t v_2 \t count
#な感じ

require 'pp'

class COHITS
  def initialize(filename = "")
    @nodes_u = Hash.new{|h, k|h[k] = []}
    @nodes_v = Hash.new{|h, k|h[k] = []}
    @score_u = Hash.new{ }
    @score_v = Hash.new{ }
    @raw_edge_weight = Hash.new{0}
    @edges = Hash.new{0.0}

    if File.exist?(filename)
      open(filename).each do |l|
        u, v, c = l.chomp.split("\t")
        @nodes_u[u].push v
        @nodes_v[v].push u
        @raw_edge_weight[u=>v] += c.to_i
      end
    end
  end

  def set_edges(u, v, count)
    @nodes_u[u].push v
    @nodes_v[v].push u
    @raw_edge_weight[u=>v] += count
  end

  def set_value
    #各ノードから出る枝の合計数を保持
    sum_count = Hash.new{0.0}

    @nodes_u.each_key{|u| @nodes_u[u].uniq!}
    @nodes_v.each_key{|v| @nodes_v[v].uniq!}

    @raw_edge_weight.each_pair do |key, count|
      u, v = key.to_a[0]
      sum_count[u] += count
      sum_count[v] += count
    end

    @nodes_u.each_pair do |u, ary|
      ary.each do |v|
        if @raw_edge_weight[u=>v] > 0
          @edges[u=>v] = @raw_edge_weight[u=>v] / sum_count[u]
          @edges[v=>u] = @raw_edge_weight[u=>v] / sum_count[v]
        end
      end
    end

    @score_u.default = 1.0 / @nodes_u.size;
    @score_v.default = 1.0 / @nodes_v.size;
  end

  def make_sub_graph(from_u, depth = 3)

    sub_list = []
    u_list = [from_u]
    v_list = []
    watched = []

    1.upto(depth) do |k|
      case k % 2
      when 1
        u_list.each do |u|
          @nodes_u[u].each do |v|
            unless watched.include?(v)
              v_list.push v
              sub_list.push [u, v]
              watched.push v
            end
          end
          watched.push u
        end
        u_list.clear
      when 0
        v_list.each do |v|
          @nodes_v[v].each do |u|
            unless watched.include?(u)
              u_list.push u
              sub_list.push [u, v]
              watched.push u
            end
          end
          watched.push v
        end
        v_list.clear
      end
    end

    sub = COHITS.new()
    sub_list.each do |elem|
      u, v = elem
      sub.set_edges(u, v, @raw_edge_weight[u=>v])
    end
    return sub
  end

  def propagation(lambda_u, lambda_v)
    @nodes_v.each_key do |v|
      @score_v[v] = (1 - lambda_v)*(1.0 / @nodes_v.size) + lambda_v * @nodes_v[v].inject(0.0){|s,u|s +=  @edges[u=>v]*@score_u[u]}
    end

    @nodes_u.each_key do |u|
      @score_u[u] = (1 - lambda_u)*(1.0 / @nodes_u.size) + lambda_u * @nodes_u[u].inject(0.0){|s,v|s +=  @edges[v=>u]*@score_v[v]}
    end
  end

  def calc(n, lambda_u, lambda_v)
    n.times do |i|
      puts "#{i+1}回目のループ"
      propagation(lambda_u, lambda_v)
    end
  end

  def show
    puts "U's score."
    pp @score_u.to_a.sort{|a,b|b[1] <=> a[1]}
    puts "V's score."
    pp @score_v.to_a.sort{|a,b|b[1] <=> a[1]}
  end

  def debug
    pp @nodes_u
    pp @nodes_v
  end
end

a = COHITS.new("./sample.txt")
a.set_value
b = a.make_sub_graph("sll0005",2)
b.set_value
b.calc(10,0.5,0.5)
b.show