Skip to content

Commit 912b486

Browse files
author
duaraghav8@gmail
committed
PageRank v2
1 parent 3ca02f9 commit 912b486

File tree

3 files changed

+129
-1
lines changed

3 files changed

+129
-1
lines changed

‎algorithm/graph_search/page_rank/desc.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
"<a href='http://pr.efactory.de/e-pagerank-algorithm.shtml'>E-Factory</a>"
1313
],
1414
"files": {
15-
"basic": "Version #1 of PageRank Algorithm (does not take into account the total number of nodes in the graph, i.e., number of pages on web)."
15+
"basic": "Version #1 of PageRank Algorithm (does not take into account the total number of nodes in the graph, i.e., number of pages on web).",
16+
"v2": "Version #2 divides (1 - D), where D = damping factor, by N, the total no. of documents on internet (nodes in Graph). The resultant Page Ranks form a probability distribution."
1617
}
1718
}

‎algorithm/graph_search/page_rank/v2/code.js‎

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
/*
2+
PageRank Algorithm Version 1
3+
Equation:
4+
PR (X) = (1 - D) + D (Summation i->X (PR (I) / Out (i)))
5+
NOTE: Algorithm uses the recommended damping factor (D). Number of iterations is small because only a small Web of 5 Pages is simulated
6+
*/
7+
8+
function arraySum (array) {
9+
return array.reduce (function (sum, curr) {
10+
return sum + (curr ? 1 : 0); //if curr is 0 (no edge) or undefined (loop not allowed), sum remains unchanged
11+
}, 0);
12+
}
13+
14+
function showOutgoingEdges (i) {
15+
G [i].forEach (function (edgeExists, j) {
16+
edgeExists && graphTracer._visit (j, i)._wait () && graphTracer._leave (j, i)._wait ();
17+
});
18+
}
19+
20+
//PRECOMPUTATIONS
21+
22+
logger._print ('Calculate Outgoing Edge Count for each Node');
23+
(function calculateOEC () {
24+
var count = 0;
25+
G.forEach (function (relations, i) {
26+
outgoingEdgeCounts [i] = arraySum (relations);
27+
showOutgoingEdges (i);
28+
29+
oecTracer._notify (i, outgoingEdgeCounts [i])._wait ();
30+
oecTracer._denotify (i)._wait ();
31+
});
32+
}) ();
33+
34+
logger._print ('determine incoming nodes for each node');
35+
(function determineIN () {
36+
for (var i = 0; i < G.length; i++) {
37+
for (var j = 0; j < G.length; j++) {
38+
if (G [i] [j]) {
39+
//there's an edge FROM i TO j
40+
graphTracer._visit (j, i)._wait ();
41+
42+
var nextPos = incomingNodes [j].indexOf (-1);
43+
incomingNodes [j] [nextPos] = i;
44+
inTracer._notify (j, nextPos, i)._wait ();
45+
inTracer._denotify (j, nextPos)._wait ();
46+
47+
graphTracer._leave (j, i)._wait ();
48+
}
49+
}
50+
}
51+
52+
//logger._print ('All -1s will be removed from incoming node records, they are irrelevant');
53+
incomingNodes.forEach (function (arr) {
54+
arr.splice (arr.indexOf (-1));
55+
});
56+
}) ();
57+
58+
function updateRank (nodeIndex) {
59+
var inNodeSummation = 0, result;
60+
61+
logger._print ('Updating rank of ' + nodeIndex);
62+
logger._print ('The incoming Nodes of ' + nodeIndex + ' are being highlighted');
63+
64+
incomingNodes [nodeIndex].forEach (function (incoming, i) {
65+
inTracer._select (nodeIndex, i)._wait ();
66+
logger._print ('Outgoing edge count of ' + incoming + ' is ' + outgoingEdgeCounts [incoming]);
67+
oecTracer._select (incoming)._wait ();
68+
69+
inNodeSummation += (ranks [incoming] / outgoingEdgeCounts [incoming]);
70+
71+
oecTracer._deselect (incoming)._wait ();
72+
inTracer._deselect (nodeIndex, i)._wait ();
73+
});
74+
logger._print ('In-Node summation of ' + nodeIndex + ' = ' + inNodeSummation);
75+
76+
result = ((1 - damping) / G.length) + (damping * inNodeSummation); //notice the subtle difference between equations of Basic PR & PR version 2 (divide by N)
77+
logger._print ('Therefore, using Equation, new rank of ' + nodeIndex + ' = ' + result);
78+
return result;
79+
}
80+
81+
var damping = 0.85,
82+
iterations = 7;
83+
var initialRank = 1.0;
84+
85+
logger._print ('Initialized all Page ranks to ' + initialRank);
86+
ranks = filledArray (G.length, initialRank);
87+
88+
rankTracer._setData (ranks);
89+
logger._print ('Begin execution of PageRank Version #1');
90+
logger._print ('Equation used: PR (X) = (1 - D) + D (In-Node-Summation i->X (PR (I) / Out (i)))');
91+
logger._print ('D = Damping Factor, PR (X) = Page rank of Node X, i = the ith In-Node of X, Out (i) = outgoing Edge Count of i');
92+
logger._print ('');
93+
94+
while (iterations--) {
95+
for (var node = 0; node < ranks.length; node++) {
96+
ranks [node] = updateRank (node);
97+
rankTracer._notify (node, ranks [node])._wait ();
98+
rankTracer._notify (node)._wait ();
99+
}
100+
}
101+
102+
logger._print ('Page Ranks have been converged to.')
103+
ranks.forEach (function (rank, node) {
104+
logger._print ('Rank of Node #' + node + ' = ' + rank);
105+
});
106+
logger._print ('Done');

‎algorithm/graph_search/page_rank/v2/data.js‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
function filledArray (length, value) {
2+
return Array.apply (null, Array (length)).map (Number.prototype.valueOf, value);
3+
}
4+
5+
var G = new DirectedGraph.random (5, 0.4),
6+
ranks,
7+
outgoingEdgeCounts = filledArray (G.length, 0),
8+
incomingNodes;
9+
10+
var graphTracer = new DirectedGraphTracer ('Web Page inter-connections'),
11+
rankTracer = new Array1DTracer ('Web Page Ranks'),
12+
oecTracer = new Array1DTracer ('Outgoing Edge Counts'),
13+
inTracer = new Array2DTracer ('Incoming Nodes');
14+
15+
var logger = new LogTracer ();
16+
17+
graphTracer._setData (G);
18+
oecTracer._setData (outgoingEdgeCounts);
19+
20+
for (incomingNodes = []; incomingNodes.length < G.length; incomingNodes.push (filledArray (G.length, -1)));
21+
inTracer._setData (incomingNodes);

0 commit comments

Comments
 (0)