com.raphtory.algorithms.generic.KCore

KCore

KCore(3)

Identify the K-Cores of a graph with given k

A k-core of a graph is a maximal subgraph in which every vertex has degree at least k. This algorithm identifies the k-cores of a graph. (https://en.wikipedia.org/w/index.php?title=Degeneracy_(graph_theory)&action=edit&section=3).

Parameters

k: Int

The value of k to run k-core with.

resetStates: Bool = True

When true this resets all the effectiveDegree states at the start of running so the algorithm runs from scratch, when false reuses previous effectiveDegree data and runs on the remaining alive nodes (e.g. for nested KCore iterations like in Coreness.)

Defaults to true, generally should be true.

States

effectiveDegree: Int

Stores the current number of alive neighbours of each vertex (decreases as nodes get deleted).

At the end of the algorithm the nodes in the k-cores are those with effectiveDegree => k.

In a tabularise this can be filtered using the boolean vertex.getState[Int]("effectiveDegree") >= k

Returns

vertex name

if in the k-core (only returns true rows)

name: String

vertex.getState[Int]("effectiveDegree") >= k: Bool

Implementation

The algorithm works by recursively removing nodes that don’t have enough alive neighbours for them to remain in the graph.

  1. Each node sets is effectiveDegree to it’s actual degree (as all it’s neighbours are currently alive). If it has degree < k, it can’t be in the k-core, so dies and broadcasts its death. If resetStates == false, we start from previous effectiveDegree values instead.

  2. When a node receives a message saying its neighbour has died, it decrements its effective degree.

  3. It then checks if its effectiveDegree < k, in which case it can’t be in the k-core, so dies and broadcasts its death.

  4. This continues until no more nodes are dying.