Infomap¶

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

算法介绍¶

Infomap 通过最小化随机游走编码长度来划分社区。

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

更多信息，请参见 Infomap。

数据模型¶

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

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

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

过程实现 ¶

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

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

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

max_flow_iter：INT64类型，默认值50。流量均衡（PageRank）阶段的最大迭代次数。
max_move_iter：INT64类型，默认值20。点移动（社区重分配）阶段的最大迭代次数。
teleport_prob：DOUBLE类型，默认值0.15。随机游走流量模型中的传送概率（鉳尼因子）。
tolerance：DOUBLE类型，默认值0.000000001。流量均衡阶段的收敛阈値。

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

变量名	变量类型	描述
`node_cnt`	全局 SumAgg 聚合值变量	图中点总数。
`flow_iter`	原始值变量	流量均衡阶段的迭代计数。
`move_iter`	原始值变量	模块重分配阶段的迭代计数。
`flow_delta`	全局 SumAgg 聚合值变量	当前迭代中总流量的变化量。
`dangling`	全局 SumAgg 聚合值变量	从悬挂（汇点）点均匀重分配的流量总和。
`changed`	原始值变量	本轮是否有点更改了所属模块。
`qsum`	全局 SumAgg 聚合值变量	当前映射方程值（总描述长度）。
`modf`	全局 SumAgg 聚合值变量	全局 {模块 ID → 总流量} 映射。
`mods`	全局 SumAgg 聚合值变量	全局 {模块 ID → 点数} 映射。
`msink`	全局 SumAgg 聚合值变量	全局 {模块 ID → 悬挂流量} 映射。
`medge`	全局 SumAgg 聚合值变量	全局 {模块 ID → 模块间流量} 映射。
`mod`	点绑定 SumAgg 聚合值变量	每点当前所属模块（社区）。
`nextm`	点绑定 SumAgg 聚合值变量	每点在下一步的候选模块。
`outw`	点绑定 SumAgg 聚合值变量	每点出边权重之和。
`flow`	点绑定 SumAgg 聚合值变量	每点稳态流量（类 PageRank 访问概率）。
`nextf`	点绑定 SumAgg 聚合值变量	当前迭代中正在更新的每点流量值。
`cand`	点绑定 SumAgg 聚合值变量	每点待考察的候选模块 ID 集合。
`outf`	点绑定 SumAgg 聚合值变量	每点的 {目标模块 → 出流量} 映射。
`inm`	点绑定 SumAgg 聚合值变量	每点的 {来源模块 → 入流量} 映射。
`result_table`	表变量	存储 (vertex_id, module) 结果对的输出表。

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

通过类 PageRank 迭代初始化每点的稳态流量flow，直至收敛（flow_delta低于阈值）。
将每个点分配到独立模块；计算模块级流量聚合（modf、mods、msink、medge）和初始映射方程值qsum。
迭代点移动阶段：对每个点，评估移入各邻居模块后qsum的减少量，执行使qsum最小化的移动；直至无法改进。
返回所有点的（vertex_id、module_id）。

操作步骤¶

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

1. 准备图数据 ¶

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

