Structural Analysis

algo.kcore

Property Value

Procedure

algo.kcore

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.kcore([relTypes])
YIELD node, coreNumber

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

coreNumber

Integer

Maximum k for which this vertex belongs to a k-core

Description

Computes the k-core decomposition of the graph using the Batagelj-Zaversnik O(V+E) algorithm with bucket sort. The k-core of a graph is the maximal subgraph in which every vertex has at least degree k. Each vertex is assigned its coreness: the maximum k for which it belongs to a k-core.

Use Cases

  • Identifying dense graph cores and peripheral nodes

  • Network robustness analysis

  • Cohesive subgroup detection

Example

CALL algo.kcore('KNOWS')
YIELD node, coreNumber
RETURN node, coreNumber ORDER BY coreNumber DESC LIMIT 20

References

  • Batagelj, V. & Zaversnik, M. (2003). An O(m) Algorithm for Cores Decomposition of Networks. arXiv:cs/0310049.

algo.triangleCount

Property Value

Procedure

algo.triangleCount

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.triangleCount([relTypes])
YIELD node, triangles, clusteringCoefficient

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

triangles

Integer

Number of triangles the vertex participates in

clusteringCoefficient

Double

Local clustering coefficient

Description

Counts the number of closed triangles for each vertex using BitSet intersection of neighbor sets (minimal GC pressure). The local clustering coefficient is computed as 2 × triangles / (deg × (deg-1)), measuring how close the vertex’s neighbors are to forming a complete subgraph.

Use Cases

  • Social network cohesiveness analysis

  • Spam detection (low clustering = suspicious accounts)

  • Community structure pre-screening

Example

CALL algo.triangleCount('KNOWS')
YIELD node, triangles, clusteringCoefficient
RETURN node, triangles, clusteringCoefficient ORDER BY triangles DESC LIMIT 20

References

algo.articulationPoints

Property Value

Procedure

algo.articulationPoints

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.articulationPoints([relTypes])
YIELD node

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity of an articulation point

Description

Finds all articulation points (cut vertices) — vertices whose removal would increase the number of connected components — using Tarjan’s iterative DFS algorithm with discovery time and low-link arrays. Only vertices identified as articulation points are returned; all other vertices produce no result rows.

Use Cases

  • Network resilience analysis: single points of failure

  • Critical infrastructure node identification

  • Dependency chain vulnerability assessment

Example

CALL algo.articulationPoints('CONNECTED_TO')
YIELD node
RETURN node

References

algo.bridges

Property Value

Procedure

algo.bridges

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.bridges([relTypes])
YIELD source, target

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

source

RID

Source vertex of the bridge edge

target

RID

Target vertex of the bridge edge

Description

Finds all bridge edges — edges whose removal would disconnect the graph — using Tarjan’s iterative DFS. A bridge is detected when the low-link value of the child strictly exceeds the discovery time of the parent: low[v] > disc[parent]. Uses OUT-direction adjacency for DFS traversal.

Use Cases

  • Network resilience: critical links whose failure causes disconnection

  • Infrastructure planning: bottleneck link identification

  • Supply chain single-path dependency detection

Example

CALL algo.bridges('LINK')
YIELD source, target
RETURN source, target

References

algo.mst

Property Value

Procedure

algo.mst

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

2

Syntax

CALL algo.mst([weightProperty, relTypes])
YIELD source, target, weight, totalWeight

Parameters

Parameter Type Required Default Description

weightProperty

String

No

uniform weight

Edge property name for weights

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

source

RID

Source vertex of the MST edge

target

RID

Target vertex of the MST edge

weight

Double

Weight of this MST edge

totalWeight

Double

Total weight of the entire MST (same on every row)

Description

Computes the minimum spanning tree of the graph using Kruskal’s algorithm with a Union-Find data structure (path halving + union by rank). Edges are sorted by weight; each edge is added if it connects two different components. For disconnected graphs, a minimum spanning forest is returned.

Use Cases

  • Network infrastructure with minimal cost

  • Clustering by minimal connectivity

  • Dendrogram construction for hierarchical analysis

Example

CALL algo.mst('cost', 'CABLE')
YIELD source, target, weight, totalWeight
RETURN source, target, weight, totalWeight ORDER BY weight ASC

References

algo.topologicalSort

Property Value

Procedure

algo.topologicalSort

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.topologicalSort([relTypes])
YIELD node, order

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

order

Integer

Topological position (0-based); -1 if the node is part of a cycle

Description

Computes a topological ordering of the vertices of a directed acyclic graph (DAG) using Kahn’s BFS algorithm. Nodes in cycles cannot be topologically sorted and receive order = -1. The algorithm processes nodes with zero in-degree first, progressively reducing in-degrees of successors.

