Community Detection

algo.wcc

Property Value

Procedure

algo.wcc

Category

Community Detection

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.wcc([relTypes])
YIELD node, componentId

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

componentId

Integer

Sequential component identifier (0-based)

Description

Identifies weakly connected components using BFS, treating all edges as undirected regardless of their actual direction. Two vertices are in the same component if there exists any undirected path between them. Component IDs are remapped to sequential integers starting at 0.

Use Cases

  • Data quality: detecting isolated subgraphs

  • Network partition detection

  • Graph reachability analysis

Example

CALL algo.wcc('CONNECTED_TO')
YIELD node, componentId
RETURN componentId, count(node) AS size ORDER BY size DESC

References

algo.scc

Property Value

Procedure

algo.scc

Category

Community Detection

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.scc([relTypes])
YIELD node, componentId

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

componentId

Integer

Sequential component identifier (0-based)

Description

Identifies strongly connected components using Kosaraju’s two-pass algorithm: iterative DFS on the original graph to compute finish-time ordering, then BFS on the reversed graph in reverse finish order. A strongly connected component is a maximal set of vertices where every vertex is reachable from every other.

Use Cases

  • Deadlock detection in dependency graphs

  • Circular dependency analysis in software systems

  • Identifying mutually-reachable clusters in directed networks

Example

CALL algo.scc('DEPENDS_ON')
YIELD node, componentId
RETURN componentId, collect(node) AS members ORDER BY size(members) DESC

References

algo.louvain

Property Value

Procedure

algo.louvain

Category

Community Detection

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.louvain([{maxIterations: 10, tolerance: 0.0001, weightProperty: null}])
YIELD node, communityId, modularity

Parameters

Parameter Type Required Default Description

config map

Map

No

see defaults

Configuration properties (all optional)

maxIterations

Integer

No

10

Maximum number of phase-1 passes

tolerance

Double

No

0.0001

Stop when modularity gain falls below this value

weightProperty

String

No

null

Edge property for weighted modularity

Yield Fields

Field Type Description

node

RID

Vertex identity

communityId

Integer

Sequential community identifier (0-based)

modularity

Double

Final modularity score of the partition

Description

Detects communities by maximizing modularity using the Louvain method: a greedy phase where each node is moved to the neighboring community that maximally increases modularity, iterated until no improvement is found. Community IDs are remapped to sequential 0-based integers.

Use Cases

  • Social community discovery

  • Topic clustering in citation networks

  • Customer segmentation in purchase graphs

Example

CALL algo.louvain({maxIterations: 15, weightProperty: 'weight'})
YIELD node, communityId, modularity
RETURN communityId, collect(node) AS members, modularity ORDER BY size(members) DESC

References

algo.leiden

Property Value

Procedure

algo.leiden

Category

Community Detection

Complexity

CPU

Min Args

0

Max Args

3

Syntax

CALL algo.leiden([relTypes, maxIterations, resolution])
YIELD nodeId, community

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

maxIterations

Integer

No

10

Maximum number of local-move + refinement iterations

resolution

Double

No

1.0

Resolution parameter γ (higher = more, smaller communities)

Yield Fields

Field Type Description

nodeId

RID

Vertex identity

community

Integer

Sequential community identifier (0-based)

Description

An improved community detection algorithm over Louvain, featuring a two-phase approach: (1) local greedy moves maximizing modularity, followed by (2) a refinement phase that checks whether nodes should be split out from their community to ensure well-connectedness. The resolution parameter γ controls granularity of the resulting communities.

Use Cases

  • High-quality community detection with guaranteed well-connectedness

  • Hierarchical community structure analysis

  • Fine-grained cluster control via resolution parameter

Example

CALL algo.leiden('KNOWS', 10, 1.0)
YIELD nodeId, community
RETURN community, count(nodeId) AS size ORDER BY size DESC

References

  • Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9, 5233.

algo.labelpropagation

Property Value

Procedure

algo.labelpropagation

Category

Community Detection

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.labelpropagation([{maxIterations: 10, direction: 'BOTH'}])
YIELD node, communityId

Parameters

Parameter Type Required Default Description

config map

Map

No

see defaults

Configuration properties (all optional)

maxIterations

Integer

No

10

Maximum number of propagation passes

direction

String

No

"BOTH"

Edge direction to follow: "IN", "OUT", or "BOTH"

Yield Fields

Field Type Description

node

RID

Vertex identity

communityId

Integer

Community label assigned to this vertex

Description

Detects communities by iteratively propagating labels. Each vertex adopts the most frequent label among its neighbors; ties are broken by choosing the smallest label. Vertex processing order is randomly shuffled each iteration. Converges quickly in practice but may produce non-deterministic results.

