Graph Algorithms in Practice with Neo4j: PageRank, Shortest Path, and Community Detection

Graph theory exists on a spectrum. At one end is the pure mathematics of vertices and edges. At the other end is production telemetry: "which server in this network is most critical?" or "which customers form a coordinated fraud ring?" This article lives at the production end.

The Neo4j Graph Data Science (GDS) library bridges that gap. It exposes a curated set of graph algorithms — centrality, community detection, pathfinding, similarity — as callable procedures that operate entirely within your Neo4j database. No export to a separate analytics cluster. No awkward data pipelines. Your graph stays in the graph, and the algorithm runs against it.

This guide covers three families of algorithms that deliver the most value in production systems: centrality (who matters), community detection (who clusters together), and pathfinding (how things connect).

Setting Up the GDS Library

GDS ships as a plugin for Neo4j. If you are running Neo4j in Docker, installation is a volume mount:

volumes:
  - ./plugins:/plugins
environment:
  NEO4J_dbms_security_procedures_unrestricted: gds.*

Download the JAR matching your Neo4j version from Neo4j download centre and place it in plugins/. Restart Neo4j and verify:

RETURN gds.version()

If you see a version string, you're ready. GDS exposes two tiers of algorithms — those that run natively (in-process, fastest) and those that run estimate (to preview memory cost before execution).

All GDS algorithms follow a consistent lifecycle: create a graph projection → run the algorithm → (optionally) write results back to the canonical graph.

// Step 1: Project a subgraph into memory
CALL gds.graph.project(
  'my-graph',
  'User',
  'FOLLOWS'
)

