Graphs in the Wild

Every algorithm on the other pages of this track is running in production somewhere right now, usually at a scale where the constant factors matter more than the asymptotics. This page is the payoff: where each one actually lives, and the handful of concepts that only exist because real graphs are enormous.

Nothing here is needed for an interview. It is here because knowing that Kahn's algorithm is npm install makes the algorithm stick in a way another practice problem does not.

1. The map

System	The graph is	The algorithm is
**npm / pip / cargo install**	packages, with edges to their dependencies	Topological sort, plus cycle detection to report a circular dependency. A version conflict makes it a full SAT problem, which is why modern resolvers embed a SAT solver.
**make / Bazel / any build system**	targets and their inputs	Topological sort. "How many parallel build stages" is level-batched Kahn.
Git	commits, with edges to parents	A DAG. git log is a traversal, merge-base is lowest common ancestor, and a rebase is a replay in topological order.
Internet routing (OSPF, IS-IS)	routers and links, weighted by cost	Dijkstra, re-run on every topology change. BGP between networks is policy-driven rather than shortest-path, which is why the internet is not globally optimal.
Maps and navigation	road intersections and segments	Dijkstra and A\*, on a graph far too big to search naively - see section 3.
Spreadsheets	cells, with edges to the cells they reference	Topological sort to decide recalculation order; a cycle is the #REF! circular-reference error.
Compilers	basic blocks; also the type/trait resolution graph	Dominator trees (a low-link relative), SCCs for loop detection, topological sort for instruction scheduling.
Social networks	people and follows/friendships	BFS for degrees of separation, centrality for influence, community detection for grouping.
Fraud detection	accounts and transactions	Connected components and SCCs to surface rings; a cycle of transfers is often the signal itself.
Recommendations	a bipartite graph of users and items	Random walks and matrix factorisation; "people who bought this" is a two-hop neighbourhood.
Chip design and scheduling	tasks with dependencies and durations	The critical path method - earliest start, latest start, slack.
Garbage collectors	objects, with edges to the objects they reference	Reachability from the roots. Mark-and-sweep is literally a DFS; anything unreached is freed.

Mnemonic

"Does the order matter?" means topological sort. "How far apart?" means BFS or Dijkstra. "Who belongs together?" means components or SCCs. "What is the bottleneck?" means min cut. Four questions cover most production graph work, and each maps to one page of this track.

2. Centrality: which vertex matters most

"Important" is not one thing, so there is not one measure. Four definitions, each answering a different question and each used somewhere:

Measure	Defines importance as	Cost	Where it is used
Degree centrality	how many neighbours you have	O(V + E)	The cheap first cut. "Most followed account."
Closeness centrality	how short your average distance to everyone is	O(V * (V + E)) - a BFS per vertex	Facility location: where to put the warehouse.
Betweenness centrality	how many shortest paths run through you	O(V * E) with Brandes' algorithm	Finding brokers and chokepoints - the social analogue of a bridge.
PageRank	how likely a random surfer is to land on you	O(E) per iteration, tens of iterations	Web search, citation ranking, and any "importance flows from important things" question.

The same structural fact as C being on a bridge: local popularity and global indispensability are different properties.

PageRank

PageRank is the one worth understanding properly, because it is a fixed point rather than a traversal. Imagine a surfer who, at every step, either follows a random outgoing link (with probability d, conventionally 0.85) or teleports to a uniformly random page. PageRank is the long-run fraction of time spent on each page.

def pagerank(num_nodes, adj, damping=0.85, iterations=50):

rank = [1 / num_nodes] * num_nodes

out_degree = [len(adj[u]) for u in range(num_nodes)]

for _ in range(iterations):

nxt = [(1 - damping) / num_nodes] * num_nodes # the teleport term

leaked = 0.0

for u in range(num_nodes):

if out_degree[u] == 0:

leaked += rank[u] # dangling: spread it evenly

continue

share = damping * rank[u] / out_degree[u]

for v in adj[u]:

nxt[v] += share

if leaked:

for v in range(num_nodes):

nxt[v] += damping * leaked / num_nodes

rank = nxt

return rank

Importance flows along edges and is conserved.

