pagerank

README

pagerank

A Monte Carlo implementation of the PageRank algorithm

Documentation

Overview

Package pagerank computes PageRank on up to MaxUInt32 (4,294,967,295) items via graph traversal.

The demonstration that this method is effective in calculating PageRank comes via http://arxiv.org/pdf/1006.2880.pdf

The key insight is that simple graph iteration and counting can approximate PageRank, and can also -- if the graph is stored -- be used to inexpensively recalculate PageRank when edges are added to or removed from the graph.

This package does not ultimately store the entire graph traversal history, and therefore it does not assist with recalculating PageRank when edges are removed from the graph. However, it is designed to make the addition of edges easy and inexpensive, since it stores traversal counts from prior runs. The choice to store traversal counts (rather than the full traversal history) is the reason that edge removal is not facilitated.

Index

• type Base
  • func (b *Base) IsStarter() bool
  • func (b *Base) Traversals() uint64
  • func (b *Base) Traverse()
• type Graph
  • func NewGraph(seed int64, edgesFor func(Node) []Node, nodes *[]Node) *Graph
  • func (g *Graph) Calculate(JumpProbability float32, RoundsPerNode int)
  • func (g *Graph) Pagerank(node Node, normalized bool) (float32, error)
• type Node

Types

type Base

type Base struct {
	// contains filtered or unexported fields
}

func (*Base) IsStarter

func (b *Base) IsStarter() bool

func (*Base) Traversals

func (b *Base) Traversals() uint64

func (*Base) Traverse

func (b *Base) Traverse()

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

func NewGraph

func NewGraph(seed int64, edgesFor func(Node) []Node, nodes *[]Node) *Graph

func (*Graph) Calculate

func (g *Graph) Calculate(JumpProbability float32, RoundsPerNode int)

Calculate runs the Pagerank computation on your graph in-place.

func (*Graph) Pagerank

func (g *Graph) Pagerank(node Node, normalized bool) (float32, error)

type Node

type Node interface {
	IsStarter() bool // Should we start iterations from this node?
	Traverse()
	Traversals() uint64
}