Use Cases

  • Fast community detection in very large graphs

  • Semi-supervised classification when some labels are pre-assigned

  • Near-linear time community discovery

Example

CALL algo.labelpropagation({maxIterations: 20, direction: 'OUT'})
YIELD node, communityId
RETURN communityId, count(node) AS size ORDER BY size DESC

References

algo.hierarchicalClustering

Property Value

Procedure

algo.hierarchicalClustering

Category

Community Detection

Complexity

CPU+RAM

Min Args

0

Max Args

2

Syntax

CALL algo.hierarchicalClustering([relTypes, numClusters])
YIELD nodeId, cluster

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

numClusters

Integer

No

2

Desired number of clusters

Yield Fields

Field Type Description

nodeId

RID

Vertex identity

cluster

Integer

Assigned cluster identifier

Description

Performs agglomerative (bottom-up) hierarchical clustering using single-linkage: each vertex starts in its own cluster, and the two clusters with the highest Jaccard similarity between their neighbor sets are merged iteratively until the target number of clusters is reached. Uses Union-Find for efficient cluster management.

Use Cases

  • Dendrogram-style cluster analysis

  • Grouping vertices by structural neighborhood similarity

  • Coarse-grained community assignment with controlled count

Example

CALL algo.hierarchicalClustering('SIMILAR_TO', 5)
YIELD nodeId, cluster
RETURN cluster, count(nodeId) AS size ORDER BY size DESC

References

algo.slpa

Property Value

Procedure

algo.slpa

Category

Community Detection

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.slpa([config]) YIELD node, communities

Parameters

Name Type Default Description

config

Map

{}

Configuration map (see below)

Config Parameters

Key Type Default Description

iterations

Integer

20

Number of propagation iterations (T)

threshold

Float

0.1

Minimum label frequency in memory to be included in output

seed

Long

-1

Random seed for reproducibility; -1 uses a random seed

Yield Fields

Field Type Description

node

Vertex

The vertex

communities

List<Long>

List of community IDs the vertex belongs to (overlapping)

Description

SLPA (Speaker-Listener Label Propagation Algorithm) detects overlapping communities. Each node maintains a memory of labels it has received over T iterations. In each iteration every node acts as a speaker (emitting its most frequent memory label) and a listener (recording the most common label from its neighbours). After T rounds, labels appearing with frequency ≥ threshold are retained as community assignments.

Unlike non-overlapping algorithms (Louvain, Label Propagation), SLPA allows each vertex to belong to multiple communities simultaneously, making it suitable for social networks where individuals naturally participate in multiple groups.

Use Cases

  • Overlapping community detection in social networks

  • Finding cross-cutting roles in collaboration networks

  • Identifying nodes that bridge multiple communities

Example

CALL algo.slpa({iterations: 20, threshold: 0.1, seed: 42})
YIELD node, communities
RETURN node.name AS name, communities
ORDER BY size(communities) DESC

References

algo.maxKCut

Property Value

Procedure

algo.maxKCut

Category

Community Detection

Complexity

CPU

Min Args

1

Max Args

2

Syntax

CALL algo.maxKCut(k [, config]) YIELD node, community, cutWeight

Parameters

Name Type Default Description

k

Integer

—

Number of partitions (≥ 2)

config

Map

{}

Configuration map (see below)

Config Parameters

Key Type Default Description

maxIterations

Integer

100

Maximum local-search passes per restart

restarts

Integer

3

Number of random restarts (best result returned)

weightProperty

String

null

Edge property for weights; null = all weights 1.0

relTypes

String

all types

Comma-separated edge type names

direction

String

BOTH

Edge traversal direction: IN, OUT, or BOTH

seed

Long

-1

Random seed; -1 = random

Yield Fields

Field Type Description

node

Vertex

The vertex

community

Integer

Partition index in range [0, k − 1]

cutWeight

Float

Total weight of inter-partition edges (same on every row)

Description

Approximates the Maximum k-Cut problem: partition all vertices into k disjoint subsets to maximise the total weight of edges that cross between different partitions. Uses a greedy local-search heuristic:

  1. Randomly assign each vertex to one of k partitions.

  2. For each vertex, compute the cut gain for every possible partition and move it to the best one.

  3. Repeat until no vertex can be moved to improve the cut (or maxIterations is reached).

  4. Repeat steps 1–3 for restarts independent runs and return the best result found.

This heuristic achieves a (k−1)/k fraction of the optimal cut on unweighted graphs and converges quickly in practice.

Use Cases

  • Graph partitioning for parallel processing

  • Community detection via balanced cut

  • Circuit bipartitioning and VLSI placement

Example

CALL algo.maxKCut(3, {restarts: 5, seed: 42})
YIELD node, community, cutWeight
RETURN node.name AS name, community
ORDER BY community

References