  # Change Nickname

Current Nickname:

Certifications

Certificate Issued at Valid until Serial No. File
Serial No. Valid until

Not having one? Apply now! >>>

Invoice

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

# k-Core

✓ File Writeback ✕ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats

## 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:

## 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