Use Cases

  • Build system dependency resolution

  • Task scheduling with ordering constraints

  • Compilation order determination

Example

CALL algo.topologicalSort('DEPENDS_ON')
YIELD node, order
RETURN node, order ORDER BY order ASC

References

algo.bipartite

Property Value

Procedure

algo.bipartite

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.bipartite([relTypes])
YIELD node, partition, isBipartite

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

partition

Integer

Partition assignment: 0 or 1

isBipartite

Boolean

Global flag: true if the graph is bipartite

Description

Tests whether the graph is bipartite by attempting 2-coloring via BFS. A graph is bipartite if and only if it contains no odd-length cycles. The algorithm correctly handles disconnected graphs by running BFS from each unvisited component. All rows share the same isBipartite value.

Use Cases

  • Verifying bipartite structure before applying bipartite-specific algorithms

  • Recommendation system graph validation (users ↔ items)

  • Conflict-free scheduling verification

Example

CALL algo.bipartite('CONNECTS')
YIELD node, partition, isBipartite
RETURN isBipartite, partition, collect(node) AS members

References

algo.graphColoring

Property Value

Procedure

algo.graphColoring

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.graphColoring([relTypes])
YIELD node, color, chromaticNumber

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

color

Integer

Assigned color (0-based integer)

chromaticNumber

Integer

Global chromatic number of the coloring (same on every row)

Description

Assigns colors to vertices such that no two adjacent vertices share the same color, using a greedy algorithm with a forbidden[] array to track unavailable colors for each vertex. The result is a valid coloring but not guaranteed to use the minimum number of colors (the chromatic number). The greedy approach works well in practice for most graph types.

Use Cases

  • Exam/exam-room scheduling (students sharing courses cannot share a room)

  • Frequency assignment in radio networks

  • Register allocation in compilers

Example

CALL algo.graphColoring('CONFLICTS_WITH')
YIELD node, color, chromaticNumber
RETURN chromaticNumber, color, collect(node) AS group

References

algo.cycleDetection

Property Value

Procedure

algo.cycleDetection

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.cycleDetection([relTypes])
YIELD node, inCycle, hasCycle

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

inCycle

Boolean

true if the vertex is part of a cycle

hasCycle

Boolean

Global flag: true if the graph contains any cycle

Description

Detects cycles using Kosaraju’s SCC algorithm. A vertex is considered to be in a cycle if it belongs to an SCC of size greater than 1, or if it has a self-loop. The global hasCycle flag is true if any vertex satisfies this condition.

Use Cases

  • Dependency graph cycle detection (circular dependencies)

  • Deadlock possibility analysis

  • DAG validation before topological sort

Example

CALL algo.cycleDetection('DEPENDS_ON')
YIELD node, inCycle, hasCycle
RETURN hasCycle, node, inCycle

References

algo.densestSubgraph

Property Value

Procedure

algo.densestSubgraph

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.densestSubgraph([relTypes])
YIELD node, inDenseSubgraph, density

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

node

RID

Vertex identity

inDenseSubgraph

Boolean

true if the vertex is part of the densest subgraph found

density

Double

Edge density of the densest subgraph (same on every row)

Description

Finds the densest subgraph using Charikar’s greedy peeling 2-approximation algorithm. The algorithm iteratively removes the vertex with the lowest current degree, tracking the density (edges / nodes) of the remaining subgraph. The subgraph that achieved the maximum density is returned.

Use Cases

  • Identifying tightly-knit communities in social networks

  • Quasi-clique detection

  • Anomaly detection: unusually dense subgraphs

Example

CALL algo.densestSubgraph('KNOWS')
YIELD node, inDenseSubgraph, density
RETURN density, node, inDenseSubgraph ORDER BY inDenseSubgraph DESC

References

  • Charikar, M. (2000). Greedy approximation algorithms for finding dense components in a graph. APPROX 2000.

algo.clique

Property Value

Procedure

algo.clique

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

2

Syntax

CALL algo.clique([relTypes, minSize])
YIELD clique, size

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

minSize

Integer

No

3

Minimum clique size to report

Yield Fields

Field Type Description

clique

List<RID>

List of vertex identities forming the clique

size

Integer

Number of vertices in the clique

Description

Enumerates all maximal cliques in the graph using the Bron-Kerbosch algorithm with Tomita pivoting, implemented iteratively with an explicit stack to avoid JVM stack overflow on deep recursion. The graph is treated as undirected (both OUT and IN edges merged). Only cliques of size ≥ minSize are returned.

Use Cases

  • Finding tightly connected groups (friend circles, co-author clusters)

  • Network motif analysis

  • Dense community detection

Example

CALL algo.clique('KNOWS', 4)
YIELD clique, size
RETURN size, clique ORDER BY size DESC LIMIT 10

