Class: PageRank::Sparse

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

Overview

Implementation of PageRank using a sparse matrix representation of the graph

Ruby is not known for its speed, especial for math computations. However, if the number of edges is relatively small in relation to the number of nodes, this pure Ruby implementation should perform well enough for many applications. It uses a sparse matrix representation and thus avoids an order of mangitude of calculations that are not necessary.

If speed is desired, it would be best to implement a NativeSparse class (and optionally NativeDense) 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) ⇒ Sparse

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



20
21
22
23
24
25
26
27
 
# File 'lib/page_rank/sparse.rb', line 20

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

  @graph = {}
  @weight_totals = Hash.new(0.0)
  @weights = {}
  @nodes = Set.new
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) 


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

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

  @graph[dest] ||= Set.new
  @graph[dest] << source
  @weights[source] ||= Hash.new(0.0)
  @weights[source][dest] += weight
  @weight_totals[source] ||= 0.0
  @weight_totals[source] += weight
  @nodes << source
  @nodes << dest
  nil
end