k-Core

Overview

The k-Core algorithm finds the largest connected subgraph where every node has at least degree k. It is commonly employed to identify tightly connected groups in a graph for further analysis. Common applications include financial risk control, social network analysis, and biological studies. The algorithm runs in linear time, making it efficient for large graphs. Its output is also easy to interpret, helping reveal structural patterns and relationships.

The widely accepted concept of k-core was first introduced 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 computed through iterative pruning. Nodes with a degree less than k are successively removed until all remaining nodes have degrees greater than or equal to k.

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. They are not counted when calculating the degree of a node.
• The k-Core algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
INSERT (A:default {_id: "A"}),       
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),       
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),       
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),       
       (H:default {_id: "H"}),
       (I:default {_id: "I"}),       
       (A)-[:default]->(C),
       (B)-[:default]->(B),
       (B)-[:default]->(D),
       (C)-[:default]->(B),
       (C)-[:default]->(D),
       (E)-[:default]->(D),
       (E)-[:default]->(F),
       (E)-[:default]->(G),
       (E)-[:default]->(H),
       (F)-[:default]->(D),
       (G)-[:default]->(D),
       (G)-[:default]->(F),
       (I)-[:default]->(A);

Running on HDC Graphs

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: k_core

File Writeback

GQLUQL
CALL algo.k_core.write("my_hdc_graph", {
  k: 3,
  return_id_uuid: "id"
}, {
  file: {
    filename: "3-core"
  }
})

Result:

File: 3-core
_id
G
F
E
D

Full Return

GQLUQL
CALL algo.k_core.run("my_hdc_graph", {
  k: 2
}) YIELD k2
RETURN k2

Result
[{"id":"G","uuid":"13690943966717935617","schema":"default","values":{}}]
[{"id":"D","uuid":"288231475663339522","schema":"default","values":{}}]
[{"id":"F","uuid":"2882304861028745219","schema":"default","values":{}}]
[{"id":"B","uuid":"3530823207370096641","schema":"default","values":{}}]
[{"id":"E","uuid":"10520409829049106435","schema":"default","values":{}}]
[{"id":"C","uuid":"12033619303845593090","schema":"default","values":{}}]

Stream Return

GQLUQL
CALL algo.k_core.stream("my_hdc_graph", {
  k: 3
}) YIELD r
FOR node in r
RETURN node._id

Result:

Running on Distributed Projections

Creating Distributed Projection

To project the entire graph to its shard servers as myProj:

GQLUQL
CREATE PROJECTION myProj OPTIONS {
  nodes: {"*": ["*"]}, 
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true
}

Parameters

Algorithm name: k_core

File Writeback

GQLUQL
CALL algo.k_core.write("myProj", {
  k: 3
}, {
  file: {
    filename: "3-core"
  }
})

File: 3-core
_id
E
D
F
G