# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 4 Infomap
Infomap aggregates neighboring nodes into modules, subsequently aggregates them into larger modules, and repeats. First, Infomap assigns each node to its own module. Then, in random sequential order, it tries to move each node to the neighboring or a new module that gives the largest code length decrease (Algorithm 4). If no move gives a code length decrease, the node stays in its original module. The change of code length for each possible move can be calculated locally based only on the change in _enter_ and _exit_ flows, the current flow in the moving node and affected modules, and the initial _enter_ flow for the module. For state nodes, the physical node visit rates can be locally updated. Infomap repeats this procedure, each time in a new random sequential order, until no move happens. Then Infomap rebuilds the network with the modules of the last level forming the nodes at the new level, and, exactly as in the previous level, aggregates the nodes into modules, which replace the existing ones. Infomap repeats this hierarchical network rebuilding until the map equation cannot be further reduced. The computational complexity of the repeated node aggregation is considered to be \(\mathcal{O}(N\log N)\) for the Louvain method applied to networks with \(N\) nodes [34]. While Infomap optimizes the map equation with some more costly logarithms, there is no fundamental difference in the scaling. However, for sparse memory networks, the scaling applies to the number of state nodes. In any case, the first aggregation step is the most expensive because Infomap considers each node and all its links such that the complexity scales with the number of links in the network. To further optimize the map equation, Infomap performs stochastic tuning steps with more network dependent computational complexity. ```
1 functionrepeatedNodeAggregation(Network \(G\), Node-to-module map \(\mathsf{M}\))
2 Let \(L=L(\mathsf{M})\) be the code length for the map \(\mathsf{M}\) with node-to-module assignments
3 Let \(e\) be a small threshold
4 Let \(l^{L}_{max}\) be a maximum number of level iterations
5 if\(\mathsf{M}\) is emptythen
6\(\mathsf{M}\leftarrow\) one module per node in \(G\)
7\(L_{old}\gets L(\mathsf{M})\)
8\(l^{L}\gets 0\)
9 repeat
10\(l^{L}\gets l^{L}+1\)
11\(N\leftarrow\) number of nodes in \(G\)
12\(\mathsf{M}\) = Optimize(\(G\), \(\mathsf{M}\)) (Algorithm 4)
13\(M\leftarrow\) number of modules in \(\mathsf{M}\)
14\(L=L(\mathsf{M})\)
15\(\delta L\gets L-L_{old}\)
16\(L_{old}\gets L\)
17 if\(M=1\) or\(M=N\)then
18 Break
19\(G\leftarrow\) Aggregate nodes within modules and links between modules to a new network
20\(\mathsf{M}\leftarrow\) one module per node in \(G\)
21 until\(\delta L>-\epsilon\) or\(l^{L}=l^{L}_{max}\) return\(\mathsf{M}\)
```
**Algorithm 3** Repeated node aggregation
```
1 functionoptimize(Network \(G\), Node-to-module map \(\mathsf{M}\))
2 Let \(l^{M}_{max}\) be a maximum number of iterations
3\(l^{M}\gets 0\)
4 repeat
5\(l^{M}\gets l^{M}+1\)
6 fornode \(n_{i}\in G\) in random order do
7 for link \(l_{ij}\) to neighboring node \(n_{j}\) in module \(m_{j}\)do
8 Calculate change in \(enter\) and \(exit\) flows for modules \(m_{i}\) and \(m_{j}\) if moving node \(n_{i}\) to module \(m_{j}\)
9 For state nodes, calculate change in physical node visit rates (Equation (25))
10 Calculate change in \(enter\) and \(exit\) flow if moving to a new module
11 Calculate change in code length \(\delta L_{ij}\) for each possible move of node \(n_{i}\) to module \(m_{j}\)
12 if\(\min_{j}\delta L_{ij}<-\epsilon\) and\(m_{j}\
eq m_{i}\)then
13 Update \(\mathsf{M}\) with \(m_{i}\gets m_{j}\)
14 Update \(enter\), \(exit\) and node flow in modules \(m_{i}\) and \(m_{j}\)
15\(L\gets L+\delta L_{ij}\)
16\(\delta L\gets L-L_{old}\)
17\(L_{old}\gets L\)
18 until\(\delta L>-\epsilon\) or\(l^{M}=l^{M}_{max}\) return\(\mathsf{M}\)
```
**Algorithm 4** Optimize network

### Fine-Tuning

In the fine-tuning step, Infomap tries to move single nodes out from existing modules into new or neighboring modules (Algorithm 5).