Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 30 ยท Graph Algorithms and Applications

Graph algorithms: PageRank, communities, shortest paths

See how Neo4j's Graph Data Science library runs PageRank, community detection, betweenness and Dijkstra, and build each idea yourself in Python.

Cypher is excellent at answering questions about specific nodes and their neighbourhoods. Some questions are about the whole graph: which accounts are most influential, which groups of people form natural clusters, which node is the only bridge between two halves of a network. Those are answered by graph algorithms, and Neo4j ships a separate library for them called Graph Data Science (GDS).

This lesson explains how GDS is used and then builds the main ideas from scratch: PageRank, community detection, betweenness centrality and weighted shortest paths with Dijkstra. GDS is a server plugin, so its procedure calls are read-only code blocks. The Python stand-ins run in your browser on tiny graphs. They are simplified, deterministic teaching versions: GDS uses parallel, optimized implementations with more options, and its numbers can differ in small ways (for example in how it treats damping and dangling nodes).

How GDS works: project, run, drop

GDS does not run algorithms directly on the stored graph. First you project the part you need into an in-memory graph, then run algorithms on that projection, and finally write results back or stream them out.

CYPHER
// 1. project nodes and relationships into memory under a name
CALL gds.graph.project('social', 'Person', 'FOLLOWS')

// 2. run an algorithm in stream mode and join results back to nodes
CALL gds.pageRank.stream('social')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 5

// 3. free the memory when you are done
CALL gds.graph.drop('social')

Most algorithms offer several execution modes: stream returns rows, stats returns a summary, mutate stores results in the in-memory graph for the next algorithm, and write stores them as properties in the database. The in-memory projection is fast because the algorithm no longer touches the transactional store. The price is that you must rebuild the projection when the data changes. Procedure names and options evolve between releases, so confirm them against the manual for your version.

flowchart LR
    DB[("Stored graph")] -- "gds.graph.project" --> M["In-memory<br/>graph projection"]
    M --> A["Algorithm<br/>PageRank, Louvain, ..."]
    A -- "stream" --> R["Result rows"]
    A -- "write" --> DB
    A -- "mutate" --> M

The GDS workflow: project into memory, run an algorithm, then stream, mutate or write the results.

PageRank scores a node by how many nodes point to it, weighted by the scores of those nodes. A follow from someone important counts for more than a follow from a nobody. The classic way to think about it is a random surfer who keeps clicking links, and who with probability 0.15 (the damping remainder) jumps to a random page instead. The score is the share of time the surfer spends on each node.

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

The calculation is iterative. Start every node with an equal score, then repeatedly give each node a share of the score of every node linking to it, until the numbers stop changing. The stand-in does exactly that.

Python PageRank by repeated sharing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cy comes out on top because five of the six people follow Cy. Dee is a close second: Dee has only two followers, but one of them is Cy, so a large share of Cy's score flows on to Dee, and Dee passes much of it back. Eli, followed only by Dee, inherits a good share too. Ben and Fay have no followers, so they keep only the random-jump share, 0.15 / 6 = 0.025. The ranking reflects both how many links point at a node and who those links come from.

Community detection: finding clusters

Community detection groups nodes that are densely connected with each other and sparsely connected to the rest. GDS offers several algorithms, such as Louvain (maximizes a measure called modularity), Label Propagation and Weakly Connected Components (which only separates disconnected pieces).

CYPHER
CALL gds.louvain.stream('social')
YIELD nodeId, communityId
RETURN communityId, collect(gds.util.asNode(nodeId).name) AS members
ORDER BY size(members) DESC

Label propagation is simple enough to write in a few lines: every node starts with its own label and repeatedly adopts the most common label among its neighbours. Real implementations are randomized or parallel; the stand-in uses a fixed visiting order and a fixed tie-break so that the output is the same every time.

The same program computes betweenness centrality, which counts on how many shortest paths between other node pairs a node lies. A high value marks a bridge or broker. It uses Brandes' algorithm, which runs one breadth-first search per node.

Python Communities and bridges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bridge node scores highest, 9.0: each of the 3 x 3 pairs made of one node from each triangle has a single shortest path, and all of them pass through it. Its neighbours a3 and b1 are on 8 of those paths each. In a real network such a node is a single point of failure, a key broker, or both. Note also that the label propagation put the bridge into the first group, because its two neighbours tied and the smaller label won: community results depend on tie-breaking, which is why real implementations expose seeds and settings.

Shortest paths: Dijkstra with weights

In Paths, aggregation and WITH the shortest path counted hops. Real networks often have costs: distance, travel time, price. Dijkstra's algorithm finds the cheapest route when costs are not negative. If you have not met it, read Dijkstra first. GDS exposes it like this, with the cost taken from a relationship property:

CYPHER
MATCH (a:Station {name: 'North'}), (b:Station {name: 'Harbor'})
CALL gds.shortestPath.dijkstra.stream('transit', {
  sourceNode: a,
  targetNode: b,
  relationshipWeightProperty: 'minutes'
})
YIELD totalCost, nodeIds
RETURN totalCost, [id IN nodeIds | gds.util.asNode(id).name] AS route

The projection must include the weight property, for example by passing relationshipProperties: 'minutes' in the relationship configuration when you project.

Python Fewest hops is not cheapest

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The direct road has the fewest stops (one hop) but costs 20, while the cheapest route takes two roads and costs 7. That is the difference between an unweighted shortestPath in Cypher and a weighted algorithm in GDS.

Choosing an algorithm

Question Family Example in GDS
Who is important? Centrality PageRank, Betweenness, Degree
Which nodes belong together? Community detection Louvain, Label Propagation
How are two things connected cheaply? Pathfinding Dijkstra, A*, BFS
Which nodes look alike? Similarity Node Similarity, K-Nearest Neighbors

Treat the output as evidence, not truth. PageRank on a sparse sample of a graph can mislead, and community results change with the algorithm and its settings.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the first step when using a GDS algorithm?

    GDS algorithms run on an in-memory projection created with gds.graph.project, not directly on the stored graph.
  2. 2. In PageRank, which node gets a higher score?

    Scores flow along links, so a link from an important node is worth more than a link from an unimportant one.
  3. 3. What does a high betweenness centrality indicate?

    Betweenness counts how many shortest paths between other pairs pass through a node.
  4. 4. Why can Dijkstra's cheapest route differ from Cypher's shortestPath result?

    A route with fewer hops can cost more in total, which weighted algorithms account for.

Summary

  • GDS runs algorithms on a named in-memory projection and offers stream, stats, mutate and write modes.
  • PageRank measures importance by incoming links weighted by the importance of the linkers.
  • Community detection (Louvain, label propagation) finds dense clusters; betweenness finds bridges.
  • Dijkstra finds the cheapest path with non-negative weights; Cypher's shortestPath only counts hops.
  • The procedure calls above are read-only; the Python programs are simplified stand-ins that show the underlying ideas.

Next: Recommendations and fraud detection with graphs.