Skip to content
Miscellaneous graph metrics for graphology.
JavaScript
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
centrality
test
.gitignore
.travis.yml
LICENSE.txt
README.md
degree.js
density.js
extent.js
index.js
modality.js
modularity.js
package.json
weighted-degree.js
weighted-size.js

README.md

Build Status

Graphology metrics

Miscellaneous metrics to be used with graphology.

Installation

npm install graphology-metrics

Usage

Graph metrics

Node metrics

Attributes metrics

Density

Computes the density of the given graph.

import {density} from 'graphology-metrics';
import density from 'graphology-metrics/density';

// Passing a graph instance
const d = density(graph);

// Passing the graph's order & size
const d = density(order, size);

// Or to force the kind of density being computed
import {
  mixedDensity,
  directedDensity,
  undirectedDensity,
  multiMixedDensity,
  multiDirectedDensity,
  multiUndirectedDensity
} from 'graphology-metric/density';

const d = undirectedDensity(mixedGraph);

Arguments

Either:

  • graph Graph: target graph.

Or:

  • order number: number of nodes in the graph.
  • size number: number of edges in the graph.

Extent

Computes the extent - min, max - of a node or edge's attribute.

import extent from 'graphology-metrics/extent';

// Retrieving a single node attribute's extent
extent(graph, 'size');
>>> [1, 34]

// Retrieving multiple node attributes' extents
extent(graph, ['x', 'y']);
>>> {x: [-4, 3], y: [-34, 56]}

// For edges
extent.edgeExtent(graph, 'weight');
>>> [0, 5.7]

Arguments

  • graph Graph: target graph.
  • attributes string|array: single attribute names or array of attribute names.

Modularity

Computes the modularity, given the graph and a partitioning

import {modularity} from 'graphology-metrics';
// Alternatively, to load only the relevant code:
import modularity from 'graphology-metrics/modularity';

// Simplest way
const Q = modularity(graph);

// If community mapping is external to the graph
const Q = modularity(graph, {
  communities: {'1': 0, '2': 0, '3': 1, '4': 1, '5': 1}
});

Arguments

  • graph Graph: target graph.
  • options ?object: options:
    • communities ?object: object mapping nodes to their respective communities.
    • attributes ?object: attributes' names:
      • community ?string [community]: name of the nodes' community attribute in case we need to read them from the graph itself.
      • weight ?string [weight]: name of the edges' weight attribute.

Weighted size

Computes the weighted size, i.e. the sum of the graph's edges' weight, of the given graph.

import {weightedSize} from 'graphology-metrics';
// Alternatively, to load only the relevant code:
import weightedSize from 'graphology-metrics/weighted-size';

const graph = new Graph();
graph.mergeEdge(1, 2, {weight: 3});
graph.mergeEdge(1, 2, {weight: 1});

// Simplest way
weightedSize(graph);
>>> 4

// With custom weight attribute
weightedSize(graph, 'myWeightAttribute');
>>> 4

Arguments

  • graph Graph: target graph.
  • weightAttribute ?string [weight]: name of the weight attribute.

Degree

Returns degree information for every node in the graph. Note that graphology's API already gives you access to this information through #.degree etc. So only consider this function as a convenience to extract/assign all degrees at once.

import degree from 'graphology-metrics/degree';

import degree, {
  inDegree,
  outDegree,
  undirectedDegree,
  directedDegree,
  allDegree
} from 'graphology-metrics/degree';

// To extract degree information for every node
const degrees = degree(graph);
>>> {node1: 34, node2: 45, ...}

// To extract only in degree information for every node
const inDegrees = inDegree(graph);

// To extract full degree breakdown for every node
const degrees = allDegree(graph);
>>> { // Assuming the graph is directed
  node1: {
    inDegree: 2,
    outDegree: 36
  },
  ...
}

// To map degree information to node attributes
degree.assign(graph);
graph.getNodeAttribute(node, 'degree');
>>> 45

// To map only degree & in degree to node attributes
allDegree.assign(graph, {types: ['degree', 'inDegree']});

// To map only degree & in degree with different names
allDegree(
  graph,
  {
    attributes: {
      inDegree: 'in',
      outDegree: 'out'
    },
    types: ['inDegree', 'outDegree']
  }
)
>>> {
  1: {in: 1, out: 1},
  ...
}

