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 Person(name STRING PRIMARY KEY);
CREATE REL TABLE KNOWS(FROM Person to Person);

Insert nodes and edges

CREATE (u0:Person {name: 'Alice'}),
        (u1:Person {name: 'Bob'}),
        (u2:Person {name: 'Charlie'}),
        (u3:Person {name: 'Derek'}),
        (u4:Person {name: 'Eve'}),
        (u5:Person {name: 'Frank'}),
        (u6:Person {name: 'George'}),
        (u0)-[:KNOWS]->(u1),
        (u1)-[:KNOWS]->(u2),
        (u2)-[:KNOWS]->(u3),
        (u3)-[:KNOWS]->(u4),
        (u3)-[:KNOWS]->(u5),
        (u3)-[:KNOWS]->(u6),
        (u4)-[:KNOWS]->(u5),
        (u4)-[:KNOWS]->(u6),
        (u5)-[:KNOWS]->(u6);

Project graph

CALL project_graph('Graph', ['Person'], ['KNOWS']);

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

┌───────────┬──────────┐
│ node.name │ k_degree │
│ STRING    │ INT64    │
├───────────┼──────────┤
│ Frank     │ 3        │
│ George    │ 3        │
│ Eve       │ 3        │
│ Derek     │ 3        │
│ Charlie   │ 1        │
│ Bob       │ 1        │
│ Alice     │ 1        │
└───────────┴──────────┘