Infomap¶

Algorithm introduction¶

Infomap optimizes flow-based code length and partitions nodes into communities with efficient random-walk encoding.

Compute a directed weighted two-level Infomap partition on a graph whose node 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 node.

For more information, see Infomap.

Data model¶

To implement the Infomap 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.

Procedure implementation ¶

To compute Infomap results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

max_flow_iter: INT64 (default: 50). Maximum iterations for the flow equilibration (PageRank) phase.
max_move_iter: INT64 (default: 20). Maximum iterations for the node-move (community reassignment) phase.
teleport_prob: DOUBLE (default: 0.15). Teleportation probability used in the random-walk flow model (damping factor).
tolerance: DOUBLE (default: 0.000000001). Convergence threshold for the flow equilibration phase.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
`node_cnt`	Global SumAgg aggregator value variable	Total number of nodes in the graph.
`flow_iter`	Primitive value variable	Iteration counter for the flow equilibration phase.
`move_iter`	Primitive value variable	Iteration counter for the module reassignment phase.
`flow_delta`	Global SumAgg aggregator value variable	Change in total flow in the current iteration.
`dangling`	Global SumAgg aggregator value variable	Accumulated flow from dangling (sink) nodes redistributed uniformly.
`changed`	Primitive value variable	Whether any node changed its module in this pass.
`qsum`	Global SumAgg aggregator value variable	Current map equation value (total description length).
`modf`	Global SumAgg aggregator value variable	Global map of {module_id → total flow}.
`mods`	Global SumAgg aggregator value variable	Global map of {module_id → node count}.
`msink`	Global SumAgg aggregator value variable	Global map of {module_id → dangling flow}.
`medge`	Global SumAgg aggregator value variable	Global map of {module_id → inter-module flow}.
`mod`	Node-attached SumAgg aggregator value variable	Per-node current module (community) assignment.
`nextm`	Node-attached SumAgg aggregator value variable	Per-node candidate module for the next step.
`outw`	Node-attached SumAgg aggregator value variable	Per-node total outgoing edge weight.
`flow`	Node-attached SumAgg aggregator value variable	Per-node stationary flow (PageRank-like visit probability).
`nextf`	Node-attached SumAgg aggregator value variable	Per-node flow value being updated in the current iteration.
`cand`	Node-attached SumAgg aggregator value variable	Per-node set of candidate module IDs to consider.
`outf`	Node-attached SumAgg aggregator value variable	Per-node map of {target_module → outgoing flow}.
`inm`	Node-attached SumAgg aggregator value variable	Per-node map of {source_module → incoming flow}.
`result_table`	Table variable	Output table storing (vertex_id, module) pairs.

The following steps outline the logic of the procedure:

Initialize per-node flow via PageRank-style iteration until convergence (flow_delta < threshold).
Assign each node to its own module; compute module-level flow aggregates (modf, mods, msink, medge) and the initial map equation qsum.
Iterate node-move phase: for each node, evaluate moving to each neighbor's module; apply the move that minimally decreases qsum; repeat until no improvement.
Return (vertex_id, module_id) 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 to check where to run commands and how the directory is mounted.

1. Prepare graph data ¶

Create a graph type that matches your data model.

'''
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)
}
'''

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

infomap_node.csv: Node data.
infomap_edge.csv: Edge data.

Preview the CSV files

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 a temporary graph based on the graph type and load the data files into the temporary graph.

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

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

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

The expected node_count is 24. If it differs, check the files and import results before continuing.

2. Create a procedure ¶

Create a procedure to implement the Infomap algorithm. For more information about the procedure, see Procedure implementation.

'''
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. Call your procedure ¶

Find communities and return the module ID assigned to each node.

USE #infomap_graph CALL infomap() RETURN vertex_id, module_id

Returns:

Expand to view results

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

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.

Infomap¶

Algorithm introduction¶

Data model¶

Procedure implementation¶

Steps¶

1. Prepare graph data¶

2. Create a procedure¶

3. Call your procedure¶

Procedure implementation ¶

1. Prepare graph data ¶

2. Create a procedure ¶

3. Call your procedure ¶