kCore Decomposition
A kcore of a graph is a maximal connected subgraph in which every vertex is connected to at least \$k\$ vertices in the subgraph.
This algorithm takes a range of values for \$k\$ and returns the vertex set that constitutes the kcore with the highest possible value of \$k\$ within the range.
To obtain the kcore of a graph, the algorithm first deletes the vertices whose outdegree is less than k. It then updates the outdegree of the neighbors of the deleted vertices, and if that causes a vertex’s outdegree to fall below k, it will also delete that vertex. The algorithm repeats this operation until every vertex left in the subgraph has an outdegree of at least k.
Notes
This is an implementation of Algorithm 2 in Scalable KCore Decomposition for Static Graphs Using a Dynamic Graph Data Structure, Tripathy et al., IEEE Big Data 2018.
Specifications
tg_kcore(STRING v_type, STRING e_type, INT k_min = 0,
INT k_max = 1, BOOL print_results = TRUE,
STRING result_attribute = "", STRING file_path = "",
BOOL print_all_k = FALSE, BOOL show_shells=FALSE)
Parameters
Parameter  Description 


Vertex type to include in the kcore 

Edge type to count for kcore connections 

Minimum value of k. If the actual maximum core is below 

Maximum value of k. If 

Boolean value that decides whether the algorithm will return output in JSON 

An attribute of the vertex to save the core level of the vertex to. If 

If 

Whether to print all k connections 

The kshell is the set of vertices that are part of the kcore but not part of the (k+1)core. If 
Example
In the example below based on the social
graph from GSQL 101, we can see that Dan, Tom, and Jenny make up a 2core, which is the maxcore of the graph:
If we run the kcore
algorithm on this small graph like so:
RUN QUERY tg_kcore("person", "friendship", 0, 1, TRUE, "", "", FALSE, FALSE)
Here is the returned JSON response, which includes a 2core that is comprised of Dan, Jenny, and Tom:
[
{
"core_size": 3,
"k": 2, // the kcore with the highest possible k is returned
"max_core": [
{
"attributes": {
"@core": 2,
"@deg": 0,
"age": 40,
"gender": "male",
"name": "Tom",
"state": "ca"
},
"v_id": "Tom",
"v_type": "person"
},
{
"attributes": {
"@core": 2,
"@deg": 0,
"age": 34,
"gender": "male",
"name": "Dan",
"state": "ny"
},
"v_id": "Dan",
"v_type": "person"
},
{
"attributes": {
"@core": 2,
"@deg": 0,
"age": 25,
"gender": "female",
"name": "Jenny",
"state": "tx"
},
"v_id": "Jenny",
"v_type": "person"
}
]
}
]