# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 4 Infomap
In this way, Infomap can explore the submodule hierarchy in parallel with a breadth-first search to efficiently find a multilevel clustering of the input network. ```
1 functionrepeatedSupModules(Network \(G\), Multilevel node-to-module map \(M\))
2\(Q\leftarrow\) top modules in \(M\)
3 Remove submodules in \(M\) if exist
4 while\(Q\) not empty do
5\(R\leftarrow\) empty queue to collect submodules
6 for module \(m_{i}\) in \(Q\) (in parallel) do
7\(G_{i}\leftarrow\) network of nodes and links within \(m_{i}\)
8\(N\leftarrow\) number of nodes in \(G_{i}\)
9\(M_{i}\leftarrow\)partition(\(G_{i}\)) (Algorithm 2)
10\(M_{i}\leftarrow\)repeatedSuperModules(\(G_{i}\), \(M_{i}\)) (Algorithm 7)
11\(\widehat{M}\leftarrow\) number of top modules in \(M_{i}\)
12 if\(\widehat{M}=1\) or \(\widehat{M}=N\)then
13 Replace \(m_{i}\) with top modules in \(M_{i}\)
14 for each top module \(\widehat{m}\) in \(M_{i}\)do
15 Add \(\widehat{m}\) to queue \(R\)
16\(Q\gets R\)
17 returnM
```

**Algorithm 7** Repeated supermodule clustering

### Download Infomap

Infomap can be downloaded from www.mapequation.org, which contains installation instructions, a complete list of running options, and examples for how to run Infomap stand-alone or with other software, including igraph, Python, Jupyter, and R. In the Appendix, we provide Infomap's basic syntax (Appendix A.1) and examples for how to cluster a multilayer network (Appendix A.2), a memory network (Appendix A.3), and a sparse memory network (Appendix A.4). The website also contains interactive storyboards to explain the mechanics of the map equation, and interactive visualizations to simplify large-scale networks and their changes over time. ### Mapping Multistep and Multi-Source Data with Infomap

We illustrate our approach by mapping network flows from air traffic data between more than 400 airports in the US [35]. For quarterly reported itineraries in 2011, we assembled pathways into four quarterly, two half-year, and one full-year collection. From pathways of length two, three, and four, for each collection we generated sparse memory networks corresponding to first-, second-, and third-order Markov models of flows. Then we generated sparse memory networks corresponding to multilayer networks with four layers from the quarterly collections and two layers from the half-yearcollections for all Markov orders. This example illustrates how sparse memory networks can go beyond standard representations and represent combinations of multilayer and memory networks. To identify communities in multistep and multi-source air traffic data represented with sparse memory networks, we run Infomap ten times and report the median values in Table 1. Except for a small drop in the number of physical nodes for the third-order models because some airports are not represented in long itineraries, the number of physical nodes remain the same for all models. However, the number of state nodes and links between them increases with order. Larger systems require state-node lumping based on minimum information loss into more efficient sparse memory networks that correspond to variable-order Markov models. Such more compact descriptions of higher-order can balance over- and underfitting as well as cut the computational time [18]. In any case, higher-order representations can better capture constraints on flows. For example, a drop in the entropy rate by one bit corresponds to doubled flow prediction, and the four-bit drop between the first- and third-order models corresponds to a sixteenfold higher flow prediction accuracy. These flows move with relatively long persistence times among groups of airports that form connected legs in frequent itineraries. Infomap capitalizes on this modular flow pattern and identifies pervasively overlapping modules. ## 5 Conclusions

The map equation applied to sparse memory networks provides a general solution to reveal modular patterns in higher-order flows through complex systems.