com.raphtory.algorithms.generic.KCore
KCore
KCore(3)
Identify the KCores of a graph with given k
A kcore of a graph is a maximal subgraph in which every vertex has degree at least k. This algorithm identifies the kcores of a graph. (https://en.wikipedia.org/w/index.php?title=Degeneracy_(graph_theory)&action=edit§ion=3).
Parameters
k: Int
The value of k to run kcore 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 kcores 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 kcore (only returns true rows) 



Implementation
The algorithm works by recursively removing nodes that don’t have enough alive neighbours for them to remain in the graph.
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 kcore, so dies and broadcasts its death. If resetStates == false, we start from previous effectiveDegree values instead.
When a node receives a message saying its neighbour has died, it decrements its effective degree.
It then checks if its effectiveDegree < k, in which case it can’t be in the kcore, so dies and broadcasts its death.
This continues until no more nodes are dying.