Arguments

  • graph Graph: target graph.
  • options ?object: options:
    • attributes ?object: Custom attribute names:
      • degree ?string: Name of the mixed degree attribute.
      • inDegree ?string: Name of the mixed inDegree attribute.
      • outDegree ?string: Name of the mixed outDegree attribute.
      • undirectedDegree ?string: Name of the mixed undirectedDegree attribute.
      • directedDegree ?string: Name of the mixed directedDegree attribute.
    • types ?array: List of degree types to extract.

Centrality

Betweenness centrality

Computes the betweenness centrality for every node.

import betweennessCentrality from 'graphology-metrics/centrality/betweenness';

// To compute centrality for every node:
const centrality = betweennessCentrality(graph);

// To compute weighted betweenness centrality
const centrality = betweennessCentrality(graph, {weighted: true});

// To directly map the result onto nodes' attributes (`beetweennessCentrality`):
betweennessCentrality.assign(graph);

// To directly map the result onto a custom attribute:
betweennessCentrality.assign(graph, {attributes: 'myCentrality'});

Arguments

  • graph Graph: target graph.
  • options ?object: options:
    • attributes ?object: Custom attribute names:
      • centrality ?string [betweennessCentrality]: Name of the centrality attribute to assign.
      • weight ?string: Name of the weight attribute.
    • normalized ?boolean [true]: should the result be normalized?
    • weighted ?boolean [false]: should we compute the weighted betweenness centrality?

Degree centrality

Computes the degree centrality for every node.

import degreeCentrality from 'graphology-metrics/centrality/degree';
// Or to load more specific functions:
import {
  degreeCentrality,
  inDegreeCentrality,
  outDegreeCentrality
} from 'graphology-metrics/centrality/degree';

// To compute degree centrality for every node:
const centrality = degreeCentrality(graph);

// To directly map the result onto nodes' attributes (`degreeCentrality`):
degreeCentrality.assign(graph);

// To directly map the result onto a custom attribute:
degreeCentrality.assign(graph, {attributes: {centrality: 'myCentrality'}});

Arguments

  • graph Graph: target graph.
  • options ?object: options:
    • attributes ?object: custom attribute names:
      • centrality ?string [degreeCentrality]: name of the centrality attribute to assign.

Weighted degree

Computes the weighted degree of nodes. The weighted degree of a node is the sum of its edges' weights.

import weightedDegree from 'graphology-metrics/weighted-degree';
// Or to load more specific functions:
import {
  weightedDegree,
  weightedInDegree,
  weightedOutDegree
} from 'graphology-metrics/weighted-degree';

// To compute weighted degree of a single node
weightedDegree(graph, 'A');

// To compute weighted degree of every node
const weightedDegrees = weightedDegree(graph);

// To compute normalized weighted degree, i.e. weighted degree will be
// divided by the node's relevant degree
weightedDegree(graph, 'A', {normalized: true});

// To directly map the result onto node attributes
weightedDegree.assign(graph);

Arguments

To compute the weighted degree of a single node:

  • graph Graph: target graph.
  • node any: desired node.
  • options ?object: options. See below.

To compute the weighted degree of every node:

  • graph Graph: target graph.
  • options ?object: options. See below.

Options

  • attributes ?object: custom attribute names:
    • weight ?string [weight]: name of the weight attribute.
    • weightedDegree ?string [weightedDegree]: name of the attribute to assign.

Modalities

Method returning a node categorical attribute's modalities and related statistics.

import modalities from 'graphology-metrics/modalities';

// Retrieving the 'type' attribute's modalities
const info = modalities(graph, 'type');
>>> {
  value1: {
    nodes: 34,
    internalEdges: 277,
    internalDensity: 0.03,
    externalEdges: 45,
    externalDensity: 0.05,
    inboundEdges: 67,
    inboundDensity: 0.07,
    outboundEdges: 124,
    outboundDensity: 0.003
  },
  ...
}

// Retrieving modalities info for several attributes at once
const info = modalities(graph, ['type', 'lang']);
>>> {
  type: {...},
  lang: {...}
}

Arguments

  • graph Graph: target graph.
  • attribute string|array: target categorical attribute or array of categorical attributes.
You can’t perform that action at this time.