community_detection

Abstract

This query module makes available the Louvain method ^[1] for community detection, using the Grappolo parallel implementation.

The Louvain algorithm belongs to the modularity maximization family of community detection algorithms. Each node is initially assigned to its own community, and the algorithm uses a greedy heuristic to search for the community partition with the highest modularity score by merging previously obtained communities.

The algorithm is suitable for large-scale graphs as it runs in O(nlogn) time on a graph with n nodes. Further performance gains are obtained by parallelization using a distance-1 graph coloring heuristic, and a graph coarsening algorithm that aims to preserve communities.

¹ Fast unfolding of communities in large networks, Blondel et al.

Trait	Value
Module type	algorithm
Implementation	C++
Graph direction	undirected
Edge weights	weighted / unweighted
Parallelism	parallel

Procedures

get()

Computes graph communities using the Louvain method.

Input

• weight: str(null) ➡ Specifies the default edge weight. If not set, the algorithm uses the weight edge attribute when present and otherwise treats the graph as unweighted.
• coloring: bool(False) ➡ If set, use the graph coloring heuristic for effective parallelization.
• min_graph_shrink: int(100000) ➡ The graph coarsening optimization stops upon shrinking the graph to this many nodes.
• community_alg_threshold: double(0.000001) ➡ Controls how long the algorithm iterates. When the gain in modularity goes below the threshold, iteration is over. Valid values are between 0 and 1 (exclusive).
• coloring_alg_threshold: double(0.01) ➡ If coloring is enabled, controls how long the algorithm iterates. When the gain in modularity goes below this threshold, a final iteration is performed using the community_alg_threshold value. Valid values are between 0 and 1 (exclusive); this parameter's value should be higher than community_alg_threshold.

Output:

• node: Vertex ➡ Graph node.
• community_id: int ➡ Community ID. Defaults to -1 if the node does not belong to any community.

Usage:

CALL community_detection_online.get()
YIELD node, community_id;

Example

Step 1: Input graph

Step 3: Load commands

MERGE (a: Node {id: 0}) MERGE (b: Node {id: 1}) CREATE (a)-[r: Relation]->(b);
MERGE (a: Node {id: 0}) MERGE (b: Node {id: 2}) CREATE (a)-[r: Relation]->(b);
MERGE (a: Node {id: 1}) MERGE (b: Node {id: 2}) CREATE (a)-[r: Relation]->(b);
MERGE (a: Node {id: 2}) MERGE (b: Node {id: 3}) CREATE (a)-[r: Relation]->(b);
MERGE (a: Node {id: 3}) MERGE (b: Node {id: 4}) CREATE (a)-[r: Relation]->(b);
MERGE (a: Node {id: 3}) MERGE (b: Node {id: 5}) CREATE (a)-[r: Relation]->(b);
MERGE (a: Node {id: 4}) MERGE (b: Node {id: 5}) CREATE (a)-[r: Relation]->(b);

Step 4: Running command

CALL community_detection.get()
YIELD node, community_id
RETURN node.id AS node_id, community_id
ORDER BY node_id;

Step 5: Results

┌─────────────────────────┬─────────────────────────┐
│ node_id                 │ community_id            │
├─────────────────────────┼─────────────────────────┤
│ 0                       │ 1                       │
│ 1                       │ 1                       │
│ 2                       │ 1                       │
│ 3                       │ 2                       │
│ 4                       │ 2                       │
│ 5                       │ 2                       │
└─────────────────────────┴─────────────────────────┘