Class CoreDecomposition

Inheritance Relationships

Base Type

Class Documentation

class CoreDecomposition : public NetworKit::Centrality

Computes k-core decomposition of a graph.

Public Functions

CoreDecomposition(const Graph &G, bool normalized = false, bool enforceBucketQueueAlgorithm = false, bool storeNodeOrder = false)

Create CoreDecomposition class for graph G. The graph may not contain self-loops.

Contains the parallel algorithm by Dasari, N.S.; Desh, R.; Zubair, M., “ParK: An efficient algorithm for k-core decomposition on

multicore processors,” in Big Data (Big Data), * 2014 IEEE International Conference.

TODO complexity?

The algorithm runs in parallel if the usage of a bucket priority queue is not enforced and if the node ids of the input graph are continuous (i.e., numberOfNodes() = upperNodeIdBound()).

  • G – The graph.

  • normalized – If set to true the scores are normalized in the interval [0,1].

  • enforceBucketQueueAlgorithm – If set to true, uses a bucket priority queue data structure. This it is generally slower than ParK but may be more flexible. TODO check

  • storeNodeOrder – If set to true, the order of the nodes in ascending order of the cores is stored and can later be returned using getNodeOrder(). Enforces the sequential bucket priority queue algorithm.

virtual void run() override

Perform k-core decomposition of graph passed in constructor.

Cover getCover() const

Get the k-cores as a graph cover object.


the k-cores as a Cover

Partition getPartition() const

Get the k-shells as a partition object


the k-shells as a Partition

index maxCoreNumber() const

Get maximum core number.


The maximum core number

virtual double maximum() override

Get the theoretical maximum of centrality score in the given graph.


The theoretical maximum centrality score.

const std::vector<node> &getNodeOrder() const

Get the node order.

This is only possible when storeNodeOrder was set.


The nodes sorted by increasing core number.