Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems

Here is a thought experiment. You have a network with two million nodes — every intersection and stretch of road in California. Or three and a half thousand cities connected by flight routes spanning the globe. Or eight thousand academic journals citing each other nine million times. You want to know how these systems are organized. So you run a clustering algorithm, and it hands you back a flat list of groups. One level. One cut. And you immediately sense something is wrong, because you know — intuitively — that California's roads have neighborhoods inside cities inside counties inside regions. That science has subfields inside fields inside disciplines. That a single flat partition is not a map. It's a smear. Martin Rosvall and Carl Bergstrom built a method that does what a good map does: it finds the countries and the continents simultaneously, and it decides how many levels to show. It does this through compression alone — through the mathematics of information theory — with no prior assumptions about how deep the hierarchy should go. The starting point is a question about dynamics. Most community detection approaches ask: what probabilistic process generated these links? That is useful if you want to know how the network was built. But Rosvall and Bergstrom are interested in something different — what happens on the network after it exists. Passengers flow through airports. Readers follow citations. Signals propagate through neurons. The structure that matters for those processes is the structure that shapes flow, and the tool they use to probe it is a random walker: an agent that hops from node to node along links, with probability proportional to link weights. The key insight is that a random walker reveals structure through time. It lingers inside tightly connected regions and rarely crosses between them. Those differences in dwelling time are exploitable. If you're describing the walker's path step by step, you can assign short codewords to frequently visited nodes within a module, and use a separate index codebook to indicate which module's codebook is currently active. When the walker stays inside a module for a long stretch, you keep using that module's short codewords without paying the switching cost. This is the map equation: the average number of bits needed to describe one step of the random walk. Minimize that average over all possible partitions, and you've found the partition that best compresses the walk — which is the same as finding the partition that best reflects the structure generating the flow. Rosvall and Bergstrom illustrate this with a twenty-seven node example. A single global codebook — no modules — requires four point seventy-five bits per step. Partitioning the network into nine modules and using a two-level scheme drops that to three point fifty-seven bits. But then they notice something: the nine modules themselves cluster into larger groups where the walker tends to linger. Adding a second index level — a coarser codebook that names groups of modules — drops the description length further to three point forty-eight bits. Nine hundredths of a bit. Small, but real. And that small saving is the formal signature of genuine hierarchical structure. The hierarchical map equation extends this logic recursively. Instead of one index codebook sitting above the module codebooks, you can nest index codebooks inside index codebooks — modules of modules of modules, to whatever depth the data supports. Crucially, the method decides depth automatically. Adding a level only helps if it shortens the description. If a system has no meaningful substructure below a certain scale, the algorithm simply stops there. No user specified resolution parameter. No arbitrary dendrogram cut. The search algorithm that finds the optimal hierarchical partition works recursively and greedily. It begins by assigning each node to its own module, then repeatedly moves each node to whichever neighboring module produces the largest drop in description length. When single-node moves stop helping, the current modules become the nodes of a coarser network, and the procedure repeats at the next level up. Two refinement passes — one that looks for submodules within each module, and one that frees individual nodes for singleton moves — are applied recursively and repeated until no further improvement is possible. On networks of ten thousand nodes and one million links, individual runs take seconds on a modern laptop. Rosvall and Bergstrom routinely ran hundreds of restarts to guard against local minima. They benchmarked the method on Lancichinetti-Fortunato hierarchical benchmark networks — ten thousand nodes, one hundred thousand links, planted three-level hierarchies — using normalized mutual information between the planted and recovered partitions as the performance metric, where one means perfect recovery and zero means the two partitions share no information. The method recovers planted structure well across a range of mixing parameters. That validation done, the real networks arrive — and the results are striking. From the global air traffic network — three thousand eight hundred eighty-three cities, fourteen thousand one hundred forty-two routes — the algorithm recovers cities grouped into countries, countries grouped into continents. The largest module combines European and African cities organized into fifty-five submodules. The second largest groups the Americas into seventy-five submodules, distinguishing Eastern US, Western US, Mexican cities, and more. The algorithm found this geography knowing nothing about geography. It only knew which cities had direct flights to which other cities. The journal citation network is even richer. More than nine million citations among nearly eight thousand journals. The hierarchical map equation recovers over one hundred scientific fields organized into four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. Physical sciences split further into a physics and chemistry cluster with thirty-five subfields and a mathematics cluster with twenty-four subfields. Flow makes this concrete: a random reader following citations would spend fifty-four percent of her time in life sciences, thirty-three percent in physical sciences, eight percent in ecology and earth sciences, and four percent in social sciences. Only about one percent of steps cross discipline boundaries, with the most common crossing running from physical sciences into life sciences. Now here is where the results become more than a demonstration of the method. Rosvall and Bergstrom compare hierarchical depth across very different systems, and a pattern emerges that is itself scientifically meaningful. The California road network — two million nodes, five and a half million links — produces a per-node average depth of four point eight and a compression gain of thirty-six percent over a two-level description. That means going from a flat partition to a multilevel one cuts the description length by more than a third. The road network is spatially constrained: you cannot drive from San Francisco to Los Angeles without passing through everything in between. Flow is local. Structure is deeply nested. At the other extreme, the C. elegans brain network and the weighted US air passenger network both compress no better with multiple levels than with two. Their compression gain is zero percent. These systems are globally interconnected — long-range links, short path lengths, flow that mixes broadly. There is nothing to be gained by nesting, because the walker doesn't linger in local pockets long enough to make local codebooks efficient. Web graphs fall between these poles. The Google web graph, with seven hundred forty thousand nodes, achieves a compression gain of sixteen percent and an average depth of four point five — deep structure, but with more global mixing than roads. The pattern Rosvall and Bergstrom summarize is direct: shallow hierarchies in globally interconnected systems, rich multilevel organization in systems with highly separated regions. But stated that way, it sounds almost tautological. What makes it interesting is that the depth emerges from the compression objective alone — you don't put geography or topology in by hand. The algorithm is reading the flow, and the flow is telling you how locally organized the system is. This is what makes the hierarchical map equation more than a clustering tool. The depth of the hierarchy it recovers is a measurement. It quantifies how compartmentalized a system is — how strongly flow is channeled into nested local structures rather than spreading globally. A road network and a brain network can both be described as nodes and links, but the hierarchical map equation distinguishes them precisely because it is sensitive to how movement actually propagates through each one. The framework is agnostic to what kind of flow you model. Random walks are the default, but any flow model that assigns visit probabilities to nodes and transition probabilities to links can be plugged in. That means the hierarchical cartography Rosvall and Bergstrom describe is available to any domain where dynamics on a network are the object of interest — not just the links themselves, but what moves along them. Compression, in this view, is not a bookkeeping convenience. It is a lens. The shortest description of a random walk is, simultaneously, the best map of the territory the walk explores. This lecture was created by ennepō. Go to https://ennepo.ai to Discover, Create and Follow the latest research in your field. Read when you can. Listen when you want to.