# ngraph.centrality

2.1.0 • Public • Published

# ngraph.centrality

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:

// 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:

// 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();

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

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
``````

MIT

# todo

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

## Package Sidebar

### Install

`npm i ngraph.centrality`

### Repository

github.com/anvaka/ngraph.centrality

1,297

2.1.0

MIT

20.9 kB

13