k-Core

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:

Examples

The example graph is as follows:

File Writeback

UQL
algo(k_core).params({
  k: 3
}).write({
  file:{
    filename: '3-core'
  }
})

Results: File 3-core

File
G
F
E
D

Direct Return

UQL
algo(k_core).params({
  k: 2
}) as k2 
return k2

Results: k2

Stream Return

UQL
algo(k_core).params({
  k: 2
}).stream() as k2 
find().nodes(k2) as nodes
return nodes{*}

Results: nodes