All files / plugins/sigma.statistics.HITS index.ts

100% Statements 49/49
100% Branches 16/16
100% Functions 11/11
100% Lines 44/44

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;
  });
}