Partitioning Massive Graphs with MapReduce: Building Multi-Source BFS from Scratch

Overview

I’ve been trying to move beyond solving problems in memory and actually think in terms of systems. So I picked up a project that sits right in that space: graph partitioning using MapReduce.

The idea sounds simple at first. Take a directed graph, pick a few starting nodes (centroids), and assign every other node to the closest centroid using BFS.

The catch is doing all of that in a distributed setting.

Each line of input looked like this:

1,2,3,4,5

Which just means node 1 connects to nodes 2, 3, 4, and 5.

Nothing complicated about the format. The complexity comes from how the data flows.

What We’re Actually Doing

Instead of running BFS from one node, we run it from multiple nodes at the same time.

Each centroid spreads outward, layer by layer. Every node gets claimed by whichever centroid reaches it first.

You can think of it like multiple signals moving through the graph at once, competing to reach nodes.

Step by Step Breakdown

The first step was converting raw text into something structured.

Each node becomes a vertex object that stores:

• its ID
• its neighbors
• the centroid it belongs to
• the distance from that centroid

At the beginning, most nodes are unassigned:

centroid = -1

A few nodes are chosen as starting points:

first 10 nodes → centroid = id

This sets up multiple BFS sources from the start.

Step 2: Simulating BFS with MapReduce

This is where things get interesting.

In a normal BFS, you’d use a queue. Here, you don’t have that. Instead, BFS is simulated across multiple MapReduce iterations.

Each iteration represents one “layer” of BFS.

Map Phase

For every node:

• pass its structure forward so we don’t lose the graph
• if it belongs to a centroid, send that centroid information to its neighbors

Conceptually:

emit(node, structure)
emit(neighbor, centroid message

Reduce Phase

Each node collects all incoming messages and decides which centroid is closest.

if (depth < min_depth) update centroid

Once that decision is made, the node updates:

• its centroid
• its depth

This process repeats across iterations.

The Critical Insight

This is the part that took me a minute to get right.

At first, I let every node that had a centroid keep spreading it every iteration.

That completely breaks BFS.

Instead of clean layers, everything floods at once and distances stop meaning anything.

The fix was simple but important: In code, that became:

vertex.depth == BFS_depth - 1

This ensures that only nodes discovered in the previous iteration expand in the current one.

That single condition makes the difference between correct BFS and completely wrong results.

Step 3: Count Cluster Sizes

After enough iterations, every node has been assigned to a centroid.

The final step is just aggregation.

Each node emits:

emit(centroid, 1)

Reducers sum everything:

cluster size = total nodes per centroid

So the final output looks like:

69   4
80   10
82   6

Each row represents:

• the centroid
• the number of nodes in its cluster

Running the System

Local mode:

bin/run-local

Distributed mode:

bin/run-distr

To verify correctness:

diff small-solution.txt local-output.txt

If nothing prints, the output matches exactly.

What I Took Away

This project made it clear that algorithms like BFS behave very differently in a distributed setting. Without a queue or shared memory, everything depends on how you structure iterations and pass state between steps. Small details, like controlling which nodes expand at each stage, end up determining whether the entire system works or fails. It also changed how I approach debugging. Instead of stepping through code, I had to reason about data flow and compare outputs to understand what was going wrong. Overall, it pushed me to think less about writing logic line by line and more about how data moves through a system, which is really what distributed systems are all about.