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

Parameter	Type	Optional	Default	Description
graph_name	STRING	No	-	Name of the projected graph to run the algorithm on
maxPhases	INT64	Yes	20	Maximum number of phases to run
maxIterations	INT64	Yes	20	Maximum number of iterations to run in each phase

Return

Column	Type	Description
node	NODE	Node object
louvain_id	INT64	The louvain community ID that the node belongs to

Example

Define schema

CREATE NODE TABLE Person(name STRING PRIMARY KEY);
CREATE REL TABLE KNOWS(FROM Person to Person);

Insert nodes and edges

CREATE (u0:Person {name: 'Alice'}),
        (u1:Person {name: 'Bob'}),
        (u2:Person {name: 'Charlie'}),
        (u3:Person {name: 'Derek'}),
        (u4:Person {name: 'Eve'}),
        (u5:Person {name: 'Frank'}),
        (u6:Person {name: 'George'}),
        (u7:Person {name: 'Hina'}),
        (u0)-[:KNOWS]->(u1),
        (u0)-[:KNOWS]->(u2),
        (u1)-[:KNOWS]->(u2),
        (u0)-[:KNOWS]->(u3),
        (u1)-[:KNOWS]->(u3),
        (u2)-[:KNOWS]->(u3),
        (u4)-[:KNOWS]->(u5),
        (u4)-[:KNOWS]->(u6),
        (u5)-[:KNOWS]->(u6),
        (u4)-[:KNOWS]->(u7),
        (u5)-[:KNOWS]->(u7),
        (u6)-[:KNOWS]->(u7),
        (u3)-[:KNOWS]->(u4);

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

CALL project_graph('Graph', ['Person'], ['KNOWS']);

Run the Louvain algorithm on the projected graph as follows:

CALL louvain('Graph')
RETURN louvain_id, collect(node.name)
ORDER BY louvain_id;

┌────────────┬───────────────────────────┐
│ louvain_id │ COLLECT(node.name)        │
│ INT64      │ STRING[]                  │
├────────────┼───────────────────────────┤
│ 0          │ [Derek,Charlie,Bob,Alice] │
│ 1          │ [Eve,George,Hina,Frank]   │
└────────────┴───────────────────────────┘