Graph Algorithms with Neo4j: Shortest Path, Centrality, and Community Detection

Why Graph Algorithms Matter

A graph database stores relationships natively, but the real power comes from analysing those relationships. A friend-of-a-friend query is useful; finding the most influential node in a network of ten thousand users is transformative.

Graph algorithms unlock insights that SQL window functions and recursive CTEs can only approximate. Whether you are ranking web pages, detecting fraud rings, optimising delivery routes, or finding research communities, the same core algorithms apply — and Neo4j ships a production-grade framework for running them at scale: the Graph Data Science (GDS) library.

This article covers the three families of graph algorithms you will reach for most often — pathfinding, centrality, and community detection — with concrete Cypher and GDS examples you can run today.

Prerequisites: GDS and Graph Projections

Before running algorithms, you need the GDS library installed. Neo4j Desktop and Neo4j Aura include it by default. For self-managed instances:

# Download and place the GDS jar in the plugins directory
curl -L -o /var/lib/neo4j/plugins/neo4j-gds.jar \
  https://github.com/neo4j/graph-data-science/releases/latest/download/neo4j-gds-2.14.0.jar

GDS operates on in-memory graph projections — a snapshot of your labelled subgraph loaded into memory with a specific topology. You create one with gds.graph.project:

CALL gds.graph.project(
  'myGraph',
  ['Person', 'Company'],          // Node labels
  ['KNOWS', 'WORKS_AT', 'INVESTED_IN']  // Relationship types
);

Once projected, you can run any algorithm against it. When you are done, drop it:

CALL gds.graph.drop('myGraph');

Pathfinding: Getting from A to B

Pathfinding algorithms answer the most natural graph question: how do I get from this node to that node?

Shortest Path (BFS)

The simplest pathfinder — breadth-first search — finds the path with the fewest hops (edges), ignoring edge weights:

MATCH (a:Person {name: 'Alice'}), (b:Person {name: 'Bob'})
CALL gds.shortestPath.bfs.stream('myGraph', {
  sourceNode: id(a),
  targetNode: id(b)
})
YIELD nodeIds, path
RETURN [node IN nodes(path) | node.name] AS route

Use BFS when every edge has equal cost — social network hops, organisational reporting lines, network topologies.

Weighted Shortest Path (Dijkstra)

When edges carry different costs (distance, time, monetary value), Dijkstra's algorithm finds the cheapest path:

MATCH (a:Warehouse {name: 'Berlin'}), (b:Warehouse {name: 'Munich'})
CALL gds.shortestPath.dijkstra.stream('shipmentGraph', {
  sourceNode: id(a),
  targetNode: id(b),
  relationshipWeightProperty: 'cost_eur'
})
YIELD nodeIds, totalCost, path
RETURN [node IN nodes(path) | node.name] AS route, totalCost

Dijkstra has one limitation: it cannot handle negative edge weights. For graphs with negative costs (rare in practice but possible), use the Bellman-Ford variant via gds.shortestPath.bellmanFord.stream.

All Pairs and Single Source Shortest Path

For global analysis — how far is every warehouse from every other warehouse? — run the delta-stepping algorithm, which parallelises well on large graphs:

CALL gds.allPairs.shortestPath.stream('shipmentGraph', {
  relationshipWeightProperty: 'cost_eur'
})
YIELD sourceNode, targetNode, distance
RETURN gds.util.asNode(sourceNode).name AS source,
       gds.util.asNode(targetNode).name AS target,
       distance
ORDER BY distance DESC
LIMIT 10;

Algorithm	Best When	Edge Weights	Complexity
BFS	Fewest hops	Unweighted	O(V + E)
Dijkstra	Cheapest path	Non-negative	O(E + V log V)
Delta-Stepping	All-pairs / large graphs	Non-negative	O(E + V log V) — parallel
Bellman-Ford	Graphs with negative edges	Any	O(V × E)

Yen's k-Shortest Paths

One shortest path is often not enough in production. A logistics platform needs alternatives — the fastest route, the cheapest route, and a fallback that avoids toll roads. Yen's algorithm extends Dijkstra to return the top k distinct paths:

