K-Core Decomposition
K-Core Decomposition identifies subgraphs where every node has a degree of at least k
.
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 algorithm iteratively removes 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 such as social network analysis, where it can help identify cohesive groups, and in network resilience analysis, where it can help understand a networkβs robustness 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
Required arguments:
GRAPH_NAME
: Name of the projected graph to run the algorithm on- Type:
STRING
- Type:
Returns:
node
: A node objectk_degree
: The k-core degree of the node
Example
Create the node and relationship tables:
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);
Create a projected graph from the node and relationship tables:
CALL project_graph('Graph', ['Person'], ['KNOWS']);
Run the K-Core Decomposition algorithm on the projected graph:
CALL k_core_decomposition('Graph')RETURN node.name, k_degreeORDER BY k_degree DESC;
βββββββββββββ¬ββββββββββββ node.name β k_degree ββ STRING β INT64 ββββββββββββββΌβββββββββββ€β Frank β 3 ββ George β 3 ββ Eve β 3 ββ Derek β 3 ββ Charlie β 1 ββ Bob β 1 ββ Alice β 1 ββββββββββββββ΄βββββββββββ