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)

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;

Further Reading

• Introduction to GraphRAG — Combine graph algorithms with retrieval-augmented generation
• Neo4j AI: Building Intelligent Applications — Production Neo4j patterns
• Graph Theory 101 — The mathematical foundations
• 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.