Skip to content

Instantly share code, notes, and snippets.

@BYVoid
Last active October 14, 2016 16:51
Show Gist options
  • Save BYVoid/5458415 to your computer and use it in GitHub Desktop.
Save BYVoid/5458415 to your computer and use it in GitHub Desktop.
Calculate pagerank of every vertex in a graph using Go language
package main
import (
"bufio"
"errors"
"fmt"
"io"
"math"
"os"
"strings"
)
type vertex struct {
inDegree int
outDegree int
pagerank float64
}
type edge struct {
start int
end int
}
var vertexs []vertex
var edges []edge
var vertexID map[string]int = make(map[string]int)
var numVertex int = 0
func lineReader(filename string) (func() (string, error), error) {
f, err := os.Open(filename)
if err != nil {
return nil, err
}
buf := bufio.NewReaderSize(f, 64)
return func() (string, error) {
line, isPrefix, err := buf.ReadLine()
if err != nil {
if err == io.EOF {
if err := f.Close(); err != nil {
return "", err
}
}
return "", err
}
if isPrefix {
return "", errors.New("buffer size to small")
}
return string(line), nil
}, nil
}
func addVertex(vertexName string) int {
var ID int
var ok bool
if ID, ok = vertexID[vertexName]; !ok {
ID = numVertex
vertexID[vertexName] = ID
vertexs = append(vertexs, vertex{})
numVertex++
}
return ID
}
func read() {
readline, err := lineReader("wt2g_inlinks.source")
if err != nil {
panic(err)
}
for {
line, err := readline()
if err != nil {
if err == io.EOF {
break
}
panic(err)
}
// Line format is like "ID1\tID2"
sections := strings.Split(line, "\t")
if len(sections) != 2 {
panic(errors.New("Illegal line format"))
}
start := addVertex(sections[0])
end := addVertex(sections[1])
edges = append(edges, edge{start, end})
}
}
func calcPagerank(alpha float64, numIterations int) {
// Initialize out degree of every vertex
for i := range edges {
edge := &edges[i]
vertexs[edge.start].outDegree++
vertexs[edge.end].inDegree++
}
var I = make([]float64, numVertex)
var S float64
for i := 0; i < numVertex; i++ {
vertexs[i].pagerank = 1 / float64(numVertex)
I[i] = alpha / float64(numVertex)
}
// Calculate pagerank repeatedly until converge (numIterations times)
for k := 0; k < numIterations; k++ {
for i := range edges {
edge := &edges[i]
I[edge.end] += (1 - alpha) * vertexs[edge.start].pagerank / float64(vertexs[edge.start].outDegree)
}
S = 0
for i := 0; i < numVertex; i++ {
if vertexs[i].outDegree == 0 {
S += (1 - alpha) * vertexs[i].pagerank / float64(numVertex)
}
}
for i := 0; i < numVertex; i++ {
vertexs[i].pagerank = I[i] + S
I[i] = alpha / float64(numVertex)
}
}
}
func stat() {
var minPagerank float64 = 1.0
var maxPagerank float64 = 0.0
var minInDegree int = math.MaxInt32
var maxInDegree int = 0
var minOutDegree int = math.MaxInt32
var maxOutDegree int = 0
for i := 0; i < numVertex; i++ {
if vertexs[i].pagerank > maxPagerank {
maxPagerank = vertexs[i].pagerank
}
if vertexs[i].pagerank < minPagerank {
minPagerank = vertexs[i].pagerank
}
if vertexs[i].inDegree > maxInDegree {
maxInDegree = vertexs[i].inDegree
}
if vertexs[i].inDegree < minInDegree {
minInDegree = vertexs[i].inDegree
}
if vertexs[i].outDegree > maxOutDegree {
maxOutDegree = vertexs[i].outDegree
}
if vertexs[i].outDegree < minOutDegree {
minOutDegree = vertexs[i].outDegree
}
}
numRanges := 100
pagerankRangeLen := (maxPagerank - minPagerank) / float64(numRanges)
inDegreeRangeLen := (maxInDegree - minInDegree) / numRanges
outDegreeRangeLen := (maxOutDegree - minOutDegree) / numRanges
var pagerankStat = make([]int, numRanges)
var inDegreeStat = make([]int, numRanges)
var outDegreeStat = make([]int, numRanges)
for i := 0; i < numVertex; i++ {
for j := 0; j < numRanges; j++ {
if vertexs[i].pagerank >= minPagerank+float64(j)*pagerankRangeLen && vertexs[i].pagerank <= minPagerank+float64(j+1)*pagerankRangeLen {
pagerankStat[j]++
break
}
}
for j := 0; j < numRanges; j++ {
if vertexs[i].inDegree >= minInDegree+j*inDegreeRangeLen && vertexs[i].inDegree <= minInDegree+(j+1)*inDegreeRangeLen {
inDegreeStat[j]++
break
}
}
for j := 0; j < numRanges; j++ {
if vertexs[i].outDegree >= minOutDegree+j*outDegreeRangeLen && vertexs[i].outDegree <= minOutDegree+(j+1)*outDegreeRangeLen {
outDegreeStat[j]++
break
}
}
}
fmt.Println(minPagerank, pagerankRangeLen)
//fmt.Println(minInDegree, inDegreeRangeLen)
//fmt.Println(minOutDegree, outDegreeRangeLen)
for i := 0; i < numRanges; i++ {
fmt.Println(i, pagerankStat[i])
//fmt.Println(i, inDegreeStat[i])
//fmt.Println(i, inDegreeStat[i])
}
}
func main() {
read()
calcPagerank(0.15, 30)
stat()
fmt.Println("Done")
}
@dcadenas
Copy link

Maybe you want to give a try to https://github.com/dcadenas/pagerank

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment