Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 1x 10x 10x 10x 10x 10x 10x 10x 10x 10x 22x 22x 23x 23x 45x 43x 43x 43x 43x 148x 148x 148x 292x 274x 148x 43x 178x 64x 178x 178x 292x 274x 178x 43x 148x 148x 108x 43x 178x 178x 134x 43x 43x 10x | /* eslint-disable no-constant-condition, no-loop-func */
/**
* This plugin computes HITS statistics (Authority and Hub measures) for each node of the graph.
* It adds to the graph model a method called "HITS".
*
* Author: Mehdi El Fadil, Mango Information Systems
* License: This plugin for sigma.js follows the same licensing terms as sigma.js library.
*
* This implementation is based on the original paper J. Kleinberg, Authoritative Sources in a Hyperlinked Environment (http://www.cs.cornell.edu/home/kleinber/auth.pdf), and is inspired by implementation in Gephi software (Patick J. McSweeney <pjmcswee@syr.edu>, Sebastien Heymann <seb@gephi.org>, Dual-licensed under GPL v3 and CDDL)
* https://github.com/Mango-information-systems/gephi/blob/fix-hits/modules/StatisticsPlugin/src/main/java/org/gephi/statistics/plugin/Hits.java
*
* Bugs in Gephi implementation should not be found in this implementation.
* Tests have been put in place based on a test plan used to test implementation in Gephi, cf. discussion here: https://github.com/jacomyal/sigma.js/issues/309
* No guarantee is provided regarding the correctness of the calculations. Plugin author did not control the validity of the test scenarii.
*
* Warning: tricky edge-case. Hubs and authorities for nodes without any edge are only reliable in an undirected graph calculation mode.
*
* Check the code for more information.
*
* Here is how to use it:
*
* > // directed graph
* > var stats = s.graph.HITS()
* > // returns an object indexed by node Id with the authority and hub measures
* > // like { "n0": {"authority": 0.00343, "hub": 0.023975}, "n1": [...]*
*
* > // undirected graph: pass 'true' as function parameter
* > var stats = s.graph.HITS(true)
* > // returns an object indexed by node Id with the authority and hub measures
* > // like { "n0": {"authority": 0.00343, "hub": 0.023975}, "n1": [...]
*/
export default function extend(sigma) {
/**
* This method takes a graph instance and returns authority and hub measures computed for each node. It uses the built-in
* indexes from sigma's graph model to search in the graph.
*
* @param {boolean} isUndirected flag informing whether the graph is directed or not. Default false: directed graph.
* @return {object} object indexed by node Ids, containing authority and hub measures for each node of the graph.
*/
sigma.classes.graph.addMethod("HITS", function HITS(isUndirected) {
let res = {};
const epsilon = 0.0001;
const hubList = [];
const authList = [];
const nodes = this.nodes();
let tempRes = {};
if (!isUndirected) isUndirected = false;
nodes.forEach(node => {
if (isUndirected) {
hubList.push(node);
authList.push(node);
} else {
if (this.degree(node.id, "out") > 0) hubList.push(node);
if (this.degree(node.id, "in") > 0) authList.push(node);
}
res[node.id] = { authority: 1, hub: 1 };
});
let done;
while (true) {
done = true;
let authSum = 0;
let hubSum = 0;
authList.forEach(auth => {
tempRes[auth.id] = { authority: 1, hub: 0 };
const connectedNodes = isUndirected
? this.allNeighborsIndex[auth.id]
: this.inNeighborsIndex[auth.id];
Object.keys(connectedNodes)
.filter(j => j !== auth.id)
.forEach(j => {
tempRes[auth.id].authority += res[j].hub;
});
authSum += tempRes[auth.id].authority;
});
hubList.forEach(hub => {
if (tempRes[hub.id]) tempRes[hub.id].hub = 1;
else tempRes[hub.id] = { authority: 0, hub: 1 };
const connectedNodes = isUndirected
? this.allNeighborsIndex[hub.id]
: this.outNeighborsIndex[hub.id];
Object.keys(connectedNodes)
.filter(j => j !== hub.id)
.forEach(j => {
tempRes[hub.id].hub += res[j].authority;
});
hubSum += tempRes[hub.id].hub;
});
authList.forEach(auth => {
tempRes[auth.id].authority /= authSum;
if (
Math.abs(
(tempRes[auth.id].authority - res[auth.id].authority) /
res[auth.id].authority
) >= epsilon
)
done = false;
});
hubList.forEach(hub => {
tempRes[hub.id].hub /= hubSum;
if (
Math.abs((tempRes[hub.id].hub - res[hub.id].hub) / res[hub.id].hub) >=
epsilon
)
done = false;
});
res = tempRes;
tempRes = {};
if (done) break;
}
return res;
});
}
|