Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_core/
Documentation version: v5.3.2

# K-Core

## Algorithm introduction

K-Core peels nodes iteratively and keeps the maximal subgraph in which each node has degree at least K.

Iteratively peel nodes whose undirected degree is less than k and return the remaining k-core nodes.

For more information, see [K-Core](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)).

## Data model

To implement the K-Core algorithm in GQL, the following data model is used to create a graph type:

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_core/#1_prepare_graph_data).

## Procedure implementation[]()

To compute K-Core results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_core/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- `k`: `INT64`. Minimum degree threshold: only nodes with degree >= k are kept.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `frontier` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Active set of nodes being processed in the current peeling step.
 | `has_active` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether any node is still active and may be peeled.
 | `degree` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node remaining degree, decremented as neighbors are peeled.
 | `alive` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node flag indicating the node survives the current k threshold.
 | `result_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing surviving (vertex_id, degree) pairs.

The following steps outline the logic of the procedure:

1. Initialize all nodes as `alive` and set each node's `degree` to its actual degree.
2. Iteratively remove nodes whose `degree` is below the threshold `k` (peeling step); decrement neighbors' `degree` when a node is removed.
3. Repeat until no more nodes are removed (`has_active` is false).
4. Return the surviving nodes (`vertex_id`, `degree`) that form the k-core.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data[]()

1. 

Create a graph type that matches your data model.

````
'''
CREATE GRAPH TYPE IF NOT EXISTS k_core_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/k_core/` under your deployment directory:

  - [k_core_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/k_core/k_core_node.csv): Node data.
  - [k_core_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/k_core/k_core_edge.csv): Edge data.

Preview the CSV files

k_core_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

k_core_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

Create a temporary graph based on the graph type and load the data files into the temporary graph.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #k_core_graph TYPED k_core_graph_type

````

````
'''
USE #k_core_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/k_core/k_core_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/k_core/k_core_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

````
'''
USE #k_core_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

The expected `node_count` is `24`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure[]()

Create a procedure to implement the K-Core algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_core/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE k_core(k INT64)
RETURNS (vertex_id INT64, degree INT64)
COMMENT "Iteratively peel vertices whose undirected degree is less than k and return the remaining k-core vertices."
AS {
  VALUE frontier ACTIVE_SET
  VALUE has_active OrAgg = false

  NODE VALUE degree SumAgg<INT64> = 0
  NODE VALUE alive OrAgg = false

  TABLE result_table TYPED TABLE {vertex_id INT64, degree INT64}

  MATCH (s)
  PER NODE (s) {
    SET s.@alive = true
  }

  MATCH (s)-[e]-(t)
  PER PATH {
    SET s.@degree += 1
  }

  MATCH (s)
  WHERE s.@degree < k
  PER NODE (s) {
    SET s.@alive = false
    SET @has_active += true
  }
  FINALLY {
    SET frontier = s
  }

  WHILE @has_active = true THEN {
    SET @has_active = false

    MATCH (s)-[e]-(t)
    WHERE s IN frontier AND t.@alive = true
    PER PATH {
      SET t.@degree += -1
    }

    MATCH (t)
    WHERE t.@alive = true AND t.@degree < k
    PER NODE (t) {
      SET t.@alive = false
      SET @has_active += true
    }
    FINALLY {
      SET frontier = t
    }
  }

  MATCH (s)
  WHERE s.@alive = true
  PER NODE (s) {
    EXPORT s.id, s.@degree INTO result_table
  }

  FOR r IN result_table
  RETURN r.vertex_id AS vertex_id, r.degree AS degree
  ORDER BY degree DESC, vertex_id ASC
}
'''

````

### 3. Call your procedure[]()

Set `k` to `3` and return the nodes retained in the K-Core with their degrees.

````
USE #k_core_graph CALL k_core(3) RETURN vertex_id, degree

````

Returns:

Expand to view results

````
+-----------+--------+
| vertex_id | degree |
+-----------+--------+
| 6         | 7      |
| 9         | 7      |
| 12        | 7      |
| 15        | 7      |
| 18        | 7      |
| 21        | 7      |
| 4         | 6      |
| 5         | 6      |
| 8         | 6      |
| 10        | 6      |
| 14        | 6      |
| 2         | 5      |
| 3         | 5      |
| 16        | 5      |
| 19        | 5      |
| 1         | 4      |
| 11        | 4      |
| 13        | 4      |
| 17        | 4      |
| 20        | 4      |
| 22        | 4      |
| 24        | 4      |
| 7         | 3      |
| 23        | 3      |
+-----------+--------+

````

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.