-
Notifications
You must be signed in to change notification settings - Fork 5
/
easyToRead.js
116 lines (98 loc) · 3.24 KB
/
easyToRead.js
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/**
* This implementation is slower than the main implementation but it is
* easier to follow. I'm keeping it here for your reference only, even though
* it is not used.
*/
module.exports = pagerank;
function pagerank(graph, internalJumpProbability, epsilon) {
if (typeof epsilon !== 'number') epsilon = 0.005;
if (typeof internalJumpProbability !== 'number') internalJumpProbability = 0.85;
var done = false; // when done is true, the algorithm is converged
var distance = 0; // distance between two eigenvectors in adjacent timesteps
var leakedRank = 0; // we account leaked rank to solve spider traps and dead ends
var nodesCount = graph.getNodesCount();
var nodes = initializeNodes(graph);
var currentRank;
var node;
do {
leakedRank = 0;
for (var j = 0; j < nodesCount; ++j) {
node = nodes[j];
currentRank = 0;
if (node.indegree === 0) {
node.rank = 0;
} else {
var neighbors = node.neighbors;
for (var i = 0; i < neighbors.length; ++i) {
currentRank += neighbors[i].prevRank / neighbors[i].outdegree;
}
node.rank = internalJumpProbability * currentRank;
leakedRank += node.rank;
}
}
// now reinsert the leaked PageRank and compute distance:
leakedRank = (1 - leakedRank) / nodesCount;
distance = 0;
for (j = 0; j < nodesCount; ++j) {
node = nodes[j];
currentRank = node.rank + leakedRank;
distance += Math.abs(currentRank - node.prevRank);
node.prevRank = currentRank; // set up for the next iteration
}
done = distance < epsilon;
} while (!done);
return finalResults(nodes);
}
function finalResults(pageRankNodes) {
var result = Object.create(null);
for (var i = 0; i < pageRankNodes.length; ++i) {
var node = pageRankNodes[i];
result[node.id] = node.prevRank;
}
return result;
}
function initializeNodes(graph) {
var i = 0;
var nodesCount = graph.getNodesCount();
var initialRank = (1 / nodesCount);
var nodes = new Array(nodesCount);
// we want to use integers for faster iteration during computation. This
// means we have to map node identifiers to their integers values
var idToNumber = Object.create(null);
// unfortunately we have to do two-pass to initialize both nodes and edges
graph.forEachNode(addNode);
graph.forEachNode(initLinks);
return nodes;
function addNode(node) {
nodes[i] = new PageRankNode(initialRank, node.id);
idToNumber[node.id] = i;
i += 1;
}
function initLinks(node) {
var pageRankNode = nodes[idToNumber[node.id]];
var inDegree = 0;
var outDegree = 0;
var neighbors = pageRankNode.neighbors;
graph.forEachLinkedNode(node.id, initLink);
pageRankNode.indegree = inDegree;
pageRankNode.outdegree = outDegree;
function initLink(otherNode, link) {
if (link.fromId === node.id) {
outDegree += 1;
}
if (link.toId === node.id) {
inDegree += 1;
// TODO: this needs to be configurable. E.g. use outdegree
neighbors.push(nodes[idToNumber[otherNode.id]]);
}
}
}
}
function PageRankNode(initialRank, id) {
this.id = id;
this.rank = initialRank;
this.prevRank = initialRank;
this.outdegree = 0;
this.indegree = 0;
this.neighbors = [];
}