Skip to content
Blog

Louvain

The Louvain algorithm extracts communities from large networks by maximizing their modularity score, where the modularity measures the relative density of edges inside communities as compared to edges outside communities. A higher modularity theoretically represents a better grouping of the nodes into communities.

The Louvain algorithm is a hierarchical clustering algorithm that runs in phases. In each phase, the nodes start in their own community and the algorithm attempts to iteratively group nodes into the same community until the modularity of the graph becomes stable. Nodes within the same community are then merged into supernodes for the next phase. Phases run until the number of communities become stable.

Kuzu implements a parallelized version of the Louvain algorithm based on Grappolo.

Syntax

CALL louvain(
graph_name,
maxPhases := 20,
maxIterations := 20,
)
RETURN node, louvain_id

Parameters

ParameterTypeOptionalDefaultDescription
graph_nameSTRINGNo-Name of the projected graph to run the algorithm on
maxPhasesINT64Yes20Maximum number of phases to run
maxIterationsINT64Yes20Maximum number of iterations to run in each phase

Return

ColumnTypeDescription
nodeNODENode object
louvain_idINT64The louvain community ID that the node belongs to

Example

Define schema

CREATE NODE TABLE Node(id STRING PRIMARY KEY);
CREATE REL TABLE Edge(FROM Node to Node);

Insert nodes and edges

CREATE (u0:Node {id: 'A'}),
(u1:Node {id: 'B'}),
(u2:Node {id: 'C'}),
(u3:Node {id: 'D'}),
(u4:Node {id: 'E'}),
(u5:Node {id: 'F'}),
(u6:Node {id: 'G'}),
(u7:Node {id: 'H'}),
(u0)-[:Edge]->(u1),
(u0)-[:Edge]->(u2),
(u1)-[:Edge]->(u2),
(u0)-[:Edge]->(u3),
(u1)-[:Edge]->(u3),
(u2)-[:Edge]->(u3),
(u4)-[:Edge]->(u5),
(u4)-[:Edge]->(u6),
(u5)-[:Edge]->(u6),
(u4)-[:Edge]->(u7),
(u5)-[:Edge]->(u7),
(u6)-[:Edge]->(u7),
(u3)-[:Edge]->(u4);

We’ll first create a projected graph from the node and edge tables.

CALL project_graph('Graph', ['Node'], ['Edge']);

Run the Louvain algorithm on the projected graph as follows:

CALL louvain('Graph') RETURN louvain_id, collect(node.id);
┌────────────┬──────────────────┐
│ louvain_id │ COLLECT(node.id) │
│ INT64 │ STRING[] │
├────────────┼──────────────────┤
│ 0 │ [D,C,B,A] │
│ 1 │ [E,G,H,F] │
└────────────┴──────────────────┘