# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 4 Infomap
First, Infomap reassigns each node to be the sole member of its own module to allow for single-node movements. Then it moves all nodes back to their respective modules of the previous step. At this stage, with the same clustering as in the previous step but with each node free to move between the modules, Infomap reapplies the repeated node aggregation (Algorithm 3). ```
1 functionFineTune(Network \(G\), Node-to-module map M)
2\(\tilde{\mathsf{M}}\leftarrow\) one module per node in \(G\)
3 Update \(\tilde{\mathsf{M}}\) to mirror M
4\(\mathsf{M}\leftarrow\textsc{repeatedNodeaggregation}(G,\tilde{\mathsf{M}})\) (Algorithm 3). 5 return M
```
**Algorithm 5** Fine-tuning

### Coarse-Tuning

In the course-tuning step, Infomap tries to move submodules out from existing modules into new or neighboring modules (Algorithm 6). First, Infomap treats each module as a network on its own and applies repeated node aggregation (Algorithm 3) on this network. This procedure generates one or more submodules for each module. Infomap then replaces the modules by the submodules and moves the submodules into their modules as an initial solution. At this stage, with the same clustering as in the previous step but with each submodule free to move between the modules, Infomap reapplies the repeated node aggregation (Algorithm 3). ### Multilevel Clustering

Infomap identifies multilevel clusterings by extending two-level clusterings both by iteratively finding supermodules of modules and by recursively finding submodules of modules. To find the optimal multilevel solution, Infomap first tries to find an optimal two-level clustering, then iteratively tries to find supermodules and then recursively tries to cluster those modules until the code length cannot be further improved (Algorithm 1). ```
1 functionCoarseTune(Network \(G\), Optional node-to-module map M)
2 for module \(m_{i}\) in M do
3\(G_{i}\leftarrow\) network of nodes and links within \(m_{i}\)
4 Sub-map \(\mathsf{M}_{i}\leftarrow\textsc{repeatedNodeaggregation}(G_{i})\) (Algorithm 3)
5\(\widetilde{G}\leftarrow\) network of submodules \(\mathsf{M}_{i}\)
6\(\tilde{\mathsf{M}}\leftarrow\) map of nodes in \(\widetilde{G}\) to M
7\(\tilde{\mathsf{M}}\leftarrow\textsc{repeatedNodeaggregation}(\widetilde{G}, \tilde{\mathsf{M}})\) (Algorithm 3). 8\(\mathsf{M}\leftarrow\textsc{M}(G)\) such that \(\mathsf{M}(G)\Leftrightarrow\tilde{\mathsf{M}}(\widetilde{G})\)return M
```
**Algorithm 6** Coarse-tuning

To identify a hierarchy of supermodules from a two-level clustering, Infomap first tries to find a shorter description of flows between modules. It iteratively runs the two-level clustering algorithm (Algorithm 2) on a network with one node for each module at the coarsest level, node-visit rates from the module-entry rates, and links that describe aggregated flows between the modules (Algorithm 7). For each such step, a two-level code book replaces the coarsest code book. In this way, describing entries into, within, and out from supermodules at a new coarsest level replaces only describing entries into the previously coarsest modules. For a fast multilevel clustering, Infomap can keep this hierarchy of supermodules and try to recursively cluster the bottom modules into submodules with Algorithm 8. However, as this hierarchy of supermodules is constrained by the initial optimal two-level clustering, discarding everything but the top supermodules and starting the recursive submodule clustering from them often identifies a better multilevel clustering. To find submodules, Infomap runs the two-level clustering (Algorithm 2) followed by the super-module clustering (Algorithm 7) algorithm on the network within each module to find the largest submodule structures. If Infomap finds non-trivial submodules (that is, not one submodule for all nodes and not one submodule for each node), it replaces the module with the submodules and collects the submodules in a queue to explore each submodule in parallel for each hierarchical level.