Overview
The k-Core algorithm identifies the maximal connected subgraph where all nodes have a minimum degree of k. It is commonly employed to extract closely connected groups in a graph for further analysis. The algorithm is widely utilized in various research domains including financial risk control, social network analysis, and biology. One of the key advantages of the k-Core algorithm is its low time complexity (linear), making it efficient for large-scale graph processing. Additionally, the resulting subgraphs have good intuitive interpretability, aiding in the understanding of the graph's structural patterns and relationships.
The commonly accepted concept of k-core was first proposed by Seidman:
- S.B. Seidman, Network Structure And Minimum Degree. Soc Netw 5:269-287 (1983)
Concepts
k-Core
The k-core of a graph is obtained through an iterative pruning process. Starting with the original graph, nodes with a degree less than k are successively removed until only nodes with degrees greater than or equal to k remain.
Below is the pruning process to get the 3-core of the graph. In the first round, nodes {a, d, f} with degree less than 3 are removed , which then affects the removal of node b in the second round. After the second round, all remaining nodes have a degree of at least 3. Therefore, the pruning process ends, and the 3-core of this graph is induced by nodes {c, e, g, h}.
Ultipa's k-Core algorithm identifies the k-core in each connected component.
Considerations
- The k-Core algorithm ignores self-loops in the graph. Any self-loop present is not considered when calculating the degree of the respective node.
- The k-Core algorithm ignores the direction of edges but calculates them as undirected edges.
Syntax
- Command:
algo(k_core)
- Parameters:
Name |
Type |
Spec |
Default |
Optional |
Description |
---|---|---|---|---|---|
k | int | ≥1 | / | No | Each node in the k-core has a degree that is equal to or greater than k |
Examples
The example graph is as follows:
File Writeback
Spec |
Content |
Description |
---|---|---|
filename | _id |
ID of node in the k-core |
algo(k_core).params({
k: 3
}).write({
file:{
filename: '3-core'
}
})
Results: File 3-core
G
F
E
D
Direct Return
Alias Ordinal |
Type |
Description |
---|---|---|
0 | []perNode | UUIDs of nodes in the k-core |
algo(k_core).params({
k: 2
}) as k2
return k2
Results: k2
7 |
6 |
5 |
4 |
2 |
3 |
Stream Return
Alias Ordinal |
Type |
Description |
---|---|---|
0 | []perNode | UUIDs of nodes in the k-core |
algo(k_core).params({
k: 2
}).stream() as k2
find().nodes(k2) as nodes
return nodes{*}
Results: nodes
_id | _uuid |
---|---|
G | 7 |
F | 6 |
E | 5 |
D | 4 |
C | 2 |
B | 3 |