References

algo.kTruss

Property Value

Procedure

algo.kTruss

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

2

Syntax

CALL algo.kTruss([relTypes, k])
YIELD nodeId, trussNumber

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types

k

Integer

No

3

Target truss parameter (minimum 3)

Yield Fields

Field Type Description

nodeId

RID

Vertex identity

trussNumber

Integer

Maximum k for which this vertex belongs to a k-truss

Description

Computes the k-truss decomposition using BitSet-based triangle counting. A k-truss is a maximal subgraph where every edge participates in at least k−2 triangles. The algorithm iteratively removes edges with insufficient triangle support, and each vertex is assigned the maximum truss number of any of its incident edges in the full decomposition.

Use Cases

  • Dense subgraph discovery beyond k-cores

  • Social cohesion analysis (friend of a friend structures)

  • Financial fraud ring detection

Example

CALL algo.kTruss('KNOWS', 4)
YIELD nodeId, trussNumber
RETURN nodeId, trussNumber ORDER BY trussNumber DESC LIMIT 20

References

  • Cohen, J. (2008). Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report.

algo.biconnectedComponents

Property Value

Procedure

algo.biconnectedComponents

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

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

Parameters

Name Type Default Description

relTypes

String

all types

Comma-separated edge type names to traverse

Yield Fields

Field Type Description

node

Vertex

The vertex

componentId

Integer

Biconnected component identifier

Description

Computes biconnected components using an iterative variant of Tarjan’s algorithm with an explicit edge stack. A biconnected component is a maximal subgraph with no articulation point — removing any single vertex leaves the component connected. Articulation points (cut vertices) appear in multiple components because they belong to each component on either side of the cut.

The algorithm uses undirected traversal regardless of the edge direction parameter.

Use Cases

  • Network resilience analysis (identifying single points of failure)

  • Circuit board layout and VLSI design

  • Social network structural analysis

Example

CALL algo.biconnectedComponents('ROAD')
YIELD node, componentId
RETURN componentId, collect(node.name) AS members
ORDER BY size(members) DESC

References

algo.localClusteringCoefficient

Property Value

Procedure

algo.localClusteringCoefficient

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.localClusteringCoefficient([relTypes]) YIELD node, localClusteringCoefficient

Parameters

Name Type Default Description

relTypes

String

all types

Comma-separated edge type names to traverse (treated as undirected)

Yield Fields

Field Type Description

node

Vertex

The vertex

localClusteringCoefficient

Float

LCC value in range [0.0, 1.0]

Description

Computes the Local Clustering Coefficient (LCC) for every vertex. The LCC of a node v is the fraction of pairs of neighbours of v that are themselves connected: LCC(v) = triangles(v) / (k*(k-1)/2) where k is the degree of v. Nodes with degree < 2 receive a coefficient of 0.0. Triangle counting is performed with a BitSet intersection, making it efficient even for dense graphs.

Use Cases

  • Identifying tightly-knit communities and cliques

  • Detecting community structure (nodes with high LCC are embedded in local clusters)

  • Social network cohesion analysis

Example

CALL algo.localClusteringCoefficient('KNOWS')
YIELD node, localClusteringCoefficient
RETURN node.name AS name, localClusteringCoefficient
ORDER BY localClusteringCoefficient DESC LIMIT 20

References

algo.bipartiteMatching

Property Value

Procedure

algo.bipartiteMatching

Category

Structural Analysis

Complexity

CPU

Min Args

0

Max Args

1

Syntax

CALL algo.bipartiteMatching([relTypes]) YIELD node1, node2, matchingSize

Parameters

Name Type Default Description

relTypes

String

all types

Comma-separated edge type names defining the bipartite graph

Yield Fields

Field Type Description

node1

Vertex

Left-side matched vertex

node2

Vertex

Right-side matched vertex

matchingSize

Integer

Total number of matched pairs (same in every row)

Description

Computes a maximum bipartite matching using the Hopcroft-Karp algorithm (O(E√V)). The graph is treated as bipartite: nodes with only outgoing edges are on the left side; nodes with only incoming edges are on the right side. Each output row represents one matched pair. The algorithm finds augmenting paths via BFS (layered graph construction) followed by DFS, maximising the number of matched pairs in O(E√V) time.

Note: The procedure assumes the input graph is already bipartite. Results are undefined for non-bipartite inputs.

Use Cases

  • Task-worker assignment optimisation

  • Resource allocation (jobs to machines)

  • Stable marriage / hospital-resident matching

  • Recommendation filtering

Example

CALL algo.bipartiteMatching('ASSIGNED_TO')
YIELD node1, node2, matchingSize
RETURN node1.name AS worker, node2.name AS task, matchingSize

References