forked from aaasen/kapok
-
Notifications
You must be signed in to change notification settings - Fork 0
/
pagerank.go
55 lines (43 loc) · 1.25 KB
/
pagerank.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package graph
const DEFAULT_DAMPING = 0.85
const DEFAULT_ITERATIONS = 15
// PageRank runs a page rank algorithm on the graph n number of times.
// It uses DEFAULT_DAMPING, as the damping factor, which is a reasonable value.
//
// The algorithm is described here:
// http://en.wikipedia.org/wiki/PageRank
//
// and more simply here:
// http://stackoverflow.com/questions/3950627/python-implementation-of-pagerank
func (graph *Graph) PageRank(n int) {
graph.normalizeRanks()
for i := 0; i < n; i++ {
graph.pageRankOnce()
}
}
// Sets all ranks to 1 / (number of nodes).
// This should only be used before running pagerank,
// when the weights mean nothing.
func (graph *Graph) normalizeRanks() {
rank := 1.0
if len(graph.Nodes) > 0 {
rank = 1.0 / float64(len(graph.Nodes))
}
for node := range graph.Nodes {
node.Rank = rank
}
}
func (graph *Graph) pageRankOnce() {
oldRanks := make(map[*Node]float64)
for node := range graph.Nodes {
oldRanks[node] = node.Rank
}
for node := range graph.Nodes {
pointingToNode := graph.PointingTo(node)
sumRanks := 0.0
for _, neighbor := range pointingToNode {
sumRanks += oldRanks[neighbor] / float64(len(graph.Neighbors(neighbor)))
}
node.Rank = (1 - DEFAULT_DAMPING) + DEFAULT_DAMPING*sumRanks
}
}