-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
page-rank.js
142 lines (112 loc) · 3.66 KB
/
page-rank.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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
import { defaults } from '../../util';
import { inPlaceSumNormalize } from '../../math';
const pageRankDefaults = defaults({
dampingFactor: 0.8,
precision: 0.000001,
iterations: 200,
weight: edge => 1
});
let elesfn = ({
pageRank: function( options ){
let { dampingFactor, precision, iterations, weight } = pageRankDefaults(options);
let cy = this._private.cy;
let { nodes, edges } = this.byGroup();
let numNodes = nodes.length;
let numNodesSqd = numNodes * numNodes;
let numEdges = edges.length;
// Construct transposed adjacency matrix
// First lets have a zeroed matrix of the right size
// We'll also keep track of the sum of each column
let matrix = new Array(numNodesSqd);
let columnSum = new Array(numNodes);
let additionalProb = (1 - dampingFactor) / numNodes;
// Create null matrix
for( let i = 0; i < numNodes; i++ ){
for( let j = 0; j < numNodes; j++ ){
let n = i * numNodes + j;
matrix[n] = 0;
}
columnSum[i] = 0;
}
// Now, process edges
for( let i = 0; i < numEdges; i++ ){
let edge = edges[ i ];
let srcId = edge.data('source');
let tgtId = edge.data('target');
// Don't include loops in the matrix
if( srcId === tgtId ){ continue; }
let s = nodes.indexOfId( srcId );
let t = nodes.indexOfId( tgtId );
let w = weight( edge );
let n = t * numNodes + s;
// Update matrix
matrix[n] += w;
// Update column sum
columnSum[s] += w;
}
// Add additional probability based on damping factor
// Also, take into account columns that have sum = 0
let p = 1.0 / numNodes + additionalProb; // Shorthand
// Traverse matrix, column by column
for( let j = 0; j < numNodes; j++ ){
if( columnSum[j] === 0 ){
// No 'links' out from node jth, assume equal probability for each possible node
for( let i = 0; i < numNodes; i++ ){
let n = i * numNodes + j;
matrix[n] = p;
}
} else {
// Node jth has outgoing link, compute normalized probabilities
for( let i = 0; i < numNodes; i++ ){
let n = i * numNodes + j;
matrix[n] = matrix[n] / columnSum[j] + additionalProb;
}
}
}
// Compute dominant eigenvector using power method
let eigenvector = new Array(numNodes);
let temp = new Array(numNodes);
let previous;
// Start with a vector of all 1's
// Also, initialize a null vector which will be used as shorthand
for( let i = 0; i < numNodes; i++ ){
eigenvector[i] = 1;
}
for( let iter = 0; iter < iterations; iter++ ){
// Temp array with all 0's
for( let i = 0; i < numNodes; i++ ){
temp[i] = 0;
}
// Multiply matrix with previous result
for( let i = 0; i < numNodes; i++ ){
for( let j = 0; j < numNodes; j++ ){
let n = i * numNodes + j;
temp[i] += matrix[n] * eigenvector[j];
}
}
inPlaceSumNormalize( temp );
previous = eigenvector;
eigenvector = temp;
temp = previous;
let diff = 0;
// Compute difference (squared module) of both vectors
for( let i = 0; i < numNodes; i++ ){
let delta = previous[i] - eigenvector[i];
diff += delta * delta;
}
// If difference is less than the desired threshold, stop iterating
if( diff < precision ){
break;
}
}
// Construct result
let res = {
rank: function( node ){
node = cy.collection(node)[0];
return eigenvector[ nodes.indexOf(node) ];
}
};
return res;
} // pageRank
}); // elesfn
export default elesfn;