ngraph.centrality

    2.1.0 • Public • Published

    ngraph.centrality build status

    Library computes centrality for entire graph and returns object, where keys are nodes' identifiers and values are centrality values:

    {
      node_1: centrality_value_for_node_1,
      node_2: centrality_value_for_node_2
      // ...
    }

    usage

    Degree centrality

    var centrality = require('ngraph.centrality');
    var g = require('ngraph.graph')();
    
    // Let's build a simple graph:
    g.addLink('fortran', 'c');
    g.addLink('c', 'c++');
    g.addLink('c++', 'perl');
    g.addLink('c', 'javascript');
    
    // this will consider graph as undirected:
    var degreeCentrality = centrality.degree(g);
    
    /*
    degreeCentrality is:
    {
      "fortran": 1,
      "c": 3,
      "c++": 2,
      "perl": 1,
      "javascript": 1
    }
    */
    
    // This will compute in-centrality:
    var inCentrality = centrality.degree(g, 'in');
    /* inCentrality is 
    {
      "fortran": 0,
      "c": 1,
      "c++": 1,
      "perl": 1,
      "javascript": 1
    }
    */
    
    // out-centrality:
    var outCentrality = centrality.degree(g, 'out');
    /* outCentrality is
    {
      "fortran": 1,
      "c": 2,
      "c++": 1,
      "perl": 0,
      "javascript": 0
    }
    */
    
    // You can also pass 'inout' or 'both' to get same results
    // as `degreeCentrality`
    var sameAsDegreeCentrality = centrality.degree(g, 'inout');

    Performance of degree centrality calculation is:

    • inout: O(n), where n is number of nodes
    • in or out: O(n * a), where a is the average number of edges per node

    Betweenness centrality

    var centrality = require('ngraph.centrality');
    var g = require('ngraph.graph')();
    // Let's use the same graph as before:
    g.addLink('fortran', 'c');
    g.addLink('c', 'c++');
    g.addLink('c++', 'perl');
    g.addLink('c', 'javascript');
    
    // this will consider graph as undirected:
    var betweenness = centrality.betweenness(g);
    /* betweenness centrality is:
    
    {
      "fortran": 0,
      "c": 5,
      "c++": 3,
      "perl": 0,
      "javascript": 0
    }
    */
    
    // this will consider graph as directed:
    var directedBetweenness = centrality.betweenness(g, true);
    /* directedBetweenness is:
    {
      "fortran": 0,
      "c": 3,
      "c++": 2,
      "perl": 0,
      "javascript": 0
    }
    */

    Performance of betweenness calculation is O(n * e) time, and O(n + e) space where n is number of nodes and e is number of edges.

    This library implements Brandes's algorithm published in A Faster Algorithm for Betweenness Centrality and further discussed in On Variants of Shortest-Path Betweenness Centrality and their Generic Computation.

    Closeness centrality

    In a connected graph, the normalized closeness centrality of a node is the average length of the shortest path between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

    var centrality = require('ngraph.centrality');
    var g = createGraph();
    g.addLink(1, 2);
    g.addLink(2, 3);
    
    var closeness = centrality.closeness(g);
    
    // closeness is: 
    // { 
    //   '1': 0.6666666666666666,
    //   '2': 1,
    //   '3': 0.6666666666666666
    // }

    Eccentricity centrality

    The eccentricity centrality of a node is the greatest distance between that node and any other node in the network. It can be thought of as how far a node is from the node most distant from it in the graph.

    var centrality = require('ngraph.centrality');
    var g = createGraph();
    g.addLink(1, 2);
    g.addLink(2, 3);
    
    var eccentricity = centrality.eccentricity(g);
    
    // eccentricity is: 
    // { 
    //   '1': 2,
    //   '2': 1,
    //   '3': 2
    // }

    Since the graph's diameter equals maximum eccentricity, we can easily calculate this using the returned object:

    var eccentricityValues = Object.keys(eccentricity).map(function(key) {return eccentricity[key]});
    var diameter = Math.max.apply(null, eccentricityValues);
    // Returns 2

    install

    With npm do:

    npm install ngraph.centrality
    

    license

    MIT

    todo

    It would be nice to have asynchronous version for each centrality calculator.

    Install

    npm i ngraph.centrality

    DownloadsWeekly Downloads

    418

    Version

    2.1.0

    License

    MIT

    Unpacked Size

    20.9 kB

    Total Files

    13

    Last publish

    Collaborators

    • anvaka