'''
CREATE GRAPH TYPE IF NOT EXISTS infomap_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/infomap/：

infomap_node.csv：点数据。
infomap_edge.csv：边数据。

查看 CSV 内容

infomap_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

infomap_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 #infomap_graph TYPED infomap_graph_type

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

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

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

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

2. 创建过程 ¶

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

'''
CREATE OR REPLACE PROCEDURE infomap(
  max_flow_iter INT64 DEFAULT 50,
  max_move_iter INT64 DEFAULT 20,
  teleport_prob DOUBLE DEFAULT 0.15,
  tolerance DOUBLE DEFAULT 0.000000001
)
RETURNS (vertex_id INT64, module_id INT64)
COMMENT "Compute a directed weighted two-level Infomap partition on a graph whose vertex primary key is id and edge weight property is weight. The procedure estimates directed flow with a PageRank-style random walk, then performs sweep-based greedy neighboring-module moves that decrease the two-level map equation before returning the final module assignment for each vertex."
AS {
  VALUE node_cnt SumAgg<INT64> = 0
  VALUE flow_iter INT64 = 0
  VALUE move_iter INT64 = 0
  VALUE flow_delta SumAgg<DOUBLE> = 0.0
  VALUE dangling SumAgg<DOUBLE> = 0.0
  VALUE changed OrAgg = true
  VALUE qsum SumAgg<DOUBLE> = 0.0

  VALUE modf MapAgg<INT64, SumAgg<DOUBLE>>
  VALUE mods MapAgg<INT64, SumAgg<INT64>>
  VALUE msink MapAgg<INT64, SumAgg<DOUBLE>>
  VALUE medge MapAgg<INT64, SumAgg<DOUBLE>>

  NODE VALUE mod SumAgg<INT64> = 0
  NODE VALUE nextm SumAgg<INT64> = 0
  NODE VALUE outw SumAgg<DOUBLE> = 0.0
  NODE VALUE flow SumAgg<DOUBLE> = 0.0
  NODE VALUE nextf SumAgg<DOUBLE> = 0.0
  NODE VALUE cand SetAgg<INT64>
  NODE VALUE outf MapAgg<INT64, SumAgg<DOUBLE>>
  NODE VALUE inm MapAgg<INT64, SumAgg<DOUBLE>>

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    module_id INT64
  }

  MATCH (n)
  PER NODE (n) {
    SET @node_cnt += 1
    SET n.@outw = 0.0
  }

  MATCH (s)-[e]->(t)
  PER PATH {
    SET s.@outw += CAST(e.weight AS DOUBLE)
  }

  MATCH (n)
  PER NODE (n) {
    SET n.@mod = n.id
    SET n.@nextm = n.id
    SET n.@flow = 1.0 / CAST(@node_cnt AS DOUBLE)
    SET n.@nextf = 0.0
    SET n.@cand.clear()
    SET n.@outf.clear()
    SET n.@inm.clear()
  }

  WHILE flow_iter < max_flow_iter THEN {
    SET @dangling = 0.0
    SET @flow_delta = 0.0

    MATCH (n)
    PER NODE (n) {
      SET n.@nextf = 0.0
    }

    MATCH (s)-[e]->(t)
    WHERE s.@outw > 0.0
    PER PATH {
      SET t.@nextf += (1.0 - teleport_prob) * s.@flow * CAST(e.weight AS DOUBLE) / s.@outw
    }

    MATCH (n)
    WHERE n.@outw = 0.0
    PER NODE (n) {
      SET @dangling += n.@flow
    }

    MATCH (n)
    PER NODE (n) {
      VALUE base DOUBLE = 0.0
      VALUE delta DOUBLE = 0.0

      SET base =
        teleport_prob / CAST(@node_cnt AS DOUBLE)
        + (1.0 - teleport_prob) * @dangling / CAST(@node_cnt AS DOUBLE)
      SET n.@nextf = n.@nextf + base
      SET delta = n.@nextf - n.@flow

      IF delta < 0.0 THEN {
        SET delta = 0.0 - delta
      }

      SET @flow_delta += delta
      SET n.@flow = n.@nextf
    }

    SET flow_iter = flow_iter + 1

    IF @flow_delta <= tolerance THEN {
      BREAK
    }
  }

  WHILE @changed AND move_iter < max_move_iter THEN {
    SET move_iter = move_iter + 1
    SET @changed = false
    SET @qsum = 0.0
    SET @modf.clear()
    SET @mods.clear()
    SET @msink.clear()
    SET @medge.clear()

    MATCH (n)
    PER NODE (n) {
      SET n.@nextm = n.@mod
      SET n.@cand.clear()
      SET n.@outf.clear()
      SET n.@inm.clear()

      SET @modf += TUPLE(n.@mod, n.@flow)
      SET @mods += TUPLE(n.@mod, 1)

      IF n.@outw = 0.0 THEN {
        SET @msink += TUPLE(n.@mod, n.@flow)
      }
    }

    MATCH (s)-[e]->(t)
    PER PATH {
      VALUE edge_flow DOUBLE = 0.0

      SET s.@cand += t.@mod
      SET t.@cand += s.@mod

      IF s.@outw > 0.0 THEN {
        SET edge_flow = (1.0 - teleport_prob) * s.@flow * CAST(e.weight AS DOUBLE) / s.@outw
        SET s.@outf += TUPLE(t.@mod, edge_flow)
        SET t.@inm += TUPLE(s.@mod, edge_flow)
      }
    }

    MATCH (n)
    PER NODE (n) {
      VALUE mod_size DOUBLE = 0.0
      VALUE edge_exit DOUBLE = 0.0
      VALUE exit_prob DOUBLE = 0.0

      SET mod_size = CAST(@mods.get(n.@mod) AS DOUBLE)

      IF n.@outw = 0.0 THEN {
        SET exit_prob = n.@flow * (CAST(@node_cnt AS DOUBLE) - mod_size) / CAST(@node_cnt AS DOUBLE)
      }
      ELSE {
        SET edge_exit = (1.0 - teleport_prob) * n.@flow - n.@outf.get(n.@mod)
        SET exit_prob =
          teleport_prob * n.@flow * (CAST(@node_cnt AS DOUBLE) - mod_size) / CAST(@node_cnt AS DOUBLE)
          + edge_exit
      }

      SET @qsum += exit_prob
      SET @medge += TUPLE(n.@mod, edge_exit)
    }

    MATCH (n)
    WHERE n.@cand.size() > 0
    PER NODE (n) {
      VALUE node_count DOUBLE = 0.0
      VALUE from_mod INT64 = 0
      VALUE best_mod INT64 = 0
      VALUE cand_idx INT64 = 0
      VALUE cand_mod INT64 = 0

      VALUE from_vol DOUBLE = 0.0
      VALUE to_vol DOUBLE = 0.0
      VALUE from_sink DOUBLE = 0.0
      VALUE to_sink DOUBLE = 0.0
      VALUE from_edge DOUBLE = 0.0
      VALUE to_edge DOUBLE = 0.0
      VALUE from_vol_new DOUBLE = 0.0
      VALUE to_vol_new DOUBLE = 0.0
      VALUE from_sink_new DOUBLE = 0.0
      VALUE to_sink_new DOUBLE = 0.0
      VALUE from_edge_new DOUBLE = 0.0
      VALUE to_edge_new DOUBLE = 0.0

      VALUE from_sz INT64 = 0
      VALUE to_sz INT64 = 0
      VALUE from_sz_new INT64 = 0
      VALUE to_sz_new INT64 = 0

      VALUE from_out_same DOUBLE = 0.0
      VALUE to_out_same DOUBLE = 0.0
      VALUE from_in_same DOUBLE = 0.0
      VALUE to_in_same DOUBLE = 0.0
      VALUE old_edge_x DOUBLE = 0.0
      VALUE new_edge_x DOUBLE = 0.0

      VALUE q_from DOUBLE = 0.0
      VALUE q_to DOUBLE = 0.0
      VALUE q_from_new DOUBLE = 0.0
      VALUE q_to_new DOUBLE = 0.0
      VALUE q_total_new DOUBLE = 0.0

      VALUE p_from DOUBLE = 0.0
      VALUE p_to DOUBLE = 0.0
      VALUE p_from_new DOUBLE = 0.0
      VALUE p_to_new DOUBLE = 0.0

      VALUE best_delta DOUBLE = 0.0
      VALUE delta DOUBLE = 0.0

      SET node_count = CAST(@node_cnt AS DOUBLE)
      SET from_mod = n.@mod
      SET best_mod = from_mod
      SET from_vol = @modf.get(from_mod)
      SET from_sink = @msink.get(from_mod)
      SET from_edge = @medge.get(from_mod)
      SET from_sz = @mods.get(from_mod)
      SET q_from =
        from_edge
        + (teleport_prob * from_vol + (1.0 - teleport_prob) * from_sink)
          * (node_count - CAST(from_sz AS DOUBLE))
          / node_count
      SET p_from = q_from + from_vol

      WHILE cand_idx < n.@cand.size() THEN {
        SET cand_mod = n.@cand[cand_idx]
        SET cand_idx = cand_idx + 1

        IF cand_mod <> from_mod THEN {
          SET to_vol = @modf.get(cand_mod)
          SET to_sink = @msink.get(cand_mod)
          SET to_edge = @medge.get(cand_mod)
          SET to_sz = @mods.get(cand_mod)
          SET q_to =
            to_edge
            + (teleport_prob * to_vol + (1.0 - teleport_prob) * to_sink)
              * (node_count - CAST(to_sz AS DOUBLE))
              / node_count
          SET p_to = q_to + to_vol

          SET from_vol_new = from_vol - n.@flow
          SET to_vol_new = to_vol + n.@flow
          SET from_sink_new = from_sink
          SET to_sink_new = to_sink
          SET from_edge_new = from_edge
          SET to_edge_new = to_edge
          SET from_sz_new = from_sz - 1
          SET to_sz_new = to_sz + 1
          SET old_edge_x = 0.0
          SET new_edge_x = 0.0
          SET from_out_same = n.@outf.get(from_mod)
          SET to_out_same = n.@outf.get(cand_mod)
          SET from_in_same = n.@inm.get(from_mod)
          SET to_in_same = n.@inm.get(cand_mod)

          IF n.@outw = 0.0 THEN {
            SET from_sink_new = from_sink_new - n.@flow
            SET to_sink_new = to_sink_new + n.@flow
          }
          ELSE {
            SET old_edge_x = (1.0 - teleport_prob) * n.@flow - from_out_same
            SET new_edge_x = (1.0 - teleport_prob) * n.@flow - to_out_same
            SET from_edge_new = from_edge_new - old_edge_x + from_in_same
            SET to_edge_new = to_edge_new + new_edge_x - to_in_same
          }

          IF from_sz_new > 0 THEN {
            SET q_from_new =
              from_edge_new
              + (teleport_prob * from_vol_new + (1.0 - teleport_prob) * from_sink_new)
                * (node_count - CAST(from_sz_new AS DOUBLE))
                / node_count
          }
          ELSE {
            SET q_from_new = 0.0
          }

          SET q_to_new =
            to_edge_new
            + (teleport_prob * to_vol_new + (1.0 - teleport_prob) * to_sink_new)
              * (node_count - CAST(to_sz_new AS DOUBLE))
              / node_count
          SET p_from_new = q_from_new + from_vol_new
          SET p_to_new = q_to_new + to_vol_new
          SET q_total_new = @qsum - q_from - q_to + q_from_new + q_to_new

          SET delta = 0.0

          IF q_total_new > 0.0 THEN {
            SET delta = delta + q_total_new * ln(q_total_new)
          }
          IF @qsum > 0.0 THEN {
            SET delta = delta - @qsum * ln(@qsum)
          }

          IF q_from_new > 0.0 THEN {
            SET delta = delta - 2.0 * q_from_new * ln(q_from_new)
          }
          IF q_to_new > 0.0 THEN {
            SET delta = delta - 2.0 * q_to_new * ln(q_to_new)
          }
          IF q_from > 0.0 THEN {
            SET delta = delta + 2.0 * q_from * ln(q_from)
          }
          IF q_to > 0.0 THEN {
            SET delta = delta + 2.0 * q_to * ln(q_to)
          }

          IF p_from_new > 0.0 THEN {
            SET delta = delta + p_from_new * ln(p_from_new)
          }
          IF p_to_new > 0.0 THEN {
            SET delta = delta + p_to_new * ln(p_to_new)
          }
          IF p_from > 0.0 THEN {
            SET delta = delta - p_from * ln(p_from)
          }
          IF p_to > 0.0 THEN {
            SET delta = delta - p_to * ln(p_to)
          }

          IF delta < best_delta - tolerance OR (delta <= best_delta + tolerance AND delta < -tolerance AND cand_mod < best_mod) THEN {
            SET best_delta = delta
            SET best_mod = cand_mod
          }
        }
      }

      IF best_mod <> from_mod THEN {
        SET n.@nextm = best_mod
        SET @changed += true
      }
    }

    MATCH (n)
    WHERE n.@nextm <> n.@mod
    PER NODE (n) {
      SET n.@mod = n.@nextm
    }
  }

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

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

3. 调用过程 ¶

计算社区划分，返回各点所属的模块 ID。

USE #infomap_graph CALL infomap() RETURN vertex_id, module_id

返回：

展开查看返回

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

保存结果到文件或图中

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

Infomap¶

算法介绍¶

数据模型¶

过程实现¶

操作步骤¶

1. 准备图数据¶

2. 创建过程¶

3. 调用过程¶

过程实现 ¶

1. 准备图数据 ¶

2. 创建过程 ¶

3. 调用过程 ¶