HANP¶

本文介绍 HANP 算法，并演示如何用 GQL 实现该算法。

算法介绍¶

HANP 结合邻域影响进行加权标签传播以进行社区发现。

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

更多信息，请参见 HANP。

数据模型¶

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

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

该图类型的完整定义，请参见准备图数据。

过程实现 ¶

为了计算 HANP 结果，创建一个过程。

关于该过程的更多信息，请参见过程实现。下文将介绍该过程的关键组成部分及其工作原理。

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

max_iter：INT64类型，默认值20。最大标签传播迭代次数。
hop_decay：DOUBLE类型，默认值0.1。每跳对偏好分数的衰减因子（取值范围：(0, 1])。
preference_exponent：DOUBLE类型，默认值1.0。衡量邻居偏好分数影响的指数。

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

变量名	变量类型	描述
`iter`	原始值变量	当前迭代次数。
`changed`	原始值变量	本轮迭代中是否有点标签发生变化。
`degree`	点绑定 SumAgg 聚合值变量	每点度数，用于偏好分数归一化。
`label`	点绑定 SumAgg 聚合值变量	每点当前的社区标签。
`next_label`	点绑定 SumAgg 聚合值变量	每点在下一轮迭代的候选标签。
`score`	点绑定 SumAgg 聚合值变量	每点偏好分数，表示标签稳定性。
`next_score`	点绑定 SumAgg 聚合值变量	每点在下一轮的偏好分数。
`support`	点绑定 SumAgg 聚合值变量	每点来自邻居的 {标签 → 加权票数} 映射。
`prop`	点绑定 SumAgg 聚合值变量	每点来自邻居的 {标签 → 最大偏好分} 映射。
`result_table`	表变量	存储 (vertex_id, label) 结果对的输出表。

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

从每个点的rating属性初始化label，将score初始化为 1.0，并计算degree。
迭代：对每个点，结合边权和邻居偏好分数，将邻居标签的加权投票收集到support和prop中。
选取加权支持度最高的标签作为next_label，并按1 / degree衰减next_score。
将next_label和next_score写入label和score；在无变化或达到max_iter时停止。返回（vertex_id、label）。

操作步骤¶

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。

1. 准备图数据 ¶

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

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

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

hanp_node.csv：点数据。
hanp_edge.csv：边数据。

查看 CSV 内容

hanp_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

hanp_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

基于图类型创建临时图，并将数据文件加载到临时图中。

CREATE TEMPORARY GRAPH IF NOT EXISTS #hanp_graph TYPED hanp_graph_type

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

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

'''
USE #hanp_graph
MATCH (n)
RETURN count(n) AS node_count
'''

node_count应为24。点数不符时，先按文件问题排查检查文件和导入结果。

2. 创建过程 ¶

创建实现 HANP 算法的过程。关于该过程的更多信息，请参见过程实现。

'''
CREATE OR REPLACE PROCEDURE hanp(
  max_iter INT64 DEFAULT 20,
  hop_decay DOUBLE DEFAULT 0.1,
  preference_exponent DOUBLE DEFAULT 1.0
)
RETURNS (vertex_id INT64, community_id INT64, label_score DOUBLE)
COMMENT "Run a classic weighted undirected HANP community detection pass. Each vertex starts with its own id as the label, neighbor votes are weighted by edge weight, degree^preference_exponent, and attenuated label score, and the procedure returns the last partition reached within max_iter rounds."
AS {
  VALUE iter INT64 = 0
  VALUE changed OrAgg = true

  NODE VALUE degree SumAgg<INT64> = 0
  NODE VALUE label SumAgg<INT64> = 0
  NODE VALUE next_label SumAgg<INT64> = 0
  NODE VALUE score SumAgg<DOUBLE> = 1.0
  NODE VALUE next_score SumAgg<DOUBLE> = 1.0
  NODE VALUE support MapAgg<INT64, SumAgg<DOUBLE>>
  NODE VALUE prop MapAgg<INT64, MaxAgg<DOUBLE>>

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    community_id INT64,
    label_score DOUBLE
  }

  MATCH (n)
  PER NODE (n) {
    SET n.@degree = 0
    SET n.@label = n.id
    SET n.@next_label = n.id
    SET n.@score = 1.0
    SET n.@next_score = 1.0
    SET n.@support.clear()
    SET n.@prop.clear()
  }

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

  WHILE @changed AND iter < max_iter THEN {
    SET iter = iter + 1
    SET @changed = false

    MATCH (n)
    PER NODE (n) {
      SET n.@next_label = n.@label
      SET n.@next_score = n.@score
      SET n.@support.clear()
      SET n.@prop.clear()
    }

    MATCH (s)-[e]-(t)
    PER PATH {
      VALUE propagated DOUBLE = 0.0
      VALUE preference DOUBLE = 1.0

      SET propagated = t.@score - hop_decay

      IF propagated < 0.0 THEN {
        SET propagated = 0.0
      }

      IF t.@degree > 0 THEN {
        SET preference = exp(preference_exponent * ln(CAST(t.@degree AS DOUBLE)))
      }

      SET s.@support += TUPLE(t.@label, preference * propagated * CAST(e.weight AS DOUBLE))
      SET s.@prop += TUPLE(t.@label, propagated)
    }

    MATCH (s)
    WHERE s.@support.size() > 0
    PER NODE (s) {
      VALUE idx INT64 = 0
      VALUE cand_label INT64 = 0
      VALUE cand_support DOUBLE = 0.0
      VALUE cand_prop DOUBLE = 0.0
      VALUE best_label INT64 = s.@label
      VALUE best_support DOUBLE = -1.0
      VALUE best_prop DOUBLE = s.@score

      WHILE idx < s.@support.size() THEN {
        SET cand_label = (s.@support[idx])._0
        SET cand_support = (s.@support[idx])._1
        SET cand_prop = s.@prop.get(cand_label)

        IF cand_support > best_support
          OR (cand_support = best_support AND cand_prop > best_prop)
          OR (cand_support = best_support AND cand_prop = best_prop AND cand_label < best_label) THEN {
          SET best_label = cand_label
          SET best_support = cand_support
          SET best_prop = cand_prop
        }

        SET idx = idx + 1
      }

      SET s.@next_label = best_label
      SET s.@next_score = best_prop
    }

    MATCH (n)
    PER NODE (n) {
      IF n.@next_label <> n.@label THEN {
        SET @changed += true
      }

      SET n.@label = n.@next_label
      SET n.@score = n.@next_score
    }
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@label, n.@score INTO result_table
  }

  FOR r IN result_table
  RETURN
    r.vertex_id AS vertex_id,
    r.community_id AS community_id,
    r.label_score AS label_score
  ORDER BY vertex_id ASC
}
'''

3. 调用过程 ¶

使用过程的默认参数计算社区划分，返回各点的社区 ID 和标签分数。

USE #hanp_graph CALL hanp() RETURN vertex_id, community_id, label_score

返回：

展开查看返回

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

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 EXPORT。导出字段应与返回列及目标属性对应。

HANP¶

算法介绍¶

数据模型¶

过程实现¶

操作步骤¶

1. 准备图数据¶

2. 创建过程¶

3. 调用过程¶

过程实现 ¶

1. 准备图数据 ¶

2. 创建过程 ¶

3. 调用过程 ¶