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

# Clustering Coefficient

## Algorithm introduction

Clustering coefficient measures how tightly a node's neighbors are connected with each other.

Compute the classic local clustering coefficient for every node on an undirected graph. Nodes with degree less than 2 return coefficient 0.0.

For more information, see [Clustering Coefficient](https://en.wikipedia.org/wiki/Clustering_coefficient).

## Data model

To implement the Clustering Coefficient 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/clustering_coefficient/#1_prepare_graph_data).

## Procedure implementation[]()

To compute Clustering Coefficient 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/clustering_coefficient/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- This procedure does not require input parameters.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `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 neighbor count (degree).
 | `nbr` | 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 set of neighbor IDs.
 | `closed` | 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 count of edges between this node's neighbors (closed triangles).
 | `result_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing clustering coefficient per node.

The following steps outline the logic of the procedure:

1. Compute each node's `degree` and collect its neighbor IDs into `nbr`.
2. For each node, iterate over its incident edges and count neighbor-neighbor closures. Each closure is counted twice for the center node, once from each incident edge.
3. Compute the local clustering coefficient as `closed / (degree × (degree - 1))` for each node.
4. Return (`vertex_id`, `clustering_coefficient`) for all nodes.

## 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 clustering_coefficient_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/clustering_coefficient/` under your deployment directory:

  - [clustering_coefficient_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/clustering_coefficient/clustering_coefficient_node.csv): Node data.
  - [clustering_coefficient_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/clustering_coefficient/clustering_coefficient_edge.csv): Edge data.

Preview the CSV files

clustering_coefficient_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

````

clustering_coefficient_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 #clustering_coefficient_graph TYPED clustering_coefficient_graph_type

````

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

````

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

````
'''
USE #clustering_coefficient_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 Clustering Coefficient algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/clustering_coefficient/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE clustering_coefficient()
RETURNS (vertex_id INT64, degree INT64, triangle_count INT64, coefficient DOUBLE)
COMMENT "Compute the classic local clustering coefficient for every vertex on an undirected graph. Vertices with degree less than 2 return coefficient 0.0."
AS {
  NODE VALUE degree SumAgg<INT64> = 0
  NODE VALUE nbr SetAgg<INT64>
  NODE VALUE closed SumAgg<INT64> = 0

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    degree INT64,
    triangle_count INT64,
    coefficient DOUBLE
  }

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

  MATCH (s)-[e]-(t)
  PER PATH {
    VALUE idx INT64 = 0
    VALUE candidate_id INT64 = 0

    WHILE idx < t.@nbr.size() THEN {
      SET candidate_id = t.@nbr[idx]
      IF candidate_id <> s.id AND s.@nbr.contains_key(candidate_id) THEN {
        SET s.@closed += 1
      }
      SET idx = idx + 1
    }
  }

  MATCH (n)
  PER NODE (n) {
    VALUE triangle_count INT64 = 0
    VALUE coefficient DOUBLE = 0.0

    IF n.@degree >= 2 THEN {
      SET triangle_count = n.@closed / 2
      SET coefficient =
        CAST(n.@closed AS DOUBLE)
        / (CAST(n.@degree AS DOUBLE) * CAST(n.@degree - 1 AS DOUBLE))
    }

    EXPORT n.id, n.@degree, triangle_count, coefficient INTO result_table
  }

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

````

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

Compute the degree, triangle count, and clustering coefficient for each node.

````
USE #clustering_coefficient_graph CALL clustering_coefficient() RETURN vertex_id, degree, triangle_count, coefficient

````

Returns:

Expand to view results

````
+-----------+--------+----------------+---------------------+
| vertex_id | degree | triangle_count | coefficient         |
+-----------+--------+----------------+---------------------+
| 23        | 3      | 3              | 1.0                 |
| 1         | 4      | 5              | 0.8333333333333334  |
| 2         | 5      | 8              | 0.8                 |
| 3         | 5      | 8              | 0.8                 |
| 11        | 4      | 4              | 0.6666666666666666  |
| 20        | 4      | 4              | 0.6666666666666666  |
| 22        | 4      | 4              | 0.6666666666666666  |
| 24        | 4      | 4              | 0.6666666666666666  |
| 19        | 5      | 6              | 0.6                 |
| 5         | 6      | 8              | 0.5333333333333333  |
| 16        | 5      | 5              | 0.5                 |
| 17        | 4      | 3              | 0.5                 |
| 6         | 7      | 10             | 0.47619047619047616 |
| 15        | 7      | 9              | 0.42857142857142855 |
| 18        | 7      | 9              | 0.42857142857142855 |
| 21        | 7      | 9              | 0.42857142857142855 |
| 4         | 6      | 6              | 0.4                 |
| 8         | 6      | 6              | 0.4                 |
| 14        | 6      | 6              | 0.4                 |
| 9         | 7      | 8              | 0.38095238095238093 |
| 12        | 7      | 8              | 0.38095238095238093 |
| 10        | 6      | 5              | 0.3333333333333333  |
| 13        | 4      | 2              | 0.3333333333333333  |
| 7         | 3      | 1              | 0.3333333333333333  |
+-----------+--------+----------------+---------------------+

````

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.