// Step 2: Run an algorithm on the projection
CALL gds.pageRank.stream('my-graph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC

// Step 3: Clean up when done
CALL gds.graph.drop('my-graph')

The projection layer is deliberate — it decouples algorithm execution from your transactional workload. The canonical graph is never locked during computation.

Centrality: Finding What Matters

Centrality algorithms answer a deceptively simple question: which nodes are most important? The definition of "important" varies by algorithm.

PageRank

Originally designed to rank web pages, PageRank propagates influence through the graph by following incoming edges. A node's score is determined by the scores of nodes that link to it — a recursive computation that converges on stable values after enough iterations.

In a social network context, PageRank identifies influential users whose content reaches far beyond their immediate followers:

CALL gds.graph.project('influence', 'User', 'FOLLOWS')

CALL gds.pageRank.stream('influence', {
  maxIterations: 40,
  dampingFactor: 0.85,
  tolerance: 1e-7
})
YIELD nodeId, score
MATCH (u:User) WHERE elementId(u) = nodeId
RETURN u.name, score
ORDER BY score DESC
LIMIT 10

When to use PageRank: identifying influential accounts, ranking content by author authority, prioritising seed nodes for information propagation studies.

Betweenness Centrality

Betweenness measures how often a node lies on the shortest path between every pair of other nodes. A high betweenness score means the node is a structural bridge — removing it would fragment the graph.

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

Betweenness is computationally expensive — O(n²) in the naive form. GDS implements Brandes' algorithm with a running time of O(n·m) for unweighted graphs, but for graphs over 100,000 nodes, consider using the approximate variant:

CALL gds.betweenness.sampling.stream('influence', {
  samplingSize: 1000,
  samplingMethod: 'random'
})

When to use betweenness: network vulnerability analysis, single points of failure in infrastructure graphs, gatekeeper detection in organisational networks.

Degree Centrality

The simplest centrality metric — count of relationships. It correlates strongly with PageRank on most graphs but costs practically nothing to compute.

MATCH (u:User)
RETURN u.name,
       size((u)-[:FOLLOWS]->()) AS out_degree,
       size((u)<-[:FOLLOWS]-()) AS in_degree
ORDER BY in_degree DESC
LIMIT 10

Algorithm	What It Measures	Cost	Best For
PageRank	Inbound influence	O(I·(n+m))	Content recommendation, authority ranking
Betweenness	Structural bridging	O(n·m)	Network resilience, bottleneck detection
Degree	Raw connectedness	O(n)	First-pass analysis, real-time dashboards

Pathfinding: How Things Connect

Pathfinding algorithms find optimal routes between nodes — optimal being defined by edge weight, hop count, or a combination of both.

Dijkstra's Shortest Path (Weighted)

For weighted graphs where edges carry a cost — distance, latency, price — Dijkstra's algorithm finds the minimum-cost path between a source and target node:

CALL gds.graph.project(
  'transport',
  'Station',
  'CONNECTED_TO',
  { relationshipProperties: 'minutes' }
)

MATCH (source:Station {name: 'King\'s Cross'})
MATCH (target:Station {name: 'Paddington'})
CALL gds.shortestPath.dijkstra.stream('transport', {
  sourceNode: source,
  targetNode: target,
  relationshipWeightProperty: 'minutes'
})
YIELD index, nodeIds, cost
UNWIND gds.util.asNodes(nodeIds) AS station
RETURN index, station.name AS station, cost

GDS returns the full path as an ordered list of node IDs along with the cumulative cost at each step. The cost field is an array — the last element is the total path cost.

Yen's k-Shortest Paths

One shortest path is rarely enough in production. Yen's algorithm extends Dijkstra to return the top k distinct paths:

MATCH (source:Station {name: 'King\'s Cross'})
MATCH (target:Station {name: 'Paddington'})
CALL gds.shortestPath.yens.stream('transport', {
  sourceNode: source,
  targetNode: target,
  k: 3,
  relationshipWeightProperty: 'minutes'
})
YIELD index, nodeIds, cost
RETURN index, [node IN gds.util.asNodes(nodeIds) | node.name] AS stations, cost

Production use case: a logistics platform showing three alternative delivery routes — fastest, cheapest, and a fallback that avoids toll roads. Yen's k-shortest paths give you the top candidates without re-running the algorithm for each alternative.

Algorithm	Edge Weight	Output	Complexity
Dijkstra	Required	Single shortest path	O(m + n·log n)
A*	Required	Single shortest path (heuristic)	O(m) in practice
Yen's k-Shortest	Required	Top-k distinct paths	O(k·n·(m + n·log n))

Community Detection: Finding the Clusters

Community detection algorithms partition a graph into groups of densely connected nodes. These groups often correspond to meaningful real-world structures — teams within an organisation, topic clusters in a document graph, fraud rings in a transaction network.

Louvain Modularity

Louvain is the workhorse of community detection — fast, unsupervised, and produces a hierarchical nesting of communities. It optimises for modularity, a measure of how much denser connections are within a community than expected by chance:

CALL gds.graph.project('social', 'User', 'FOLLOWS')

CALL gds.louvain.stream('social', {
  maxLevels: 10,
  maxIterations: 50
})
YIELD nodeId, communityId, intermediateCommunityIds
MATCH (u:User) WHERE elementId(u) = nodeId
RETURN u.name, communityId, intermediateCommunityIds
ORDER BY communityId

The intermediateCommunityIds array reveals the hierarchy — community IDs at each level of the Louvain dendrogram. Level 0 is the finest granularity; higher levels are coarser groupings.

For large graphs, Louvain completes in O(n·log n) on average and scales to tens of millions of nodes on a single machine.

Weakly Connected Components (WCC)

WCC finds the connected islands in your graph — groups of nodes where every node is reachable from every other within the group via an undirected path. It is the simplest community detection algorithm but remarkably useful for data quality checks:

CALL gds.wcc.stream('social')
YIELD nodeId, componentId
WITH componentId, collect(gds.util.asNode(nodeId).name) AS members
WHERE size(members) < 5
RETURN componentId, members

This query finds orphaned communities — a sign that your graph has disconnected fragments. In a customer graph, WCC might reveal that an entire customer segment has no relationship to the product catalogue, indicating an ingestion pipeline failure.

Label Propagation

Label Propagation is a semi-supervised algorithm that spreads labels through the graph until convergence. It is ideal for scenarios where you have a small set of ground-truth labels and want to infer labels for the rest:

CALL gds.labelPropagation.stream('social', {
  maxIterations: 50,
  nodeWeightProperty: 'influence_score'
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId

Unlike Louvain, Label Propagation accepts a nodeWeightProperty — useful when some nodes are more authoritative seeds than others.

Algorithm	Supervised?	Deterministic	Best For
Louvain	No	No (tie-breaking)	General-purpose community detection
WCC	No	Yes	Graph connectivity validation
Label Propagation	Semi	No	Seed-based label expansion
Modularity Optimisation	No	Approximate	Very large graphs (100M+ nodes)

Production Patterns

Memory Management

Graph projections live in GDS's memory space, separate from Neo4j's page cache. Monitor them:

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

Always drop projections when they are no longer needed. Projections that survive beyond the session can consume enough memory to degrade transactional performance.

Mutate vs Stream vs Write

Every GDS algorithm supports three output modes:

Mode	Behaviour	Use Case
stream	Returns results as rows	Exploration, ad-hoc analysis
mutate	Stores results in the projection	Chaining multiple algorithms
write	Writes results to the canonical graph	Persisting scores/labels for application queries

Use mutate when chaining algorithms — for example, run PageRank, mutate the score into the projection, then run Louvain weighted by that score. Use write only when you need the result in transactional queries.

// Chain: PageRank → weighted Louvain → write communities
CALL gds.pageRank.mutate('my-graph', {
  mutateProperty: 'pageRankScore'
})
YIELD nodePropertiesWritten

CALL gds.louvain.write('my-graph', {
  relationshipWeightProperty: 'pageRankScore',
  writeProperty: 'community'
})
YIELD communityCount, modularity

Incremental Projections

For graphs that change frequently, rebuilding the entire projection is wasteful. GDS supports incremental projection via Cypher-based projections with filters:

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 recently active users, keeping memory usage bounded and runtime predictable.

Summary

Graph algorithms transform a static graph from a descriptive model into a predictive one. PageRank tells you who influences the network. Community detection reveals hidden organisational structures. Shortest path algorithms power the routing layer of logistics, networking, and navigation applications.

The GDS library makes these algorithms practical for production by running them in-process against memory-efficient projections, supporting incremental updates, and offering three output modes (stream, mutate, write) that let you fit the result into your existing query patterns.

Start with degree centrality and WCC — they cost almost nothing and often reveal data quality issues that would otherwise go unnoticed. Add PageRank and Louvain when you need to rank and cluster at scale. Defer betweenness and k-shortest paths to when you have a concrete routing or resilience use case.

The algorithms themselves are not new — PageRank is nearly thirty years old. What is new is that you can run them against a production graph database with one CALL statement, without exporting a single row.