Graphology Cores

Various functions related to k-cores of graphs and to be used with graphology.

The k-core of a graph is the maximal connected subgraph in which all nodes have a degree of k or more. The main core of a graph is the k-core subgraph with the highest possible k.

If the graph is directed, nodes' degree are considered as the sum of all the inbound and outbound neighbors of the node.

An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. https://arxiv.org/abs/cs.DS/0310049

Generalized Cores Vladimir Batagelj and Matjaz Zaversnik, 2002. https://arxiv.org/pdf/cs/0202039

Installation

npm install graphology-cores

Usage

• coreNumber
• kCore
• kShell
• kCrust
• kCorona
• kTruss
• onionLayers

coreNumber

Returns the core number for each node. The core number of a node is the largest k of a k-core subgraph containing this node.

This implementation doesn't allow graphs with parallel edges or self loops.

import coreNumber from 'graphology-cores/coreNumber';

// Return the core number for each node
const numbers = coreNumber(graph);

// Assign to each node its core number
coreNumber.assign(graph);

// Assign with a custom attribute label
coreNumber.assign(graph, 'core');

Arguments

• graph Graph: target graph.
• nodeCoreAttribute ?string : the name of the attribute to use if core numbers are assigned to the nodes.

kCore

Returns the maximal connected subgraph containing nodes with k degree or more. If k isn't provided, k is the highest core number present in the graph.

import kCore from 'graphology-cores/kCore';

// Return the main k-core of the graph
const core = kCore(graph);

// Return the k-core subgraph with an arbitrary k value
const core = kCore(graph, 4);

Arguments

• graph Graph: target graph.
• k ?number: custom k value to use.
• customCore ?object: custom core numbers to use.

kShell

Returns the k-shell subgraph. K-Shell subgraph is the maximal connected subgraph containing the nodes with k degree.

import kShell from 'graphology-cores/kShell';

// Return the main k-shell of the graph
const shell = kShell(graph);

// Return the k-shell subgraph with an arbitrary k value
const shell = kShell(graph, 5);

Arguments

• graph Graph: target graph.
• k ?number: custom k value to use.
• customCore ?object: custom core numbers to use.

kCrust

Returns the k-crust subgraph. K-Crust subgraph is the maximal connected subgraph containing nodes with less than k degree.

import kCrust from 'graphology-cores/kCrust';

// Return the main k-crust of the graph
const crust = kCrust(graph);

// Return the k-crust subgraph with an arbitrary k value
const crust = kCrust(graph, 4);

Arguments

• graph Graph: target graph.
• k ?number: custom k value to use.
• customCore ?object: custom core numbers to use.

kCorona

Returns the k-corona subgraph. K-Corona subgraph contains nodes in the k-core with exactly k neighbors in the k-core.

import kCorona from 'graphology-cores/kCorona';

// Return the main k-corona of the graph
const corona = kCorona(graph);

// Return the k-corona subgraph with an arbitrary k value
const corona = kCorona(graph, 4);

Arguments

• graph Graph: target graph.
• k ?number: custom k value to use.
• customCore ?object: custom core numbers to use.

kTruss

Returns the k-truss subgraph. K-Truss subgraph contains at least three nodes for which every edge is incident to at least k-2 triangles.

K-Truss is not implemented for directed graphs and multigraphs.

import kTruss from 'graphology-cores/kTruss';

// Return the k-truss of the graph with k = 4
const truss = kTruss(graph, 4);

Arguments

• graph Graph: target graph.
• k number: k value to use.

onionLayers

Computes the onion decomposition of a given graph. Onion layers can't be calculated if the graph is directed.

Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition L. Hébert-Dufresne, J. A. Grochow, and A. Allard Scientific Reports 6, 31708 (2016) http://doi.org/10.1038/srep31708

import onionLayers from 'graphology-cores/onionLayers';

// Return the onion layers for each node
const onion = onionLayers(graph);

// Assign to each node its onion layer
onionLayers.assign(graph);

// Assign with a custom attribute label
onionLayers.assign(graph, 'onion');

Arguments

• graph Graph: target graph.
• nodeOnionLayerAttribute ?string : the name of the attribute to use if onion layers are assigned to the nodes.