graphology-metrics
Advanced tools
Miscellaneous metrics to be used with graphology.
npm install graphology-metrics
Graph metrics
Node metrics
Attributes metrics
Layout quality metrics
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:
Or:
Computes the diameter, i.e the maximum eccentricity of any node of the given graph.
import {diameter} from 'graphology-metrics';
// Alternatively, to load only the relevant code:
import diameter from 'graphology-metrics/diameter';
const graph = new Graph();
graph.addNode('1');
graph.addNode('2');
graph.addNode('3');
graph.addUndirectedEdge(1, 2);
graph.addUndirectedEdge(2, 3);
diameter(graph);
>>> 2
Arguments
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
Computes the modularity, given the graph and a node partition. It works on both directed & undirected networks and will return the relevant modularity.
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 the partition is not given by node attributes
const Q = modularity(graph, {
communities: {1: 0, 2: 0, 3: 1, 4: 1, 5: 1}
});
Arguments
community]: name of the nodes' community attribute in case we need to read them from the graph itself.weight]: name of the edges' weight attribute.γ).true]: whether to compute weighted modularity or not.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
weight]: name of the weight attribute.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 (`betweennessCentrality`):
betweennessCentrality.assign(graph);
// To directly map the result onto a custom attribute:
betweennessCentrality.assign(graph, {attributes: {centrality: 'myCentrality'}});
Arguments
betweennessCentrality]: Name of the centrality attribute to assign.true]: should the result be normalized?false]: should we compute the weighted betweenness centrality?Computes the closeness centrality of a graph's nodes.
import closenessCentrality from 'graphology-metrics/centrality/closeness';
// To compute the eigenvector centrality and return the score per node:
const scores = closenessCentrality(graph);
// To directly map the result to nodes' attributes:
closenessCentrality.assign(graph);
// Note that you can also pass options to customize the algorithm:
const p = closenessCentrality(graph, {wassermanFaust: true});
Arguments
eigenvectorCentrality]: name of the node attribute that will be assigned the eigenvector centrality.false]: whether to use Wasserman & Faust's normalization scheme.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
degreeCentrality]: name of the centrality attribute to assign.Computes the eigenvector centrality of a graph's nodes.
import eigenvectorCentrality from 'graphology-metrics/centrality/eigenvector';
// To compute the eigenvector centrality and return the score per node:
const scores = eigenvectorCentrality(graph);
// To directly map the result to nodes' attributes:
eigenvectorCentrality.assign(graph);
// Note that you can also pass options to customize the algorithm:
const p = eigenvectorCentrality(graph, {tolerance: 1e-3, weighted: false});
Arguments
eigenvectorCentrality]: name of the node attribute that will be assigned the eigenvector centrality.weight]: name of the edges' weight attribute.100]: maximum number of iterations to perform.1.e-6]: convergence error tolerance.false]: whether to use available weights or not.Computes the hub/authority metrics for each node using the HITS algorithm.
import hits from 'graphology-metrics/centrality/hits';
// To compute and return the result as 'hubs' & 'authorities':
const {hubs, authorities} = hits(graph);
// To directly map the result to nodes' attributes:
hits.assign(graph);
// Note that you can also pass options to customize the algorithm:
const {hubs, authorities} = hits(graph, {normalize: false});
Arguments
weight]: name of the edges' weight attribute.hub]: name of the node attribute holding hub information.authority]: name of the node attribute holding authority information.100]: maximum number of iterations to perform.true]: should the result be normalized by the sum of values.1.e-8]: convergence error tolerance.Computes the pagerank metrics for each node.
import pagerank from 'graphology-metrics/centrality/pagerank';
// To compute pagerank and return the score per node:
const scores = pagerank(graph);
// To directly map the result to nodes' attributes:
pagerank.assign(graph);
// Note that you can also pass options to customize the algorithm:
const p = pagerank(graph, {alpha: 0.9, weighted: false});
Arguments
pagerank]: name of the node attribute that will be assigned the pagerank score.weight]: name of the edges' weight attribute.0.85]: damping parameter of the algorithm.100]: maximum number of iterations to perform.1.e-6]: convergence error tolerance.false]: whether to use available weights or not.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:
To compute the weighted degree of every node:
Options
weight]: name of the weight attribute.weightedDegree]: name of the attribute to assign.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
Computes the eccentricity which is the maximum of the shortest paths between the given node and any other node.
import {eccentricity} from 'graphology-metrics';
// Alternatively, to load only the relevant code:
import eccentricity from 'graphology-metrics/eccentricity';
graph.addNode('1');
graph.addNode('2');
graph.addNode('3');
graph.addNode('4');
graph.addUndirectedEdge(1, 2);
graph.addUndirectedEdge(2, 3);
graph.addUndirectedEdge(3, 1);
graph.addUndirectedEdge(3, 4);
eccentricity(graph, 3) >> 1;
Arguments
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
Computes the edge uniformity layout quality metric from the given graph having x and y positions attached to its nodes. Edge uniformity is the normalized standard deviation of edge length of the graph. Lower values should be synonym of better layout according to this particular metric.
Runs in O(E).
import edgeUniformity from 'graphology-metrics/layout-quality/edge-uniformity';
edgeUniformity(graph);
>>> ~1.132
Computes the "neighborhood preservation" layout quality metric from the given graph having x and y positions attached to its nodes. Neighborhood preservation is the average proportion of node neighborhood being the same both in the graph's topology and its 2d layout space. The metric is therefore comprised between 0 and 1, 1 being the best, meaning that every node keeps its neighborhood perfectly intact within the layout space.
Runs in approximately O(N * log(N)).
import neighborhoodPreservation from 'graphology-metrics/layout-quality/neighborhood-preservation';
neighborhoodPreservation(graph);
// >>> 0.456
Computes the "stress" layout quality metric from the given graph having x and y positions attached to its nodes. Stress is the sum of normalized delta between node topology distances and their layout space distances. Lower values should be synonym of better layout according to this particular metric.
Note that this metric does not work very well when the graph has multiple connected components.
Note also that this metric traverses any given graph as an undirected one.
Runs in O(N^2).
import stress from 'graphology-metrics/layout-quality/stress';
stress(graph);
// >>> ~24510.2914
FAQs
Miscellaneous graph metrics for graphology.
The npm package graphology-metrics receives a total of 22,774 weekly downloads. As such, graphology-metrics popularity was classified as popular.
We found that graphology-metrics demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 0 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Research
Security News
Socket’s threat research team has detected six malicious npm packages typosquatting popular libraries to insert SSH backdoors.
Security News
MITRE's 2024 CWE Top 25 highlights critical software vulnerabilities like XSS, SQL Injection, and CSRF, reflecting shifts due to a refined ranking methodology.
Security News
In this segment of the Risky Business podcast, Feross Aboukhadijeh and Patrick Gray discuss the challenges of tracking malware discovered in open source softare.