Class: DataMining::PageRank

Inherits:
Object
  • Object
show all
Defined in:
lib/data_mining/page_rank.rb

Overview

PageRank Algorithm to measure the importance of nodes in a graph

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph, damping_factor = 0.85, iterations = 100) ⇒ PageRank

Measure importance of nodes

Arguments:

graph: (array of arrays, like:
  [[:p1, [:p2]], [:p2, [:p1, :p3]], [:p3, [:p2]]]
damping_factor: (double between 0 and 1)



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/data_mining/page_rank.rb', line 11

def initialize(graph, damping_factor = 0.85, iterations = 100)
  @graph      = graph.to_h
  # { :p1 => [:p2], :p2 => [:p1,:p3], :p3 => [:p2] }
  @outlinks   = Hash.new { |_, key| @graph[key].size }
  # { :p1 => 1, :p2 => 2, :p3 => 1 }
  @inlinks    = Hash.new { |_, key| inlinks(key) }
  # { :p1 => [:p2], :p2 => [:p1,:p3], :p3 => [:p2] }
  @ranks      = Hash.new(1.0 / @graph.size)
  # { :p1 => 1/3, :p2 => 1/3, ... }
  @sinknodes  = @graph.select { |_, v| v.empty? }.keys
  # sinknodes aka dead-ends, have no outlink at all

  @damper     = damping_factor
  @iterations = iterations
end

Instance Attribute Details

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



4
5
6
 
# File 'lib/data_mining/page_rank.rb', line 4

def graph
  @graph
end

#ranks ⇒ Object (readonly)

Returns the value of attribute ranks.



4
5
6
 
# File 'lib/data_mining/page_rank.rb', line 4

def ranks
  @ranks
end

Instance Method Details

#rank! ⇒ Object 



27
28
29
 
# File 'lib/data_mining/page_rank.rb', line 27

def rank!
  pagerank
end