Code Monkey home page Code Monkey logo

pagerank's Introduction

pagerank GoDoc GoCover Go Report Card

Weighted PageRank implementation in Go

Usage

package main

import (
	"fmt"

	"github.com/alixaxel/pagerank"
)

func main() {
	graph := pagerank.NewGraph()

	graph.Link(1, 2, 1.0)
	graph.Link(1, 3, 2.0)
	graph.Link(2, 3, 3.0)
	graph.Link(2, 4, 4.0)
	graph.Link(3, 1, 5.0)

	graph.Rank(0.85, 0.000001, func(node uint32, rank float64) {
		fmt.Println("Node", node, "has a rank of", rank)
	})
}

Output

Node 1 has a rank of 0.34983779905464363
Node 2 has a rank of 0.1688733284604475
Node 3 has a rank of 0.3295121849483849
Node 4 has a rank of 0.15177668753652385

Install

go get github.com/alixaxel/pagerank

License

MIT

pagerank's People

Contributors

alixaxel avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

pagerank's Issues

Approach handling 4 billion nodes on modern hardware

The uint can handle values past 4 billion so that means this system can handle graphs with up to 4294967295 nodes in them. Currently, a graph with only 1,000,000 nodes ( with 100,000,000 links) takes 2.6GB of memory to calculate. Approaching 1 billion nodes (with 10 or 100 links each) would take a massive server to calculate.

Is there any way we could split the processing up by sharding the graph into smaller parts rather than processing the whole thing in memory? Perhaps we could even combine the graph.edges and graph.nodes weight values since they contain duplicate weights (or swap them for pointers to a shared float64 value).

Non deterministic result for same input

In example below order of ranks is depends on order of internal map(map of edges).
But for same input i expect deterministic output.
How do i reach this?

package main

import (
	"fmt"

	"github.com/alixaxel/pagerank"
)

const (
	damping   = 0.85
	tolerance = 0.0001
)

type Rank struct {
	idx   int
	score float64
}

func main() {
	g := pagerank.NewGraph()

	g.Link(0, 1, 0.33333)
	g.Link(1, 2, 0.33333)
	g.Link(2, 0, 0.33333)

	var ranks []int
	g.Rank(damping, tolerance, func(sentenceIndex uint32, rank float64) {
		ranks = append(ranks, int(sentenceIndex))
	})

	var ranks2 []int
	g.Rank(damping, tolerance, func(sentenceIndex uint32, rank float64) {
		ranks2 = append(ranks2, int(sentenceIndex))
	})

	fmt.Printf("%v\n", eq(ranks, ranks2)) // ! sometimes false !
}

func eq(l, r []int) bool {
	if len(l) != len(r) {
		return false
	}

	for i := range l {
		if l[i] != r[i] {
			return false
		}
	}

	return true
}

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.