MATCH (a:Warehouse {name: 'Berlin'}), (b:Warehouse {name: 'Munich'})
CALL gds.shortestPath.yens.stream('shipmentGraph', {
  sourceNode: id(a),
  targetNode: id(b),
  k: 3,
  relationshipWeightProperty: 'cost_eur'
})
YIELD index, nodeIds, cost
RETURN index,
       [node IN gds.util.asNodes(nodeIds) | node.name] AS route,
       cost

Each successive path is the next-best alternative that shares no more than a configurable overlap with previously found paths. The k parameter controls how many alternatives to produce — each additional path adds roughly the same complexity as a single Dijkstra run.

Production use case: an emergency response system that needs three alternative ambulance routes — fastest, a secondary route avoiding known congestion zones, and a tertiary route with the fewest turns (modelled as a separate edge weight).

A* Shortest Path

When your graph is large and you have geometric coordinates, A* offers a heuristic-guided shortcut. Unlike Dijkstra (which explores equally in all directions), A* uses a distance estimate — typically Euclidean or Manhattan distance — to bias exploration toward the target:

MATCH (a:Station {name: 'King\'s Cross'}), (b:Station {name: 'Paddington'})
CALL gds.shortestPath.astar.stream('transport', {
  sourceNode: id(a),
  targetNode: id(b),
  relationshipWeightProperty: 'minutes',
  latitudeProperty: 'lat',
  longitudeProperty: 'lon'
})
YIELD nodeIds, path
RETURN [node IN nodes(path) | node.name] AS route

A* is particularly effective in geospatial routing (roads, rail, utilities) where Euclidean distance is a good approximation of remaining path cost. In the worst case — a graph with no geometric structure — A* degrades to Dijkstra.

Algorithm	Edge Weight	Heuristic	Best For
Dijkstra	Required	None	General weighted shortest path
Yen's k	Required	None	Top-k alternative routes
A*	Required	Geometric distance	Geospatial routing on large graphs

Centrality: Who Matters Most?

Centrality algorithms rank nodes by importance. The right metric depends entirely on what "importance" means in your domain.

Degree Centrality

The simplest metric: nodes with the most connections win. A person with 500 LinkedIn connections has higher degree centrality than one with 50.

CALL gds.degree.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;

Degree centrality is fast and interpretable but naive — it treats every edge equally. A connection to a nobody counts the same as a connection to the CEO.

PageRank

PageRank improves on degree centrality by weighting incoming edges by the importance of the source. A link from The New York Times is worth more than a link from a personal blog.

CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;

The damping factor (0.85 by convention) models the probability that a random walker continues following edges versus teleporting to a random node. Lower values increase the influence of the graph's global structure; higher values emphasise local connectivity.

Use PageRank for: web pages, academic citations, social media influence, regulatory risk — any domain where being endorsed by influential nodes is meaningful.

Betweenness Centrality

Betweenness measures how often a node lies on the shortest path between every pair of other nodes. A node with high betweenness is a bridge — remove it and the graph fragments.

CALL gds.betweenness.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;

This is the most expensive centrality algorithm — exact computation is O(V × E) for unweighted graphs — but it reveals structural keystones: single points of failure in a network, bottleneck analysts in an organisation, chokepoint routers in a topology.

Closeness Centrality

Closeness measures how quickly a node can reach all others — the average shortest path distance to every other node. High-closeness nodes are optimal broadcast points.

CALL gds.closeness.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;

Algorithm	What It Measures	Complexity	Use Case
Degree	Raw connection count	O(V)	Quick social check
PageRank	Influential endorsements	O(I × (E + V))	Ranking content or people
Betweenness	Bridge / bottleneck	O(V × E) — V² with approximation	Infrastructure resilience
Closeness	Reachability speed	O(V × (E + V log V))	Information diffusion

Community Detection: Finding the Clusters

Community detection algorithms partition the graph into groups where nodes are densely connected internally and sparsely connected externally.

