Class CoreDecomposition¶

Inheritance Relationships¶

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

Parameters:

• 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.

Returns:

the k-cores as a Cover

Partition getPartition() const¶

Get the k-shells as a partition object

Returns:

the k-shells as a Partition

index maxCoreNumber() const¶

Get maximum core number.

Returns:

The maximum core number

virtual double maximum() override¶

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

Returns:

The theoretical maximum centrality score.

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

Get the node order.

This is only possible when storeNodeOrder was set.

Returns:

The nodes sorted by increasing core number.