Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
function createNode() {
return {
score: 1,
incoming: [],
outgoing: [],
total: 0,
};
}
function getIncomingEdge(node, toMatch) {
for (let i = 0; i < node.incoming.length; i += 1) {
const edge = node.incoming[i];
if (edge.source === toMatch) {
return edge;
}
}
return undefined;
}
function getOutgoingEdge(node, toMatch) {
for (let i = 0; i < node.outgoing.length; i += 1) {
const edge = node.outgoing[i];
if (edge.target === toMatch) {
return edge;
}
}
return undefined;
}
function createEdge(source, target) {
const currentEdge = getIncomingEdge(target, source) || getOutgoingEdge(source, target);
if (currentEdge) {
currentEdge.weight += 1;
} else {
const edge = {
source,
target,
weight: 1,
};
target.incoming.push(edge);
source.outgoing.push(edge);
}
}
function computeOutgoingEdges(node) {
return node.outgoing.reduce((acc, edge) => acc + edge.weight, 0);
}
const DAMP = 0.85;
const TOLERANCE = 0.001;
function computeScore(source) {
function computeInternalScore(node, damp) {
if (damp < TOLERANCE) {
return node.score;
}
const total = 1 - DAMP + node.incoming.reduce(
(acc, edge) => acc + computeInternalScore(edge.source, damp * DAMP) * edge.weight / computeOutgoingEdges(edge.source),
node.score,
) * DAMP;
node.total = total;
return total;
}
return computeInternalScore(source, DAMP);
}
const nodes = [
createNode(),
createNode(),
createNode(),
createNode(),
createNode(),
createNode(),
];
const sub = [
createNode(),
createNode(),
createNode(),
createNode(),
createNode(),
];
// Link Node 1 to Node 2
createEdge(nodes[1], nodes[2]);
// Link Node 2 to Node 1
createEdge(nodes[2], nodes[1]);
// Link Node 3 to Node 0 1
createEdge(nodes[3], nodes[0]);
createEdge(nodes[3], nodes[1]);
// Link Node 4 to 1, 3, 5
createEdge(nodes[4], nodes[1]);
createEdge(nodes[4], nodes[3]);
createEdge(nodes[4], nodes[5]);
// Link Node 5 to 1, 4
createEdge(nodes[5], nodes[1]);
createEdge(nodes[5], nodes[4]);
// Link sub ndoes to node 4
sub.forEach((node) => {
createEdge(node, nodes[4]);
});
// Link first 3 sub nodes to node 1
createEdge(sub[0], nodes[1]);
createEdge(sub[1], nodes[1]);
createEdge(sub[2], nodes[1]);
// Compute
for (let i = 0; i < 10; i += 1) {
nodes.forEach((node) => {
computeScore(node);
});
sub.forEach((node) => {
computeScore(node);
});
}
// Output
nodes.forEach((node, id) => {
console.log(`Node #${id}`, computeScore(node));
});
sub.forEach((node, id) => {
console.log(`Sub Node #${id}`, computeScore(node));
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment