Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/clustering_coefficient/
Documentation version: v5.3.2

# 聚类系数

本文介绍聚类系数算法，并演示如何用 GQL 实现该算法。

## 算法介绍

聚类系数用于衡量点邻居之间相互连接的紧密程度。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见[聚类系数](https://en.wikipedia.org/wiki/Clustering_coefficient)。

## 数据模型

为了在 GQL 中实现聚类系数算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/clustering_coefficient/#1_prepare_graph_data)。

## 过程实现[]()

为了计算聚类系数结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/clustering_coefficient/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- 该过程不需要输入参数。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `degree` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点的邻居数量（度数）。
 | `nbr` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点的邻居 ID 集合。
 | `closed` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点邻居之间的边数（闭合三角形数）。
 | `result_table` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 存储每点聚类系数的输出表。

以下步骤概述了该过程的逻辑：

1. 计算每个点的`degree`，并将其邻居 ID 收集到`nbr`。
2. 对每个点，遍历其关联边并统计邻居之间的闭合关系。对于中心点，每个闭合关系会沿两条关联边各统计一次，因此会被累计两次。
3. 对每个点按公式`closed / (degree × (degree - 1))`计算局部聚类系数。
4. 返回所有点的（`vertex_id`、`clustering_coefficient`）。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
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. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/clustering_coefficient/`：

  - [clustering_coefficient_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/clustering_coefficient/clustering_coefficient_node.csv)：点数据。
  - [clustering_coefficient_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/clustering_coefficient/clustering_coefficient_edge.csv)：边数据。

查看 CSV 内容

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 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: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

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

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现聚类系数算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/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. 调用过程[]()

计算各点的度、三角形数量和聚类系数。

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

````

返回：

展开查看返回

````
+-----------+--------+----------------+---------------------+
| 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  |
+-----------+--------+----------------+---------------------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。