Each vertex hands its current score out in equal shares to everything it points at, so a link from a high-scoring page is worth more than a link from a low-scoring one - which is the whole idea, and why it beat simple link-counting. The teleport term is what guarantees a unique answer: it makes the graph strongly connected, so the random walk cannot get permanently trapped.

⚠

Dangling vertices break conservation checks

Dangling vertices - out-degree zero - break conservation and must be handled explicitly. A page with no outgoing links has nowhere to send its score, so each iteration quietly destroys it and every rank decays towards the teleport floor. The standard fix is the leaked accumulator above: treat a dangling vertex as if it linked to everything. Forget it and your ranks do not sum to 1, which is the diagnostic to check.

Mnemonic

PageRank is a random walk; the damping factor is the probability of continuing it. d = 0.85 means the surfer gets bored roughly every seven clicks. Lower d weights local structure less and converges faster; d = 1 may not converge at all.

3. What changes when the graph does not fit in memory

Everything on the other pages assumes the graph is a variable you own. At real scale it is not, and three ideas exist purely because of that.

Idea	The problem it solves	How
Contraction hierarchies	Dijkstra on a continental road network takes seconds, and a routing service needs milliseconds	Precompute shortcut edges that skip unimportant intersections, then search only the "important" layers. Queries drop by three or four orders of magnitude, at the cost of hours of preprocessing.
Landmarks / ALT	A\* needs an admissible heuristic, and road distance is a weak one	Precompute exact distances to a few hundred landmark vertices; the triangle inequality then gives a much tighter admissible bound.
Graph partitioning	A billion-edge graph must be split across machines	Cut the graph into balanced parts with as few crossing edges as possible - each crossing edge is network traffic on every iteration. This is an NP-hard min-cut variant solved heuristically (METIS, Louvain).
Vertex-centric / Pregel model	Traversal does not parallelise naturally	Rewrite the algorithm as "every vertex receives messages, updates itself, sends messages" and run supersteps. BFS, PageRank and connected components all fit; DFS notoriously does not, because it is inherently sequential.
Compressed adjacency (CSR)	Python lists of lists waste most of their memory on pointers	Two flat arrays: all neighbours concatenated, plus an offset per vertex. Same O(V + E) traversal, a fraction of the bytes, and cache-friendly.

BFS, PageRank, connected components and shortest paths all parallelise cleanly - each round is "every vertex looks at its neighbours," which shards across machines. DFS does not. Its defining property is that it explores one branch fully before the next, which is a strict sequential dependency, and the disc/fin timestamps that make it powerful (the DFS tree) are exactly what cannot be computed out of order. Distributed systems therefore avoid DFS-based algorithms - which is why distributed SCC uses forward-backward reachability instead of Tarjan's.

4. Graph databases and knowledge graphs

A relational schema stores relationships as foreign keys, so "friends of friends of friends" is three self-joins, and each one multiplies the row count. A graph database (Neo4j, TigerGraph, Neptune) stores each vertex with direct pointers to its edges, so the same query is a three-hop traversal whose cost depends on the neighbourhood size rather than the table size.

	Relational	Graph database
k-hop query	k joins; cost grows with table size	k pointer hops; cost grows with neighbourhood size
Aggregations over everything	Excellent - this is what it is for	Weaker
Schema changes	Migrations	Add a new edge type and move on
The model	tables and foreign keys	property graph: vertices and edges both carry key-value properties

Mnemonic

Use a graph database when the relationships are the data. If your queries are "sum this column by that column," a relational database wins. If they are "find paths, patterns, or neighbourhoods," the traversal model wins - and the tell is whether you find yourself writing recursive CTEs.

A GNN computes a vector per vertex by repeating one step: each vertex aggregates its neighbours' vectors and mixes the result with its own. After k rounds, a vertex's vector summarises its k-hop neighbourhood - which is the same "supersteps of local updates" model as Pregel, with a learned update function instead of a fixed one. That framing also explains their main limitation: two vertices with identical k-hop neighbourhoods get identical vectors, so a plain GNN cannot tell them apart no matter how it is trained.

Where to go next

• Graph Anatomy - back to the vocabulary, if any term here was unfamiliar.
• Cycles & Ordering - the topological sort that half the systems in section 1 are running.