K-Core Decomposition

The k-core decomposition identifies subgraphs where every node has a degree of at least k within the subgraph. In other words, a k-core is a maximal subgraph where each node is connected to at least k other nodes in the same subgraph. The k-core decomposition process involves iteratively removing nodes with degree less than k until no more nodes can be removed, with the remaining nodes forming the k-core.

K-Core decomposition is useful in domains like social network analysis, where it can help identify cohesive groups, and in network resilience analysis, where it can help understand the robustness of a network to node removal.

Kuzu implements a parallelized version of K-Core decomposition based on Ligra.

Syntax

CALL k_core_decomposition(
    graph_name
)
RETURN node, k_degree

Alias: kcore

Parameters

Parameter	Type	Optional	Default	Description
graph_name	STRING	No	-	Name of the projected graph to run the algorithm on

Return

Column	Type	Description
node	NODE	Node object
k_degree	INT64	The k-core degree of the node

Example

Define schema

CREATE NODE TABLE Node(id STRING PRIMARY KEY);
CREATE REL TABLE Edge(FROM Node to Node);

Insert nodes and edges

CREATE (alice:Node {id:'Alice'}),
        (bridget:Node {id:'Bridget'}),
        (charles:Node {id:'Charles'}),
        (doug:Node {id:'Doug'}),
        (eli:Node {id:'Eli'}),
        (filip:Node {id:'Filip'}),
        (greg:Node {id:'Greg'}),
        (alice)-[:Edge]->(bridget),
        (bridget)-[:Edge]->(charles),
        (charles)-[:Edge]->(doug),
        (doug)-[:Edge]->(eli),
        (doug)-[:Edge]->(filip),
        (doug)-[:Edge]->(greg),
        (eli)-[:Edge]->(filip),
        (eli)-[:Edge]->(greg),
        (filip)-[:Edge]->(greg);

Project graph

CALL project_graph('Graph', ['Node'], ['Edge']);

CALL k_core_decomposition('Graph') RETURN node.id, k_degree ORDER BY k_degree DESC;

┌─────────┬──────────┐
│ node.id │ k_degree │
│ STRING  │ INT64    │
├─────────┼──────────┤
│ Filip   │ 3        │
│ Greg    │ 3        │
│ Eli     │ 3        │
│ Doug    │ 3        │
│ Charles │ 1        │
│ Bridget │ 1        │
│ Alice   │ 1        │
└─────────┴──────────┘