Class: PageRank::Dense

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

Overview

Implementation of PageRank using matrix multiplication

Ruby is not known for its speed, especial for math computations. As such this implementation is not well suited for large graphs, and it is especially not well suited for graphs that have a small edge-to-vertex ratio. The primary purpose of this implementation is to provide a checkpoint against other implementations to verify their validity.

If speed is desired, it would be best to implement a NativeDense class (and optionally NativeSparse) which would perform the algorithm in C.

Instance Attribute Summary

Attributes inherited from Base

#damping, #tolerance

Instance Method Summary collapse

Methods inherited from Base

#calculate

Constructor Details

#initialize(**options) ⇒ Dense

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

Parameters:

  • damping (Float) —

    The probability of following the graph vs. randomly choosing a new node

  • tolerance (Float) —

    The desired accuracy of the results



22
23
24
25
26
27
28
 
# File 'lib/page_rank/dense.rb', line 22

def initialize(**options)
  super(**options)

  @out_links = []
  @key_to_idx = {}
  @idx_to_key = {}
end

Instance Method Details

#add(source, dest, weight: 1.0) ⇒ nil

Parameters:

  • weight (Float) (defaults to: 1.0) —

    Optional weight for the graph edge

  • _source (Object) —

    The source node

  • _dest (Object) —

    The destination node

Returns:

  • (nil) 


33
34
35
36
37
38
39
40
41
42
 
# File 'lib/page_rank/dense.rb', line 33

def add(source, dest, weight: 1.0)
  return if source == dest

  source_idx = index(source)
  dest_idx = index(dest)
  @out_links[source_idx] ||= []
  @out_links[source_idx][dest_idx] ||= 0.0
  @out_links[source_idx][dest_idx] += weight
  nil
end