Louvain Modularity

Louvain is the workhorse of community detection — fast, scalable to tens of millions of nodes, and requires no prior knowledge of the number of communities.

CALL gds.louvain.stream('myGraph')
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId;

Each node receives a communityId. Nodes in the same ID are the same community. The algorithm works in two phases: first it optimises modularity locally, then it aggregates the discovered communities into super-nodes and repeats. The intermediateCommunityIds array gives you the hierarchical nesting — useful when communities have sub-communities (teams within departments within organisations).

Label Propagation (LPA)

Label propagation is simpler and faster than Louvain but non-deterministic — repeated runs on the same graph may produce slightly different partitions.

CALL gds.labelPropagation.stream('myGraph', {
  maxIterations: 10
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId;

LPA works by initialising every node with a unique label, then iteratively replacing each node's label with the majority label of its neighbours. It converges quickly (typically 5–10 iterations) and is ideal for initial exploration when you have no prior hypotheses about community structure.

Triangle Counting and Clustering Coefficient

Triangle counting is not a community detection algorithm per se, but it reveals how tightly-knit a neighbourhood is:

CALL gds.triangleCount.stream('myGraph')
YIELD nodeId, triangleCount, coefficient
RETURN gds.util.asNode(nodeId).name AS name,
       triangleCount AS triangles,
       coefficient
ORDER BY coefficient DESC
LIMIT 10;

The clustering coefficient (0 to 1) measures the fraction of a node's neighbours that are also connected to each other. A coefficient near 1 means "my friends all know each other" — a tight clique. Near 0 means "I am the sole connection between disconnected groups" — a structural bridge, which correlates with high betweenness centrality.

Algorithm	Deterministic	Scalability	Needs K	Best For
Louvain	No*	Excellent (millions)	No	Hierarchical communities
Label Propagation	No	Excellent	No	Fast first pass
Triangle Count	Yes	Moderate	No	Measuring local clustering
K-1 Coloring	Yes	Good	Yes	Constraint satisfaction

*GDS offers louvain.seed with a seed property for pseudo-deterministic runs.

Choosing the Right Algorithm

The best algorithm depends on your question:

Question	Algorithm
"What is the cheapest route?"	Dijkstra / A*
"Who is the most influential person?"	PageRank
"Which is the single point of failure?"	Betweenness centrality
"How can I segment users into groups?"	Louvain / Label Propagation
"How tightly connected is this group?"	Triangle count / clustering coefficient
"Which warehouse should serve which store?"	Closeness centrality

Practical Workflow

A production-grade graph algorithm pipeline follows three phases:

1. Project — Create a named, filtered, in-memory graph projection tailored to your question. Include only the labels and relationship types that matter; every irrelevant node slows computation.

2. Mutate — Run algorithms in mutate mode to write results back to the projection as node properties, then inspect distributions, find natural thresholds, and validate assumptions before writing to the live graph.

   CALL gds.pageRank.mutate('myGraph', {
     maxIterations: 20,
     mutateProperty: 'pagerank'
   });
   

3. Write — When you are satisfied, write results to the stored graph for persistent querying and downstream consumption:

   CALL gds.pageRank.write('myGraph', {
     writeProperty: 'pagerank'
   });
   

Once written, you query the results like any other property:

MATCH (p:Person)
WHERE p.pagerank > 0.05
RETURN p.name, p.pagerank
ORDER BY p.pagerank DESC;

Algorithm Output Modes: Stream, Mutate, and Write

Every GDS algorithm supports three output modes, each serving a different stage of the production workflow:

Mode	Behaviour	Use Case
stream	Returns results as Cypher result rows	Exploration, ad-hoc analysis, dashboards
mutate	Stores results in the in-memory projection as a new node property	Chaining algorithms, intermediate results
write	Persists results to the canonical stored graph	Production scores, labels for application queries

The mutate mode is particularly powerful because it lets you chain algorithms: run PageRank, store the score in the projection, then run Louvain weighted by that score — all without leaving the GDS memory space:

CALL gds.pageRank.mutate('myGraph', {
  maxIterations: 20,
  mutateProperty: 'pagerank'
})
YIELD nodePropertiesWritten;

CALL gds.louvain.stream('myGraph', {
  relationshipWeightProperty: 'pagerank'
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId;

Use stream during development to inspect distributions and find natural thresholds. Use mutate when chaining algorithms. Use write only when you are satisfied and need the results in transactional query paths.

Memory Management and Projection Lifecycle

Graph projections live in GDS's dedicated memory space, separate from Neo4j's page cache. A projection that survives beyond its useful life can consume enough memory to degrade transactional performance. Monitor active projections with:

CALL gds.list()
YIELD graphName, nodeCount, relationshipCount, memoryUsage
RETURN *

Always drop projections when they are no longer needed:

CALL gds.graph.drop('myGraph');

For long-running applications, establish a projection lifecycle policy:

1. Create on application startup or on demand
2. Reuse across multiple algorithm runs within a session (project once, run PageRank, Louvain, and WCC against the same projection)
3. Refresh when the underlying data changes beyond a staleness threshold
4. Drop when the session ends or the projection is no longer referenced

Memory estimation is built into every GDS algorithm. Prefix any algorithm call with gds.<algorithm>.estimate to preview costs before execution:

CALL gds.pageRank.estimate('myGraph', {
  maxIterations: 20
})
YIELD requiredMemory, memoryUsage, nodeCount
RETURN requiredMemory, memoryUsage, nodeCount;

This is indispensable in production environments where you need to validate that a projection fits within available heap before committing to a long-running computation.

Incremental Projections with Cypher Filters

For graphs that change frequently — hourly ingestion pipelines, real-time event streams — rebuilding the entire projection from scratch is wasteful. GDS supports Cypher-based projections that let you filter nodes and relationships at projection time:

CALL gds.graph.project.cypher(
  'active-users',
  'MATCH (u:User) WHERE u.lastActive > datetime() - duration("P7D") RETURN id(u) AS id',
  'MATCH (u1:User)-[:FOLLOWS]->(u2:User)
   WHERE u1.lastActive > datetime() - duration("P7D")
   RETURN id(u1) AS source, id(u2) AS target'
);

This limits the projection to users active in the last seven days, keeping memory usage bounded and runtime predictable. The Cypher projection syntax also supports complex aggregations — for example, collapsing multi-hop paths into a single projected relationship for algorithms that only work on direct edges.

When to use incremental projections:

Scenario	Full Projection	Incremental (Cypher)
Data changes hourly	Too expensive	Project only recent data
Dataset >100M nodes	Memory-intensive	Filter to relevant subgraph
Multiple algorithm pipelines	One projection per pipeline	Shared filtered projections
Exploration phase	Quick to set up	Overengineered

Production Checklist

When deploying graph algorithms to production, verify each of these:

• Projection size — estimate memory with gds.<algo>.estimate before running
• Algorithm choice — match the algorithm to the question (see decision table above)
• Output mode — use mutate for intermediate results, write for final persistence
• Projection lifecycle — drop projections after use; monitor with gds.list()
• Incremental updates — use Cypher projections for frequently changing graphs
• Determinism — if reproducibility matters, seed Louvain with louvain.seed or use deterministic algorithms (WCC, Triangle Count)

Further Reading

• Graph Algorithms in Practice with Neo4j — Advanced production patterns including chaining and incremental projections
• Graph Algorithms for Production Neo4j GDS — Deployment patterns for mission-critical graph analytics
• Introduction to GraphRAG — Combine graph algorithms with retrieval-augmented generation
• Neo4j AI: Building Intelligent Applications — Production Neo4j patterns
• Graph Theory 101 — The mathematical foundations
• Community Detection Algorithms — Deep dive into graph clustering techniques
• Neo4j Database Adapters Compared — Choose the right driver for your stack

The official Neo4j GDS Manual is the definitive reference — all algorithms documented with memory estimates, complexity analysis, and examples in both Cypher and Python.