A Bit of History
Noga Alon, Yossi Matias, and Mario Szegedy published "The Space Complexity of Approximating the Frequency Moments" in 1996 — the foundational paper of streaming algorithms, later earning its authors the Gödel Prize. On the distributed side, Google's own Grzegorz Malewicz and colleagues published "Pregel: A System for Large-Scale Graph Processing" in 2010, describing the internal system Google actually used to compute PageRank-style algorithms across web-scale graphs spanning many machines — directly inspiring the open-source systems (Apache Giraph, GraphX) that followed. The theoretical Massively Parallel Computation (MPC) model formalizing this setting was introduced by Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii in a 2010 paper directly motivated by MapReduce.
Modern Graph Algorithms Change the Resource You Are Trying to Save
Classical algorithms mostly optimize CPU time while assuming the graph is already in memory. At scale, the scarce resource may instead be memory, update time, or communication rounds.
Memory aid: streaming asks “what can I remember?”, dynamic asks “what can I repair?”, distributed asks “what must I communicate?”, and MPC asks “how few global rounds can I afford?”
Streaming Graph Algorithms
In the streaming model, a graph's edges arrive one at a time in a single pass, and the algorithm must process each edge using memory far smaller than the full graph — typically \(O(V \cdot \text{polylog}(V))\) or even less, when the graph itself could have \(O(V^2)\) potential edges. This forces fundamentally different algorithmic thinking: instead of building an adjacency list and running BFS/DFS as in earlier parts, streaming algorithms maintain small "sketches" — compressed summaries sufficient to answer specific questions (is the graph connected? what's an approximate matching size?) without ever storing the whole graph.
Memory Budgets, Passes & Sketches
A streaming algorithm is defined as much by what it refuses to remember as by what it computes. If the input stream contains millions or billions of edges, storing the adjacency list defeats the model. Instead, the algorithm chooses a compact state tailored to one question: counters, samples, hash-based sketches, a spanning forest, or other compressed summaries.
Semi-streaming target:
$$\text{memory} = O\!\left(V\,\operatorname{polylog}V\right) \ll O(E) \text{ for dense graphs.}$$
The Stream Flows Past; Only the Summary Stays
Imagine the edges as a conveyor belt. Once an edge has passed, the algorithm may never see it again. The art is deciding which tiny facts must survive so the final query can still be answered.
There are several streaming variants. In an insertion-only stream, edges only appear; for connectivity, a disjoint-set structure can maintain the connected components exactly using only vertex-scale memory. A turnstile or dynamic stream also contains deletions, which is much harder because an edge removed now may have been the only connection between two large regions. Many sophisticated graph-streaming algorithms therefore use randomized linear sketches that can survive both additions and deletions.
What a Sketch Really Means
A sketch is not a compressed copy from which the whole graph can later be reconstructed. It is a deliberately lossy summary designed so that one particular statistic or property remains recoverable — often approximately or with high probability.
Dynamic Graph Algorithms
A dynamic graph algorithm maintains a query-ready answer (connectivity, shortest paths, matching size) while the graph itself undergoes a stream of edge insertions and deletions — recomputing from scratch after every change would be far too slow for graphs updated continuously (a social network's ever-changing friendship graph, for instance). Holm, de Lichtenberg, and Thorup's landmark 2001 paper achieves \(O(\log^2 n)\) amortized time per update for dynamic connectivity — dramatically faster than recomputing a BFS/DFS-based answer (Parts 5-8) from scratch after every single edge change.
Incremental, Decremental & Fully Dynamic
“Dynamic” is not one problem but three related update models. Incremental algorithms see insertions only, decremental algorithms see deletions only, and fully dynamic algorithms must handle both. Deletions are usually the subtle part: adding an edge can only create new routes, while deleting one may invalidate a certificate the data structure has relied on for a long time.
One Edge Changes; the Whole Answer Should Not Have to Start Over
A dynamic data structure stores enough structure from the previous state that the next update can be repaired locally. The goal is to make each change far cheaper than rerunning a classical algorithm from scratch.
Dynamic algorithms are usually judged by two costs: update time (how expensive is an insertion/deletion?) and query time (how quickly can the maintained answer be read?). Sometimes one can be made tiny only by paying more for the other, so the right data structure depends on whether the workload is update-heavy or query-heavy.
Why Union-Find Is Only Half the Story
Disjoint Set Union is an excellent incremental connectivity structure: every inserted edge simply merges two components. But DSU cannot “un-merge” a component when an edge is deleted. Fully dynamic connectivity needs additional structure precisely because deletions can invalidate old unions.
Distributed Graph Processing
Graphs like the web graph or large social networks are far too large to fit on a single machine's memory, forcing computation to be spread across many machines simultaneously. Google's Pregel system (2010) popularized the influential "think like a vertex" programming model: each vertex runs the same simple local computation in synchronized rounds, sending messages only to its direct neighbors, with the system handling all cross-machine communication — this is precisely the model in which distributed PageRank (previewed in a future deep dive) and distributed connected-components algorithms are typically implemented at web scale.
Pregel Supersteps: Compute, Message, Barrier
Pregel follows a bulk-synchronous rhythm. During a superstep, each active vertex reads messages from the previous round, updates its local state, and sends messages for the next round. Then the system waits at a global barrier so that all machines agree the round is complete. This makes the programming model simple, but it also makes the number of rounds and the volume of cross-machine messages central performance costs.
A Distributed BFS Layer Is One Global Conversation
A BFS-style computation is naturally expressed as waves of messages. Vertices discovered in one superstep notify neighbors in the next. The algorithm is simple locally; the expensive part is synchronizing and moving messages across machine boundaries.
Graph partitioning now becomes an algorithmic concern in its own right. An edge whose endpoints live on the same machine is cheap; an edge crossing a partition boundary may cause network traffic every round. A “good” partition tries to balance memory and computation while minimizing those expensive cross-machine edges — goals that can conflict on irregular, high-degree real-world graphs.
The Massively Parallel Computation Model
The theoretical MPC model formalizes distributed graph processing for analysis: many machines, each holding only a sublinear share of the total data, communicate in a small number of synchronized rounds, with the goal of minimizing that round count (since cross-machine communication, not local computation, is typically the true bottleneck at scale). A large body of modern research asks: which classical graph algorithms from earlier in this series (connectivity, matching, shortest paths) can be adapted to run in O(1) or \(O(\log n)\) MPC rounds, rather than requiring a number of rounds proportional to the graph's diameter?
Key Insight
A naive distributed BFS (Part 5) needs one communication round per BFS layer — potentially thousands of rounds on a graph with large diameter. Much of modern distributed graph algorithms research is specifically about beating this bound, using techniques like graph sketching and careful load-balancing to solve connectivity and related problems in a number of rounds that barely depends on the graph's diameter at all.
Rounds, Local Memory & Total Memory
The MPC abstraction strips away implementation details and asks a cleaner theoretical question: if the input is spread over many machines, each with limited local memory, how many global communication rounds are required? Within a round, each machine may perform substantial local computation; between rounds, data can be shuffled so different machines receive different pieces of the graph.
More Machines Help Only If Communication Stays Under Control
MPC algorithms trade among three budgets: how much one machine may store, how much memory the cluster uses in total, and how many synchronized shuffles are required.
A common research regime requires each machine to hold only a sublinear fraction of the input, so no machine can secretly solve the entire problem alone. Under that constraint, an algorithm using only a constant or logarithmic number of rounds can represent an enormous reduction in wall-clock latency compared with a diameter-round BFS.
Why Round Complexity Dominates
Local CPU operations happen in parallel and are relatively cheap. A global shuffle requires serialization, network transfer, straggler handling, and synchronization across the cluster. That is why modern parallel graph theory often treats one extra communication round as a much bigger deal than millions of extra local arithmetic operations.
| Model | Input assumption | Main resource | Typical mental question |
|---|---|---|---|
| Streaming | Edges pass by, often once | Memory / passes | What tiny summary is enough? |
| Dynamic | Graph changes over time | Update + query time | What can I repair instead of recompute? |
| Pregel / BSP | Graph is partitioned across machines | Messages + supersteps | What can each vertex do locally? |
| MPC | Massive parallel cluster, limited local memory | Global rounds | How few shuffles can solve it? |
Real-World Applications
Real-Time Fraud Detection on Transaction Graphs
Payment networks model transactions as a continuously growing, continuously changing graph (accounts as vertices, transactions as edges) and need to detect suspicious connectivity patterns — like sudden dense clusters suggesting coordinated fraud — in near real time, as new transactions stream in every second. This is a direct, high-stakes application combining streaming algorithms (processing the never-ending transaction stream) and dynamic graph algorithms (maintaining connectivity and clustering answers without recomputing from scratch on every new transaction).
Notice that “streaming,” “dynamic,” and “distributed” are not competing labels. A single production pipeline may use a streaming front end to ingest events, a dynamic data structure to keep the live graph current, and a distributed or MPC-style back end for expensive neighborhood analysis.
- Streaming
See the data once; remember only a sketch. - Sketch
Lossy summary tailored to one query. - Dynamic
Repair answers after graph updates. - Deletion
Hard because old connectivity certificates can break. - Pregel
Vertex-local compute plus neighbor messages. - Partition
Cut edges often become network traffic. - MPC
Many limited-memory machines, few global rounds. - Scale
Communication can matter more than arithmetic.
Exercises
- Explain why a naive algorithm that stores the full adjacency list is not considered a valid "streaming algorithm," even if it correctly processes edges one at a time.
- Describe, at a high level, why recomputing a dynamic connectivity answer via a fresh BFS/DFS after every single edge update would not scale to a graph receiving thousands of updates per second.
- Explain the "think like a vertex" Pregel programming model in your own words, and contrast it with the single-machine BFS/DFS algorithms from earlier in this series.
- Challenge: Research the MPC model's formal round-complexity goal (typically \(O(1)\) or \(O(\log n)\) rounds) and explain why minimizing rounds, rather than total computation, is the primary objective in this model.
Conclusion & Next Steps
Scaling classical graph algorithms to streaming, dynamic, and distributed settings is an active and rapidly evolving research area, driven directly by the scale of modern real-world graphs. Those same massive real-world graphs are rarely simple, either — many naturally involve richer structures than a plain graph can represent, which the next part addresses directly.
Next in the Series
In Part 24: Hypergraphs, Temporal & Multilayer Networks, we'll explore structures that generalize plain graphs to capture group relationships, time, and multiple simultaneous relationship types.