-
Notifications
You must be signed in to change notification settings - Fork 4
/
index.js
134 lines (115 loc) · 3.28 KB
/
index.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
/**
* Computes hubs & authorities rank for a graph.
*
* @see https://en.wikipedia.org/wiki/HITS_algorithm for more details
*/
module.exports = hits;
/**
* @param {ngraph.graph} graph instance to work on.
* @param {number} [epsilon=1e-8] - convergence criteria.
*/
function hits(graph, epsilon) {
if (typeof epsilon !== 'number') epsilon = 1e-8;
var hitsGraph = initialize(graph);
var hitsNodes = hitsGraph.nodes;
var done = true;
do {
var authorityChange = computeAuthorities(hitsNodes);
var hubChange = computeHubs(hitsNodes);
done = authorityChange <= epsilon && hubChange <= epsilon;
} while (!done);
return convertToSourceGraph(graph, hitsGraph);
}
function convertToSourceGraph(originalGraph, hitsGraph) {
var result = Object.create(null);
var nodeIdToIndex = hitsGraph.nodeIdToIndex;
var hitsNodes = hitsGraph.nodes;
originalGraph.forEachNode(addHits);
return result;
function addHits(node) {
var hitsNode = hitsNodes[nodeIdToIndex[node.id]];
result[node.id] = {
authority: hitsNode.authority,
hub: hitsNode.hub
};
}
}
function initialize(graph) {
var hitsNodes = [];
var totalNodes = graph.getNodesCount();
if (totalNodes === 0) {
return {
nodes: [],
nodeIdToIndex: []
}; // degenerate case of empty graph
}
var nodeIdToIndex = Object.create(null);
var idx = 0;
graph.forEachNode(addHitsNode);
graph.forEachLink(addHitsLinks);
return {
nodes: hitsNodes,
nodeIdToIndex: nodeIdToIndex,
};
function addHitsNode(node) {
var hitsNode = new HitsNode(1);
hitsNodes.push(hitsNode);
nodeIdToIndex[node.id] = idx++;
}
function addHitsLinks(link) {
var fromIdx = nodeIdToIndex[link.fromId];
var fromNode = hitsNodes[fromIdx];
var toIdx = nodeIdToIndex[link.toId];
var toNode = hitsNodes[toIdx];
fromNode.outEdges.push(toIdx);
toNode.inEdges.push(fromIdx);
}
}
function computeHubs(nodes) {
var maxHub = -1;
for (var i = 0; i < nodes.length; ++i) {
var node = nodes[i];
var outEdges = node.outEdges;
var hub = 0;
for (var j = 0; j < outEdges.length; ++j) {
hub += nodes[outEdges[j]].authority;
}
if (hub > maxHub) maxHub = hub;
node.prevhub = node.hub;
node.hub = hub;
}
return normalize(nodes, maxHub, 'hub');
}
function computeAuthorities(nodes) {
var maxAuthority = -1;
for (var i = 0; i < nodes.length; ++i) {
var node = nodes[i];
var inEdges = node.inEdges;
var authority = 0;
for (var j = 0; j < inEdges.length; ++j) {
authority += nodes[inEdges[j]].hub;
}
if (authority > maxAuthority) maxAuthority = authority;
node.prevauthority = node.authority;
node.authority = authority;
}
return normalize(nodes, maxAuthority, 'authority');
}
function normalize(nodes, norm, attribute) {
var dx = 0;
var prevAttribute = 'prev' + attribute;
for (var i = 0; i < nodes.length; ++i) {
var node = nodes[i];
node[attribute] /= norm;
dx += Math.abs(node[attribute] - node[prevAttribute]);
}
return dx;
}
function HitsNode(norm) {
// `prev` attribute is used only to compute exit criteria. This probably could
// be done better to save more space.
this.prevauthority = this.authority = norm;
this.prevhub = this.hub = norm;
this.inEdges = [];
this.outEdges = [];
}