Class: GraphRank::PageRank

Inherits:
Object
  • Object
show all
Defined in:
lib/graph-rank/page_rank.rb

Overview

Brin, S.; Page, L. (1998). “The anatomy of a large-scale hypertextual Web search engine”. Computer Networks and ISDN Systems 30: 107–117.

Instance Method Summary collapse

Constructor Details

#initialize(damping = nil, convergence = nil, max_it = -1)) ⇒ PageRank

Initialize with default damping and convergence. A maximum number of iterations can also be supplied (default is no maximum, i.e. iterate until convergence).



9
10
11
12
13
14
15
16
17
18
 
# File 'lib/graph-rank/page_rank.rb', line 9

def initialize(damping=nil, convergence=nil, max_it=-1)
  damping ||= 0.85; convergence ||= 0.01
  if damping <= 0 or damping > 1
    raise 'Invalid damping factor.'
  elsif convergence < 0 or convergence > 1
    raise 'Invalid convergence factor.'
  end
  @damping, @convergence, @max_it = damping, convergence, max_it
  @graph, @outlinks, @nodes, @weights = {}, {}, {}, {}
end

Instance Method Details

#add(source, dest, weight = 1.0) ⇒ Object

Add a node to the graph.



21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/graph-rank/page_rank.rb', line 21

def add(source, dest, weight=1.0)
  return false if source == dest
  @outlinks[source] ||= 0.0
  @graph[dest] ||= []
  @graph[dest] << source
  @outlinks[source] += 1.0
  @nodes[source] = 0.15
  @nodes[dest] = 0.15
  @weights[source] ||= {}
  @weights[source][dest] = weight
end

#calculate ⇒ Object

Iterates the PageRank algorithm until convergence is reached.



35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/graph-rank/page_rank.rb', line 35

def calculate
  done = false
  until done
    break if @max_it == 0
    new_nodes = iteration
    done = convergence(new_nodes)
    @nodes = new_nodes
    @max_it -= 1
  end
  @nodes.sort_by {|k,v|v}.reverse
end