Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/louvain/ Documentation version: v5.3.2 # Louvain Community Detection ## Algorithm introduction Louvain is a community detection algorithm for weighted graphs. Its goal is to partition a graph into communities by maximizing modularity, where internal connections are dense and external connections are sparse. The algorithm starts by assigning each node to its own community, then repeatedly attempts to move nodes to adjacent communities. As long as a move improves the current partition, the algorithm continues. Once the partition at the current layer becomes stable, each community is collapsed into a super-node, and the same process is repeated on the coarsened graph. The final result is a hierarchical community partition together with the community assignment of each original node. ### Overall workflow 1. Initialize statistics for the current layer: 1. Traverse all edges to calculate the total edge weight `m` of the current-layer graph. 2. Calculate the weighted degree of each node, which is the sum of weights of all edges connected to that node. 3. Initialize each node as an independent community. At this point, the node ID is also used as the initial community ID. 2. Perform local moving on the current layer: 1. For each node, accumulate the sum of edge weights from that node to each adjacent community. 2. Using the current community as the baseline, calculate the modularity gain \(\Delta Q\) after moving the node to each candidate adjacent community. 3. Select the move with the highest gain among all candidates. The move is applied only when \(\Delta Q > 0\). 4. In subsequent iterations, update the total weights of the source and target communities after each move. The first iteration exploits the singleton property (each community contains only one node, so the community weight equals the node weight) and uses a simplified formula; after the first iteration completes, `community_weight` is built in bulk. 5. At the end of one iteration, if any node has moved, continue to the next iteration; otherwise, the current layer is considered converged. 3. Build a coarsened graph after the current layer converges: 1. Compress the nodes in the same community into a new community node. 2. Aggregate the edge weights between communities to form weighted edges in the next-layer graph. 3. Keep the mapping from original nodes to the current community for final result backtracking. 4. Repeat the "local moving -> coarsening" process on the coarsened graph: 1. If `max_layer` has not been reached, continue optimization on the coarsened graph. 2. If `max_layer` has been reached, or if no meaningful change occurs in later layers, stop the outer iteration. 5. Output the final community partition: 1. Use the mapping maintained across layers to output the final community of each original node. ### Mathematical formulation The implementation uses this modularity formula: \[ Q(\gamma) = \sum_{c}\left(\frac{e_c}{m} - \gamma \left(\frac{a_c}{2m}\right)^2\right) \] Where: - \(m\) is the total edge weight of the undirected graph. - \(e_c\) is the total internal edge weight of community \(c\). Each undirected edge is counted once. - \(a_c\) is the sum of the weighted degrees of all nodes in community \(c\). - \(\gamma\) is the resolution parameter. A larger \(\gamma\) makes the algorithm prefer smaller communities, while a smaller \(\gamma\) makes it prefer larger communities. The modularity gain used in local moving is: \[ \Delta Q = k_{i \to C_{\text{target}}} - k_{i \to C_{\text{current}}} + \frac{\gamma}{m} \cdot k_i \left( \Sigma_{\text{current}} - \Sigma_{\text{target}} \right) \] Where: - \(k_{i \to C_{\text{target}}}\) is the sum of edge weights from node \(i\) to the target community. - \(k_{i \to C_{\text{current}}}\) is the sum of edge weights from node \(i\) to the current community. - \(k_i\) is the weighted degree of node \(i\). - \(\Sigma_{\text{current}}\) and \(\Sigma_{\text{target}}\) are the total weights of the current and target communities, respectively. - In the notation above, \(\gamma\) is the resolution parameter and \(m\) is the total edge weight. If a candidate community yields a positive \(\Delta Q\), moving the node to that community improves the modularity of the current layer. The implementation selects the candidate move with the highest positive gain as the target for the current iteration. For more information, see [Fast unfolding of communities in large networks](https://arxiv.org/abs/0803.0476). ## Data model To demonstrate Louvain using GQL, the following data model is used: - Persons are represented by `Person` nodes. - Weighted relationships between persons are represented by `KNOWS` edges with a `weight` property. Each `Person` node contains the `id` and `cid` properties. When importing the original graph, use the same CSV field `id` to initialize both properties so that `id = cid`. The `cid` property ensures that the unified inner procedure can access the community-mapping property on both the original graph and the coarsened work graph. The procedure returns the final community assignment without writing it back to the `cid` property in the original graph. To support the outer coarsening iterations, the implementation also creates an internal work graph: - Communities are represented by `community` nodes. - Aggregated edges between communities are represented by `edge` edges with a `weight` property. Note that the semantic meaning of nodes in the internal work graph is different from that in the input graph. In the input graph, `Person` nodes represent business entities, while `community` nodes in the internal work graph represent community graph nodes constructed by the algorithm. In other words, the internal work graph uses nodes to model the coarsened community graph. More specifically, the two fields of a `community` node in the work graph have different meanings: - `id` represents the super-node ID in the current work graph, that is, the community graph node obtained after one coarsening round. - `cid` represents the community ID corresponding to the current record in the mapping chain from the initial nodes to the final communities. During multi-layer iterations, it is used to propagate the assignment of the original nodes to upper-layer communities. Therefore, `edge (community)-[:edge]->(community)` is not a business-level entity relationship edge. It is an aggregated edge between super-nodes, and its two endpoints correspond to nodes in the coarsened community graph rather than original business nodes. For the complete graph type definitions, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/louvain/#prepare_data). ## Procedure implementation To perform community detection on a weighted undirected graph, we define one entry-point procedure and two helper procedures: - `louvain_detect_communities`: The entry point that coordinates the outer iterations. - `louvain_inner_phase`: The unified inner procedure that performs local moving on both the original graph and coarsened graphs. A boolean parameter `is_init` distinguishes the first layer from subsequent layers. - `louvain_load_work_graph`: Loads the coarsened graph output from the previous layer into the work graph. The execution flow among these procedures is shown below. ```` %%{init: {"flowchart": {"nodeSpacing": 30, "rankSpacing": 40}}}%% graph LR Start([Start]) --> Entry{Coordinator:
detect_communities} Entry -->|is_init=true| Inner(Unified inner:
inner_phase) Inner -->|Output| Tables[(Intermediate tables)] Tables -->|Next layer| Load(Coarsening:
load_work_graph) Load -->|is_init=false| Inner Inner -->|Converged/End| End([Output results]) ```` For the complete procedure definitions, see [Create procedures](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/louvain/#create_procedures). The following sections describe the core components of these procedures. The entry-point procedure accepts the following input parameters: - `max_layer`: The maximum number of outer coarsening iterations. - `max_iter`: The maximum number of local-moving iterations within each layer. - `resolution`: The resolution parameter used in the modularity objective. The `louvain_inner_phase` procedure uses a boolean `is_init` to adapt its behavior: - `is_init = true` (first layer): Every node gets a `community_primary_id` after local moving. The node-to-community mapping is direct. - `is_init = false` (subsequent layers): Only active_set nodes (community representatives) have `community_primary_id`; non-representatives are traced via `node2_community_id`. The helper procedures pass results between layers through the following table variables: - `nodes`: Records the mapping from original nodes to the community in the current layer. - `edges`: Records the weighted edges used to build the next coarsened graph. The helper procedures also use the following key variables: | Variable | Type | Description | `total_weight` | Global [SumAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The total edge weight of the current undirected graph. The initial value is `0`. | `community_weight` | Global [MapAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | The sum of weighted degrees for each community, keyed by `community_primary_id`. | `node_weight` | Node-bound [SumAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The weighted degree of each node. The initial value is `0`. | `node_community_weight` | Node-bound [MapAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | The accumulated edge weights from a node to adjacent communities. | `community_id` | Node-bound [SumAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The community ID (stored as `element_id`) currently assigned to the node. The initial value is `0`. | `community_primary_id` | Node-bound [SumAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The primary (representative) node ID of the community. Used as the key for `community_weight`. The initial value is `0`. | `best_move` | Node-bound [TopKAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/topk_agg/) | Stores the best migration candidate sorted by `delta_q`, including `community_id` and `community_primary_id`. | `new_active` | Global [OrAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | Indicates whether any node moved in the current iteration. The initial value is `true`. | `active_set` | [Active set variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | The active node set. In the coarse graph (`is_init = false`), covers only community representatives because only they have edges. | `node2_community_id` | Global [MapAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | Maps original node IDs (`s.id`) to their current `community_primary_id`. Only populated when `is_init = false`. | `community_edge_weight` | Node-bound [MapAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | Stores the aggregated edge weights between communities after convergence, keyed by `community_primary_id`. | `modularity_q` | Global [SumAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The modularity of the current partition. The initial value is `0`. | `community_cnt` | Global [SumAgg aggregate value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | The number of communities in the current layer. The initial value is `0`. | `g` | [Graph variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/graph-variable/) | The temporary work graph used in outer iterations. | `nodes` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Stores the mapping from original nodes to current communities. | `edges` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Stores the weighted edges for the next coarsened graph. The execution flow of the `louvain_inner_phase` procedure is as follows: 1. Initialize graph statistics: calculate `total_weight` and each node's `node_weight`, and build `active_set`. 2. Initialize community assignments: place each node into its own community with `community_id = element_id(s)` and `community_primary_id = s.id`. Do not pre-build `community_weight` at this point, because in the initial singleton state (each community contains only one node), the community weight equals the node weight. 3. Run the local moving iterations within one layer (in two stages): 1. First iteration (singleton optimization, i.e., each community contains only one node): Exploits the property that community weight equals node weight to use a simplified \(\Delta Q\) formula. Uses `s.@community_primary_id` and `t.@community_primary_id` for the resolution term, which both equal the node weights in the singleton case. Does not update `community_weight` during moves. After the iteration completes, `community_weight` is built in bulk keyed by `community_primary_id`. 2. Subsequent iterations (WHILE loop): Uses the standard \(\Delta Q\) formula with `@community_weight.get(community_primary_id)` for community weights. Updates `community_weight` synchronously on each move by subtracting from the old community and adding to the new one. Stops when no node moves or `max_iter` is reached. 4. After the current layer converges, aggregate community-level edges (Section 4). Since `community_id` stores `element_id(s)`, `NODE(s_comm)` can be addressed directly without a `primaryid_2_nodeid` map. 5. When `is_init = false`, build the `node2_community_id` map from node IDs to `community_primary_id` (Section 5). 6. Calculate the modularity of the current partition using `@community_weight.get(s.id)` for `a_c` and `s.@community_edge_weight.get(s.id)` for `e_c` (Section 6). 7. Export two intermediate tables (Section 7): 1. `nodes`: For `is_init = true`, export `cid = s.@community_primary_id` directly. For `is_init = false`, resolve `cid` via `@node2_community_id.get(s.cid)`, falling back to `s.cid` for isolated nodes. 2. `edges`: The aggregated edges required for the next coarsened graph. 8. Repeat the same process on the coarsened graph until `max_layer` is reached. 9. Return the final node-to-community mapping. ## Procedure 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 the graph type for the input graph. ```` ''' CREATE GRAPH TYPE IF NOT EXISTS louvain_demo_gt AS { NODE TYPE Person ( LABEL Person { id INT PRIMARY KEY, cid INT } ), EDGE TYPE KNOWS ( Person )~[LABEL KNOWS { weight DOUBLE, MULTIEDGE KEY () }]~( Person ) } ''' ```` 2. Download these CSV files and save them with their original names in `examples/algorithms/louvain/` under your deployment directory: - [louvain_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/louvain/louvain_node.csv): Node data. - [louvain_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/louvain/louvain_edge.csv): Edge data. The CSV file does not need a separate `cid` column. During import, the `id` column initializes both `Person.id` and `Person.cid`. Preview the CSV files louvain_node.csv ```` id 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ```` louvain_edge.csv ```` src,dst,weight 0,1,4 1,2,4 2,3,4 3,4,4 4,0,4 0,2,3 1,3,3 2,4,3 3,0,3 4,1,3 5,6,4 6,7,4 7,8,4 8,9,4 9,5,4 5,7,3 6,8,3 7,9,3 8,5,3 9,6,3 10,11,4 11,12,4 12,13,4 13,14,4 14,10,4 10,12,3 11,13,3 12,14,3 13,10,3 14,11,3 2,5,1 4,7,1 7,10,1 9,12,1 1,11,1 3,14,1 ```` 3. Create a temporary graph and import the CSV data into it. ```` ''' CREATE TEMPORARY GRAPH IF NOT EXISTS #louvain_demo_g TYPED louvain_demo_gt ''' ```` ```` ''' USE #louvain_demo_g IMPORT INTO GRAPH { NODE (v@Person {id:id, cid:id}) FROM DATAFILE { PATH: "file:///examples/algorithms/louvain/louvain_node.csv", FORMAT: "CSV" }, EDGE (id:src)-[e@KNOWS{weight:weight}]->(id:dst) FROM DATAFILE { PATH: "file:///examples/algorithms/louvain/louvain_edge.csv", FORMAT: "CSV" } } ''' ```` After the import succeeds, run this query in the console to check the node count: ```` ''' USE #louvain_demo_g MATCH (n) RETURN count(n) AS node_count ''' ```` The expected `node_count` is `15`. 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. 4. Create the internal work graph for the outer iterations. ```` ''' CREATE GRAPH TYPE IF NOT EXISTS louvain_work_gt AS { NODE TYPE community ( LABEL community { id INT PRIMARY KEY, cid INT } ), EDGE TYPE edge ( community )~[LABEL edge { weight DOUBLE, MULTIEDGE KEY() }]~( community ) } ''' ```` ### 2. Creating Procedures []() Create all three procedures in this section in order: `louvain_inner_phase`, `louvain_load_work_graph`, and `louvain_detect_communities`. Continue to the calls in the next section after all definitions succeed. #### louvain_inner_phase This unified procedure executes one complete Louvain optimization pass on any graph layer. Controlled by the `is_init` parameter, it handles both the original graph and coarsened work graphs with the same logic, avoiding code duplication. The key difference is how the node-to-community mapping is handled in the export stage. ```` ''' CREATE OR REPLACE PROCEDURE louvain_inner_phase( is_init BOOLEAN, // true = first layer (original graph), false = coarse graph max_iter INT, // Maximum number of local moving iterations resolution DOUBLE, // Resolution parameter (granularity of community partitioning) nodes TABLE, // [Output] Temporary table for node-to-community mapping edges TABLE // [Output] Temporary table for edges in the next coarsened layer ) AS { // ------------------------------------------------------------ // Section 0: Working state and aggregators used by one Louvain layer // is_init = true → first layer (original import graph); every node has // @community_primary_id set after local moving. // is_init = false → subsequent layers (coarse graph); only active_set nodes // (community representatives) have @community_primary_id; // non-representatives are traced via node2_community_id. // node2_community_id is declared unconditionally but only populated when // is_init = false. // ------------------------------------------------------------ VALUE total_weight SumAgg = 0 VALUE community_weight MapAgg> NODE VALUE node_weight SumAgg = 0 NODE VALUE node_community_weight MapAgg> NODE VALUE community_id SumAgg = 0 NODE VALUE community_primary_id SumAgg = 0 NODE VALUE best_move TopKAgg<1, delta_q DOUBLE DESC, community_id INT64 DESC, community_primary_id INT64 DESC> VALUE new_active OrAgg = true VALUE iter = 0 VALUE node2_community_id MapAgg> NODE VALUE community_edge_weight MapAgg> VALUE modularity_q SumAgg = 0 VALUE community_cnt SumAgg = 0 VALUE active_set ACTIVE_SET // ------------------------------------------------------------ // Section 1: Graph statistics initialization // - total_weight: total edge weight m (undirected) // - node_weight: weighted degree of each node // Note: MATCH (s)-[e]-(t) scans each undirected edge twice, so divide by 2. // In the coarse graph (is_init = false) active_set covers only community // representatives because only they have edges. // ------------------------------------------------------------ MATCH (s)-[e]-(t) PER PATH { SET @total_weight += e.weight SET s.@node_weight += e.weight } FINALLY { SET active_set = s } SET @total_weight = @total_weight / 2 LOG_DEBUG("Iter start, total_weight = ", @total_weight) // ------------------------------------------------------------ // Section 2: Initial partition setup // - Start from singleton communities: community_id = element_id(s). // - Defer community_weight materialization until after the first move pass. // ------------------------------------------------------------ MATCH (s) PER NODE (s) { SET s.@community_id = element_id(s) SET s.@community_primary_id = s.id } // ------------------------------------------------------------ // Section 3: Local moving iterations (Louvain core) // Repeatedly move nodes to neighboring communities that improve ΔQ. // Stop when no node moves or max_iter is reached. // ------------------------------------------------------------ IF max_iter > 0 THEN { LOG_DEBUG("--------------- iter == ",iter) SET @new_active = false SET iter = iter + 1 // 3.1 First iteration on singleton communities. // community_weight(c) equals node_weight(c), so we avoid prebuilding the map. MATCH (s)-[e]-(t) WHERE s IN active_set AND s.id <= t.id PER PATH { // In the singleton phase, community_id equals element_id(s). Store each // undirected edge only once on the smaller endpoint and mirror-read it when needed. SET s.@node_community_weight += TUPLE(t.@community_id, e.weight) } MATCH (s)-[e]-(t) WHERE s IN active_set AND ((s.id < t.id AND iter % 2 = 0) OR (s.id > t.id AND iter % 2 = 1)) PER PATH { VALUE edge_to_target DOUBLE = 0.0 VALUE delta DOUBLE = 0.0 IF s.id <= t.id THEN { SET edge_to_target = s.@node_community_weight.get(t.@community_id) } ELSE { SET edge_to_target = t.@node_community_weight.get(s.@community_id) } SET delta = edge_to_target - s.@node_community_weight.get(s.@community_id) + (resolution / @total_weight) * s.@node_weight * (s.@node_weight - t.@node_weight) SET s.@best_move += RECORD { delta_q: delta, community_id: t.@community_id, community_primary_id: t.@community_primary_id } } MATCH (s) WHERE s IN active_set PER NODE (s) { VALUE move_list = s.@best_move IF length(move_list) <> 0 THEN { VALUE move = move_list[0] IF move.delta_q > 0 THEN { SET @new_active += true SET s.@community_id = move.community_id SET s.@community_primary_id = move.community_primary_id } } SET s.@node_community_weight.clear() SET s.@best_move.clear() } MATCH (s) WHERE s IN active_set PER NODE (s) { SET @community_weight += TUPLE(s.@community_primary_id, s.@node_weight) } } ELSE { MATCH (s) WHERE s IN active_set PER NODE (s) { SET @community_weight += TUPLE(s.@community_primary_id, s.@node_weight) } } // 3.2 Later iterations reuse the generic community_weight-based formula. WHILE iter < max_iter AND @new_active THEN { LOG_DEBUG("--------------- iter == ",iter) SET @new_active = false SET iter = iter + 1 // 3.2.1 Accumulate, for each node, total edge weight to each neighbor community. MATCH (s)-[e]-(t) WHERE s IN active_set PER PATH { SET s.@node_community_weight += TUPLE(t.@community_id, e.weight) } // 3.2.2 Build move candidates with modularity gain ΔQ under resolution γ. // Odd/even ordering reduces update conflicts in one pass. MATCH (s)-[e]-(t) WHERE s IN active_set AND ((s.id < t.id AND iter % 2 = 0) OR (s.id > t.id AND iter % 2 = 1)) PER PATH { VALUE delta = s.@node_community_weight.get(t.@community_id) - s.@node_community_weight.get(s.@community_id) + (resolution / @total_weight) * s.@node_weight * (@community_weight.get(s.@community_primary_id) - @community_weight.get(t.@community_primary_id)) SET s.@best_move += RECORD { delta_q: delta, community_id: t.@community_id, community_primary_id: t.@community_primary_id } } // 3.2.3 Apply best positive move per node and refresh related states. MATCH (s) WHERE s IN active_set PER NODE (s) { VALUE move_list = s.@best_move IF length(move_list) <> 0 THEN { VALUE move = move_list[0] IF move.delta_q > 0 THEN { SET @new_active += true SET @community_weight += TUPLE(s.@community_primary_id, -s.@node_weight) SET s.@community_id = move.community_id SET s.@community_primary_id = move.community_primary_id SET @community_weight += TUPLE(s.@community_primary_id, s.@node_weight) } } SET s.@node_community_weight.clear() SET s.@best_move.clear() } } LOG_DEBUG("louvain_inner done, iter = ", iter) // ------------------------------------------------------------ // Section 4: Build coarse inter-community edge weights // Accumulate edge weights between resulting communities for next layer. // For self-loop in input, count half to keep undirected semantics consistent. // community_id stores the representative node element_id directly, so NODE(...) // can be addressed without a primary-id to node-id map. // ------------------------------------------------------------ MATCH (s)-[e]-(t) WHERE s.id <= t.id PER PATH { VALUE s_comm = s.@community_id VALUE t_comm = t.@community_id VALUE s_primary = s.@community_primary_id VALUE t_primary = t.@community_primary_id IF s.id = t.id THEN { SET NODE(s_comm).@community_edge_weight += TUPLE(s_primary, e.weight / 2) } ELSE { IF s_comm = t_comm THEN { SET NODE(s_comm).@community_edge_weight += TUPLE(s_primary, e.weight) } ELSE { SET NODE(s_comm).@community_edge_weight += TUPLE(t_primary, e.weight) } } } // ------------------------------------------------------------ // Section 5: Build node→community mapping // active_set covers only community representatives in the coarse graph // (non-representatives have no edges). This map lets the export step // trace every coarse node to its new community via node2_community_id.get(s.cid). // ------------------------------------------------------------ MATCH (s) WHERE s IN active_set PER NODE (s) { SET @node2_community_id += TUPLE(s.id, s.@community_primary_id) } // ------------------------------------------------------------ // Section 6: Compute modularity Q(γ) for current partition // ------------------------------------------------------------ // Compute modularity Q(γ) = Σ_c [ e_c/m - γ·(a_c/(2m))^2 ] // e_c: total internal edge weight of community c (each undirected edge counted once) // a_c: total degree weight of all nodes in community c (= @community_weight.get(c)) // m: total edge weight (= @total_weight) MATCH (s) WHERE s IN active_set PER NODE (s) { VALUE a_c = @community_weight.get(s.id) VALUE e_c DOUBLE = 0.0 IF s.@community_edge_weight.contains_key(s.id) THEN { SET e_c = s.@community_edge_weight.get(s.id) } IF a_c <> 0 THEN { SET @modularity_q += e_c / @total_weight - resolution * (a_c / (2.0 * @total_weight)) * (a_c / (2.0 * @total_weight)) SET @community_cnt += 1 } } LOG_INFO("louvain modularity Q = ", @modularity_q, ", community_cnt = ", @community_cnt) SET @community_weight.clear() // ------------------------------------------------------------ // Section 7: Export coarse graph and original-node backtracking table // - edges: community-level weighted edges for next outer layer // - nodes: init mode → cid = s.@community_primary_id (direct, all nodes have it) // inner mode → cid = @node2_community_id.get(s.cid) (one-step mapping // so non-representative nodes can track their new community) // ------------------------------------------------------------ MATCH (s) PER NODE (s) { IF is_init THEN { EXPORT s.id AS id, s.@community_primary_id AS cid INTO nodes } ELSE { // The cid of isolated node is id (=cid) itself VALUE key = s.cid VALUE out_cid = key IF @node2_community_id.contains_key(key) THEN { SET out_cid = @node2_community_id.get(key) } EXPORT s.id AS id, out_cid AS cid INTO nodes } IF s.@community_edge_weight.size() <> 0 THEN { VALUE community_edge_weight_list = s.@community_edge_weight VALUE i = 0 VALUE list_size = size(community_edge_weight_list) WHILE (i < list_size) THEN { VALUE r = community_edge_weight_list[i] EXPORT s.id AS src, r._0 AS dst, r._1 AS weight INTO edges SET i = i + 1 } } } } ''' ```` #### louvain_load_work_graph This procedure imports the intermediate `nodes` and `edges` results from the previous layer into the internal work graph, constructing the coarsened community graph used by the next outer iteration. ```` ''' CREATE OR REPLACE PROCEDURE louvain_load_work_graph(nodes TABLE, edges TABLE) AS { IMPORT INTO GRAPH { NODE (v@community {id:id, cid:cid}) FROM nodes, EDGE (id:src) ~[e@edge{weight:weight}]~ (id:dst) FROM edges } OPTIONS {PRIMARY_KEY_AS_NODE_ID:true} } ''' ```` #### louvain_detect_communities This final entry-point procedure coordinates the outer iterations: it calls `louvain_inner_phase` with `is_init = true` on the original graph and `is_init = false` on subsequent work-graph layers, rebuilds the coarsened graph between layers through `louvain_load_work_graph`, and finally returns the mapping from original nodes to final communities. ```` ''' CREATE OR REPLACE PROCEDURE louvain_detect_communities( max_layer INT, // Maximum coarsening layers max_iter INT, // Maximum local-moving iterations per layer resolution DOUBLE // Modularity resolution ) RETURNS (node_id INT, community_id INT) AS { // 1. Initialize the work graph and intermediate tables for cross-layer data handoff GRAPH g TYPED louvain_work_gt TABLE nodes TYPED TABLE {id INT, cid INT} TABLE edges TYPED TABLE {src INT, dst INT, weight DOUBLE} VALUE i = 0 // 2. Start the hierarchical loop WHILE (i < max_layer) THEN { IF (i = 0) THEN { // Layer 0: Run the first partition on the original graph (is_init = true) CALL louvain_inner_phase(true, max_iter, resolution, nodes, edges) FINISH } ELSE { // Layer 1 and later: Continue on the coarsened work graph g (is_init = false) USE g CALL louvain_inner_phase(false, max_iter, resolution, nodes, edges) FINISH } // 3. If the maximum layer has not been reached, rebuild the work graph for the next layer IF (i <> max_layer - 1) THEN { SET g.clear() USE g // Convert the intermediate nodes and edges tables into a new work graph CALL louvain_load_work_graph(nodes, edges) FINISH // Clear the intermediate tables before collecting results for the next layer SET nodes.clear() SET edges.clear() } SET i = i + 1 // Move to the next coarsened layer } // 4. Return the final node-to-community mapping FOR r IN nodes RETURN r.id AS node_id, r.cid AS community_id } ''' ```` ### 3. Calling the entry procedure These calls use at most `6` coarsening levels, at most `6` iterations per level, and resolution `1.0`. Choose the query for the result you want to inspect. - Calculate the total number of communities: ```` ''' USE #louvain_demo_g CALL louvain_detect_communities(6, 6, 1.0) RETURN count(DISTINCT community_id) AS community_cnt ''' ```` Expected result for the sample graph: ```` +---------------+ | community_cnt | +---------------+ | 3 | +---------------+ ```` - View community assignment for each original node: ```` ''' USE #louvain_demo_g CALL louvain_detect_communities(6, 6, 1.0) RETURN node_id, community_id ''' ```` Result: ```` +---------+--------------+ | node_id | community_id | +---------+--------------+ | 0 | 0 | | 1 | 0 | | 2 | 0 | | 3 | 0 | | 4 | 0 | | 5 | 8 | | 6 | 8 | | 7 | 8 | | 8 | 8 | | 9 | 8 | | 10 | 13 | | 11 | 13 | | 12 | 13 | | 13 | 13 | | 14 | 13 | +---------+--------------+ ```` Note The specific values of `community_id` (e.g., 8, 13, 0) depend on internally generated super-node IDs; this is normal as long as nodes in the same community share the same ID.